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

Where is my mistake in undersanding the order of this code

  1. Oct 8, 2008 #1
    when i compile it i get perfectly well output
    without any endless recursion

    but when i trace this code:
    Code (Text):

    #include <stdio.h>
    int a(int n,int count){
          int i;
          for(i=0;i<n;i++)
               count =a(i,count);           <<<<<<<<<<the problematic line
               return count+1;
    }

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

      int main (){
        int i;
        for (i=0;i<4;i++)
          printf("%d",a(i,0));
          printf("\n%d\n",a(i,10));

          for (i=0;i<4;i++)
            printf("%d",b(i,0));
            printf("\n%d\n",b(i,10));
    return 0;
      }
     

    Code (Text):

    Main:
    for (i=0;i<4;i++)             i=0
    printf("%d",a(0,0));

    a:  

     n=0 count=0
    int a(0,0){
    for(i=0;i<n;i++)
        count =a(i,count);  a=0 count=0
     
    it will always call a again and again there is no end to this recurtion

    ???????
     
  2. jcsd
  3. Oct 8, 2008 #2

    Defennder

    User Avatar
    Homework Helper

    The recursion has a base case. What is a(0,3) for example? Take note that the for loop won't execute under some conditions. Try tracing out the function calls for a(2,3) for example. Start with small numbers, because the ouput indicates that a hell LOT of function calls have been done.
     
  4. Oct 8, 2008 #3
    thanks

    is there a way to predict the outcome by the output of the first numbers??

    or i need to execute in the paper each line each time ??
     
    Last edited: Oct 8, 2008
  5. Oct 8, 2008 #4
    is there some manual for solving this kind of stuff

    because if i will write down every line each time it executes
    it takes to much time

    is there any manual???
     
  6. Oct 8, 2008 #5

    uart

    User Avatar
    Science Advisor

    This is recursion. This is how recursion works. As already explained you should try hand tracing it only for small values of the parameters otherwise it gets unweildly very quickly.

    BTW. Why did you write the program. What is it supposed to achieve. Let me guess you didn't write it but it was homework of some type.
     
  7. Oct 8, 2008 #6
  8. Oct 8, 2008 #7

    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;
    }
     
    I also posted this in the other thread. When you do recursion, where the depth is based on an input paramater, that paramter has to be decreased in each recursive call or else the calls would go on forever, except that you'd run out of stack space.

    Note that if "n" is 0 (or negative), the result is the same as calling a with "n" = 1.
     
  9. Oct 8, 2008 #8
    in order for me to find a pattern

    i need to get the output of a(2,0) in a brute force way
    following each line

    but as i showed earlier
    when i try to write down each stage
    is some point i get lost

    i need some organized way to follow in order to get the output of a(2,0)
    i tried many ways but in every one of them
    it turns in to a big mess
    ????
     
  10. Oct 9, 2008 #9

    rcgldr

    User Avatar
    Homework Helper

    With your code as orginally written, there will never be any output. each instance of a will call a with a value for n of 0 and 1, which will return, then call a with a value of n for whill call a with a value of n of 2, which in turn will eventually call a with n==2, and so on. The chain will just keep getting deeper and never return.
     
  11. Oct 9, 2008 #10

    Defennder

    User Avatar
    Homework Helper

    I don't see how that is the case. I tried out the program with cout statements added:

    Code (Text):
     
      1 #include <stdio.h>
      2 #include <iostream>
      3 using namespace std;
      4
      5 int a(int n,int count){
      6     int i;
      7     cout<<"Function call"<<endl;
      8     for(i=0;i<n;i++)
      9     {
     10         cout<<"a("<<i<<","<<count<<")"<<endl;
     11         count = a(i,count);
     12         cout<<"count="<<count<<endl;}
     13         return count+1;
     14 }

    int main() {
    cout<<a(2,0)<<endl;
    }
     
    This was the output:
    Code (Text):

    Function call
    a(0,0)
    Function call
    count=1
    a(1,1)
    Function call
    a(0,1)
    Function call
    count=2
    count=3
    4
     
    It's pretty confusing to trace the program execution, I'd admit.
     
    Last edited: Oct 9, 2008
  12. Oct 9, 2008 #11

    uart

    User Avatar
    Science Advisor

    Yes that's correct. I just posted the same thing in the other thread a couple of minutes ago.
     
  13. Oct 10, 2008 #12

    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: Where is my mistake in undersanding the order of this code
  1. Critique my C++ code (Replies: 11)

Loading...