Where is my mistake in undersanding the order of this code

[transgalactic]

when i compile it i get perfectly well output
without any endless recursion

but when i trace this code:

#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;
  }

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

??

 

[Defennder]

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.

 

[transgalactic]

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 ??

 

[transgalactic]

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?

 

[uart]

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?

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.

 

[transgalactic]

yep :)

 

[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;
}

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.

 

[transgalactic]

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 into a big mess
?

 

[rcgldr]

i need to get the output of a(2,0)

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.

 

[Defennder]

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

  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:

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.

 

[uart]

Yes that's correct. I just posted the same thing in the other thread a couple of minutes ago.

 

[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