February 8th, 2013, 11:59 AM

How multiple recursion is working in c?
Please explain how the following recursion is working and how the output is coming.
#include<stdio.h>
#include<conio.h>
int fact(int n)
{
int f,r;
if(n==1n==0)
return 1;
f=n*fact(n1);
printf("%d",f);
r=n+fact(n1);
printf(" %d ",r);
return f;
}
void main()
{
clrscr();
printf("%d",fact(4));
getch();
}
February 8th, 2013, 12:15 PM

Please edit your code to include [code][/code] tags.
Just look at a few other recent posts to see how it's done, and what code looks like when it is done.
February 9th, 2013, 11:09 AM

Originally Posted by burle
Please explain how the following recursion is working and how the output is coming.
I rather suspect that that is the question that your professor has asked of you. :rolleyes:
A problem that can be expressed in terms of a smaller problem of the same type can be implemented by recursion. For example:
3! = 3 x 2 x 1
but also:
3! = 3 x 2!
So in general:
n! = n * (n1)!
with an exception that:
1! = 1
So give a factorial function, the factorial of any value n can be expressed as an expression involving a further smaller factorial.
A terminating condition that is necessary that (a) guaranteed to be reached, and (b) provides an absolute answer. When the terminating condition is not met, the recursive expression is used.
To see this working in a practical sense, run your code in a debugger using single stepping and stepinto the fact() function, with the callstack display open.
February 9th, 2013, 08:11 PM

Thank u clifford
But I am unable to get your following statement.
To see this working in a practical sense, run your code in a debugger using single stepping and stepinto the fact() function, with the callstack display open.[/QUOTE]
If possible please indicate how to make callstack display open by using the debugger
February 10th, 2013, 03:22 AM

At risk of accidentally solving a different homework problem you have, I will show you an example of recursion very similar to your factorial problem to give you an idea of what you should be going for here.
Consider the problem of exponentiation over nonnegative integers. An integer base, b, raised to an integer power, e, can be expressed with a recursive function which takes two variables.
Lets call this function exp, and, because we're only considering integers (particularly, nonnegative ones but I don't want to overcomplicate this for you) it will return an integer and I'll use ^ to mean a mathematical exponentiation operator, not as any sort of legitimate programming syntax for you to use in your homework.
b^e = b*b*b*b*b*.....*b*b (e times)
This problem appears to have one part which you will use to recur on, and that is the exponent.
This means we have the following prototype for our exp function:
Code:
int exp(int b, int e)
For this problem, the base won't change; we're just passing it in so we know what to multiply by in our recursion. The exponent is what we will recur on. Our base case is when e = 0, since for any integer b, b^0 = 1. It is important to identify the part of the problem you will recur on, and your base case for any problem you approach with recursion. Don't confuse the terms base case and base when I mean base of the exponent. They are completely different.
So how will this function be used? When we want 10^5, for example, we will call exp(10, 5) and expect it to return 100,000 because 10^5 = 100,000.
Now lets get under the hood of this problem. We have our base, b, and our exponent e. Since the exponent is the piece we are recurring on, the first thing we always do is check for the base case for e = 0 with the following:
Code:
if(e <= 0) return 1;
That is the most important, and easiest, part of the problem. Note that I include negative ints as part of the base case, since we're only concerned with nonnegative exponents and for simplicity we'll just treat any negative int as a 0.
Now comes the recursion part.
b^e = b*b*b*b*b*.....*b*b (e times)
Any time we do not have the base case, we will multiply b by the return value of a recursive call to our exp function. Since we start with exponent e, it is logical to recursively call exp with the same b and e  1 as arguments.
Code:
else return b*exp(b, e  1);
As a recursive function recurs down to its base case, it accumulates a stack of function calls. Lets look at the complete exp function:
Code:
int exp(int b, int e)
{
if(e <= 0)
return 1;
else
return b*exp(b, e  1);
}
Suppose we call exp(2, 3), or in other words, we want to find 2^3.
Call 1:
e is 3, so we do not have the base case
our b is 2, and is what we will multiply by
so we recursively call exp with b, and e1
return 2*exp(2, 2)
Call 2:
e is 2, so we do not have the base case
exp is recursively called with b, and e  1
return 2*exp(2, 1)
Call 3:
e is 1, we don't have the base case quite yet
exp is recursively called with b, and e  1
return 2*exp(2, 0)
Call 4:
e is 0, the base case is met and we return 1 and go back to the return statement in Call 3 >
Call 3: return 2*1 back to the return statement in Call 2 >
Call 2: return 2*2 back to the return statement in Call 1 >
Call 1: return 2*4 = 8
And then finally, the exp finishes computing 2^3 and returns 8.
Last edited by jakotheshadows; February 10th, 2013 at 03:32 AM.
February 10th, 2013, 05:54 AM

Thank you very much jakotheshadows for such a wonderful explanation on recursion.
But my problem is still their i.e. how the function call and returning of values are working in multiple recursions.
February 10th, 2013, 10:51 AM

Originally Posted by burle
If possible please indicate how to make callstack display open by using the debugger
That would depend entirely on what tool chain (compiler, debugger, IDE etc.) you are using. I can't be more specific without knowing what you are using.
February 10th, 2013, 11:02 AM

Originally Posted by burle
But my problem is still their i.e. how the function call and returning of values are working in multiple recursions.
Here is an illustration of calling fact(3), fact() is called recursively until the argument is 1, which returns, where it is multiplied by 2 (1 x 2 = 2) and returned and multiplied by three (3 x 2 = 6).
Code:
fact(3)
 3 x fact(2)
  2 x fact(1)
  
  return(1)
 return(2)
return(6)
February 10th, 2013, 06:50 PM

Originally Posted by burle
Thank you very much jakotheshadows for such a wonderful explanation on recursion.
But my problem is still their i.e. how the function call and returning of values are working in multiple recursions.
How its working? You need to be more specific with your question. What do you mean by "multiple recursions"? Are you referring to how your fact function makes two recursive calls to fact or something else?
February 11th, 2013, 11:50 AM

Yes your guess is right. Actually I want to know how fact function is two recursive calls i.e. whether it is working simultaneously or after finishing the work of one recursion the second recursion is going on.
February 11th, 2013, 08:36 PM

I'll try to show you how to fish. For example,
Code:
f=n*fact(n1);
printf("%d",f);
r=n+fact(n1);
printf(" %d ",r);
if you want to know the exact sequence of the particular calls, try putting a printf just before the assignment to f that says "n*fact(n1)" and put a printf just before the assignment to r that says "n+fact(n1)", and for now comment out the original printfs. Also include the current value of n in each of these new printfs.
The first printf should look something like this:
Code:
printf("n*fact(n1), n = %d\n", n);
February 11th, 2013, 08:45 PM

And also, no the two separate calls do not happen simultaneously. There is a predictable sequence to it.
February 12th, 2013, 08:48 AM

Originally Posted by burle
Actually I want to know how fact function is two recursive calls i.e. whether it is working simultaneously or after finishing the work of one recursion the second recursion is going on.
recursion is not the same as concurrancy.
In the expression
3! = 3 x 2!
When you call fact(3), fact(2) runs as a subroutione of fact(2) and in turn fact(1) runs as a subroutine of fact(2).
As I said before, you can see this clearly by using a debugger, but after your last query on that you have not been forthcoming with the information. Moreover I attempted to illustrate the call stack in my previous response.
To be honest it can hardly be expressed more clearly than it has already, so if you don't get it yet, read the responses again and perhaps walk through the code on paper.
February 12th, 2013, 09:13 AM

Maybe this will make it clearer.
Code:
#include <stdio.h>
static int r_count = 0 ;
int fact(int n)
{
int f, r;
r_count++ ;
r = r_count ;
if(n==1n==0)
{
printf( "%d: fact(%d) = 1\n", r, n ) ;
return 1;
}
f=n*fact(n1);
printf( "%d: fact(%d) = %d\n", r, n, f ) ;
return f;
}
int main()
{
r_count = 0 ;
printf("%d",fact(4));
}
The output is:
Code:
4: fact(1) = 1
3: fact(2) = 2
2: fact(3) = 6
1: fact(4) = 24
24
The print is done in each case just before fact() returns and starts with a recursion count r. Notice the recursion depth starts at 4 and "unwinds" back to the top level call. i.e.:
main() calls fact(4)
fact(4) calls fact(3)
fact(3) calls fact(2)
fact(2) calls fact(1),
fact (1) prints and returns to fact(2)
fact(2) prints and returns to fact(3)
fact(3) prints and returns to fact(4)
fact(4) prints and returns to main()
main() prints the result
Comments on this post
February 12th, 2013, 08:00 PM
