Where is my mistake in undersanding the order of this code

In summary, 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++)printf("%d",a(i,0));printf("\n%d\n",a(i,10));return 0;}int b(int n,int count){int i;count = a(n,count);for(i=0;i<n;
  • #1
transgalactic
1,395
0
when i compile it i get perfectly well output
without any endless recursion

but when i trace this code:
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;
  }


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

??
 
Technology news on Phys.org
  • #2
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.
 
  • #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:
  • #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?
 
  • #5
transgalactic said:
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.
 
  • #6
yep :)
 
  • #7
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:
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.
 
  • #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 into a big mess
?
 
  • #9
transgalactic said:
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.
 
  • #10
I don't see how that is the case. I tried out the program with cout statements added:

Code:
  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:
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:
  • #11
Yes that's correct. I just posted the same thing in the other thread a couple of minutes ago.
 
  • #12
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:
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:

1. What is the most common mistake when understanding the order of code?

The most common mistake when understanding the order of code is not properly understanding the syntax and structure of the programming language being used. This can lead to misinterpreting the purpose and function of certain lines of code.

2. How can I ensure that I understand the order of code correctly?

To ensure that you understand the order of code correctly, it is important to thoroughly read and understand the documentation of the programming language. It is also helpful to practice writing and debugging code to gain a better understanding of how it functions.

3. What should I do if I am unsure about the order of code in a program?

If you are unsure about the order of code in a program, it is best to consult with more experienced programmers or seek help from online resources. You can also use debugging tools to step through the code and see how it is being executed.

4. Can a small mistake in the order of code have a big impact on the program's functionality?

Yes, even a small mistake in the order of code can have a big impact on the program's functionality. This is because programming languages are very specific and require precise syntax and structure to function correctly. A small mistake can cause errors or unexpected results.

5. How can I avoid making mistakes in the order of code?

To avoid making mistakes in the order of code, it is important to practice good coding habits such as using proper indentation and commenting your code. It is also helpful to break down complex tasks into smaller, manageable chunks and to test and debug your code regularly.

Similar threads

  • Programming and Computer Science
Replies
9
Views
963
  • Programming and Computer Science
Replies
1
Views
842
  • Programming and Computer Science
Replies
10
Views
1K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
23
Views
1K
  • Programming and Computer Science
Replies
4
Views
710
  • Programming and Computer Science
Replies
22
Views
2K
  • Programming and Computer Science
Replies
5
Views
846
  • Programming and Computer Science
Replies
3
Views
1K
  • Programming and Computer Science
Replies
4
Views
880
Back
Top