How to organise the tracing of this recursion

[transgalactic]

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

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 don't 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
??

 

[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):

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

 

[uart]

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):

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

Hi Jeff, I don't 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

 

[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.

 

[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:

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