How to organise the tracing of this recursion

1. Oct 8, 2008

transgalactic

i tried to trace this recurtion for small numbers
but i dont know how to write down
in an organized way

Code (Text):

int a(int n,int count){
int i;
for(i=0;i<n;i++)
count =a(i,count);
return count+1;
}

a(0,0) is easy its 1
a(1,0) a little harder it returns 2

but when i get to
a(2,0) i get confused and i cand follow one logical path
i dont how to write it down

i tried like that:
a(n=2,count=0):
for (0,0<2)
count=a(0,0)=1
for (1,1<2)
count=a(1,1)

a(1,1)
for (0,0<1)
count=a(0,1)
a(0,1)=2

here i am getting really confused
??

2. Oct 8, 2008

rcgldr

As written, it appears that a(2, ...) will just nest forever until you run out of stack space. Perhaps you meant to write it as this (for loop starts with i=1, recursive call uses i-1):

Code (Text):

int a(int n,int count){
int i;
for(i=1; i<n; i++)
count =a(i-1,count);
return count+1;
}

3. Oct 9, 2008

uart

Hi Jeff, I dont think it nests forever with n=2. I just traced a(2,0) and I got the result of 4, it wasn't too difficult.

BTW. Note that with the "for i=0, i<n, i++" loop, each time it recurses it only counts up to n-1 so eventually you get to n=0 and starts un-nesting. I don't see the problem.

Anyway it's a hell ugly way to compute $2^n$

Last edited: Oct 9, 2008
4. Oct 9, 2008

uart

BTW transgalactic. To understand (or trace) recursion you first must fully understand how "pass by value" function paramaters work. If you're not familiar with what this means, and in particular what it means with regard to "no side effects of the functions actual parameters" then you should read up on this before you go any further.

5. Oct 10, 2008

rcgldr

I kept thinking <= instead of < in the for loop. (I should never post when I'm sleepy). As was mentioned in a later thread, a (
n, c) returns 2^n + c.

for the case a(3,0), the calling sequence looks like this:
Code (Text):

a(3,...)
a(0,...)
a(1,...)
a(0,...)
a(2,...)
a(0,...)
a(1,...)
a(0,...)

a(0, ... ) is called 4 times, a(1, ...) is called 2 times, a(2, ...) 1 time, and a(3, ...) 1 time.

$$a(n,0) = 1 + \sum_{i=0}^{n-1} 2^i$$

For the summation part:
s(n-1) = 2^0 + 2^1 + 2^2 ... + 2^(n-1)

multiply s(n-1) by 2:
2 s(n-1) = 2^1 + 2^2 + ... + 2^n

subtract s(n-1) from 2 s(n-1):
2 s(n-1) - s(n-1) = 2^n + 2^(n-1) - 2^(n-1) + ... (2^1 - 2^1) - 2^0
s(n-1) = 2^n - 1

a(n) = 1 + s(n-1) = 1 + 2^n -1 = 2^n

Last edited: Oct 10, 2008