CODEWITHSUNDEEP
crecursion
user2390775
user2390775

Reputation: 65

What does this recursive function do

i am doing some exam prep and one of the question is to describe what the following piece of C code does.

int g(int *a, int b ,int c){
if(b==c) return a[b];
return g(a,b,(b+c)/2) + g(a,(b+c)/2+1 ,c);}

Cant seem to figure out the recursion, from my understanding the sum of the left hand is sum of the series b+2^n/2*c and sum of the series of right to be (2^n/2)*(b+c) where n starts at 0. But there is no value for n that will make the series to be equal b or c respectively. Does that mean if the first if condition isn't meet it will continue on for infinity?

Upvotes: 0

Views: 74

Answers (1)

Arun
Arun

Reputation: 20383

Assuming b < c, g() returns the sum of the elements of the array a[] from index b to index c (both inclusive)

In other words,

g( a, b, c ) := 

int sum = 0;
for( int i = b; i <= c; ++i )
    sum += a[ i ];
return sum;

EDIT Proof Sketch

Assume c - b = n

(b + c)/2
= (c - b + 2b)/2
= (c - b)/2 + b
= b + n/2

Thus, g( a, b, (b + c)/2 ) + g( a, (b + c)/2 + 1, c )
= g( a, b, b + n/2 ) + g( a, b + n/2 + 1, c )

Upvotes: 2

Related Questions