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==1||n==0)
return 1;
f=n*fact(n-1);
printf("%d",f);
r=n+fact(n-1);
printf(" %d ",r);
return f;
}
void main()
{
clrscr();
printf("%d",fact(4));
getch();
}

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.

I rather suspect that that is the question that your professor has asked of you.

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 * (n-1)!

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 step-into the fact() function, with the call-stack display open.

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 step-into the fact() function, with the call-stack display open.[/QUOTE]

If possible please indicate how to make call-stack display open by using the debugger

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 non-negative 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, non-negative ones but I don't want to over-complicate 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:



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:



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 non-negative 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.



As a recursive function recurs down to its base case, it accumulates a stack of function calls. Lets look at the complete exp function:



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 e-1
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.

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.

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.

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).

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?

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.

I'll try to show you how to fish. For example,



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(n-1)" and put a printf just before the assignment to r that says "n+fact(n-1)", 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:

And also, no the two separate calls do not happen simultaneously. There is a predictable sequence to it.

recursion is not the same as concurrancy.

In the expression

3! = 3 x 2!

When you call fact(3), fact(2) runs as a sub-routione of fact(2) and in turn fact(1) runs as a sub-routine 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.

Maybe this will make it clearer.



The output is:


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

Thank u clifford.