I can't seem to figure this recursion example out..how do I sum an array recusively decomposing by n/2?

[beer]

Given an array x[0] to x[n-1]

I need to sum every element in the array decomposing by n/2, using only two parameters: n, and the array itself

 

[tikwanleap]

sum an array recusively decomposing by n/2

😕😕 need more details. What does this mean?

 

[beer]

Originally posted by: tikwanleap

sum an array recusively decomposing by n/2

😕😕 need more details. What does this mean?

The array is of length n
when you make the function call to itself, you must divide n by 2 when getting the summation, rather than doing it linearly, i.e., n-1

 

[RichieZ]

i don't see how you can do it unless you use more paramters, like start and end indicies

 

[beer]

Originally posted by: RichieZ
i don't see how you can do it unless you use more paramters, like start and end indicies

it's possible

 

[tikwanleap]

Originally posted by: Elemental007

Originally posted by: tikwanleap

sum an array recusively decomposing by n/2

😕😕 need more details. What does this mean?

The array is of length n
when you make the function call to itself, you must divide n by 2 when getting the summation, rather than doing it linearly, i.e., n-1

ok, so i'm guessing here...

does that mean the function sums n/2 elements of the array and passes the the other half of the array to itself in the next function call?

 

[tikwanleap]

Originally posted by: tikwanleap

Originally posted by: Elemental007

Originally posted by: tikwanleap

sum an array recusively decomposing by n/2

😕😕 need more details. What does this mean?

The array is of length n
when you make the function call to itself, you must divide n by 2 when getting the summation, rather than doing it linearly, i.e., n-1

ok, so i'm guessing here...

does that mean the function sums n/2 elements of the array and passes the the other half of the array to itself in the next function call?

for example:

10 elements in array

the function sums the first 10/2 = 5 elements in the array

then it calls itself passing the remaining 5 elements in the array

is this what decomposing by n/2 means? I might be way off base here.

😕

 

[yoda291]

I think it means something like this.

You must create function as follows:

func(arr,n)
{
do something to func(arr,n/2)
}

 

[beer]

Originally posted by: yoda291
I think it means something like this.

You must create function as follows:

func(arr,n)
{
do something to func(arr,n/2)
}

More or less, this is correct....I think

 

[gopunk]

so basically, in O(log n) time? or are we allowed to do more than constant work per recursive call?

 

[beer]

Originally posted by: gopunk
so basically, in O(log n) time? or are we allowed to do more than constant work per recursive call?

its beyond the scope of this example, but I am betting it will involve the addition of two recursive calls (this is probably showing us what NOT to do), which would, of course, have a much lower time efficiency.

 

[KDOG]

WTF are you guys talking about? Brain melting......aaarrrgghhh.....

 

[m0ti]

umm...

int doStupidSum(int *array, int n) {
if (n <= 0)
return 0;
if (n == 1)
return array[0];

int split = n/2;
return doStupidSum(array, split) + doStupidSum(array + split, n - split);
}

and this really should be in the programming forum and not OT.

 

[beer]

Originally posted by: m0ti
umm...

int doStupidSum(int *array, int n) {
if (n <= 0)
return 0;
if (n == 1)
return array[0];

int split = n/2;
return doStupidSum(array, split) + doStupidSum(array + split, n - split);
}

and this really should be in the programming forum and not OT.

Thanks
that worked 🙂

 

[Koing]

the joys of Java.

Yeah finally I get to understand what you guys are on about.

I see myself asking for here soon!