Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to organise the tracing of this recursion

  1. Oct 8, 2008 #1
    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. jcsd
  3. Oct 8, 2008 #2

    rcgldr

    User Avatar
    Homework Helper

    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;
    }
     
     
  4. Oct 9, 2008 #3

    uart

    User Avatar
    Science Advisor

    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 [itex]2^n[/itex] :bugeye:
     
    Last edited: Oct 9, 2008
  5. Oct 9, 2008 #4

    uart

    User Avatar
    Science Advisor

    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.
     
  6. Oct 10, 2008 #5

    rcgldr

    User Avatar
    Homework Helper

    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.

    [tex]a(n,0) = 1 + \sum_{i=0}^{n-1} 2^i[/tex]

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: How to organise the tracing of this recursion
  1. Recursion in C (Replies: 12)

Loading...