Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |
 User Name: Password: Remember me

New Free Tools on Dev Shed!
We're Excited to announce that Dev Shed now has 70 free tools on the site. To learn more, click here!

 Add This Thread To: Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb
 « Previous Thread | Next Thread » Thread Tools Search this Thread Rate Thread Display Modes
 Dev Shed Forums Sponsor:
#1
February 8th, 2013, 11:59 AM
 burle
Registered User

Join Date: Jan 2013
Posts: 6
Time spent in forums: 1 h 37 m 55 sec
Reputation Power: 0
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();
}

#2
February 8th, 2013, 12:15 PM
 salem
Contributed User

Join Date: Jun 2005
Posts: 4,258
Time spent in forums: 2 Months 4 Weeks 1 Day 13 h 52 m 26 sec
Reputation Power: 1827
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.
__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper

#3
February 9th, 2013, 11:09 AM
 clifford
Contributing User

Join Date: Aug 2003
Location: UK
Posts: 4,965
Time spent in forums: 1 Month 4 Days 3 h 25 m 52 sec
Reputation Power: 1801
Quote:
 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.

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.

#4
February 9th, 2013, 08:11 PM
 burle
Registered User

Join Date: Jan 2013
Posts: 6
Time spent in forums: 1 h 37 m 55 sec
Reputation Power: 0
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

#5
February 10th, 2013, 03:22 AM
 jakotheshadows
Contributing User

Join Date: Aug 2009
Posts: 149
Time spent in forums: 3 Days 12 h 33 m 32 sec
Reputation Power: 36
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:

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

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

Last edited by jakotheshadows : February 10th, 2013 at 03:32 AM.

#6
February 10th, 2013, 05:54 AM
 burle
Registered User

Join Date: Jan 2013
Posts: 6
Time spent in forums: 1 h 37 m 55 sec
Reputation Power: 0
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.

#7
February 10th, 2013, 10:51 AM
 clifford
Contributing User

Join Date: Aug 2003
Location: UK
Posts: 4,965
Time spent in forums: 1 Month 4 Days 3 h 25 m 52 sec
Reputation Power: 1801
Quote:
 Originally Posted by burle If possible please indicate how to make call-stack 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.

#8
February 10th, 2013, 11:02 AM
 clifford
Contributing User

Join Date: Aug 2003
Location: UK
Posts: 4,965
Time spent in forums: 1 Month 4 Days 3 h 25 m 52 sec
Reputation Power: 1801
Quote:
 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)
```

#9
February 10th, 2013, 06:50 PM
 jakotheshadows
Contributing User

Join Date: Aug 2009
Posts: 149
Time spent in forums: 3 Days 12 h 33 m 32 sec
Reputation Power: 36
Quote:
 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?

#10
February 11th, 2013, 11:50 AM
 burle
Registered User

Join Date: Jan 2013
Posts: 6
Time spent in forums: 1 h 37 m 55 sec
Reputation Power: 0
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.

#11
February 11th, 2013, 08:36 PM
 jakotheshadows
Contributing User

Join Date: Aug 2009
Posts: 149
Time spent in forums: 3 Days 12 h 33 m 32 sec
Reputation Power: 36
I'll try to show you how to fish. For example,

Code:
```f=n*fact(n-1);
printf("%d",f);
r=n+fact(n-1);
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(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:

Code:
`printf("n*fact(n-1), n = %d\n", n);`

#12
February 11th, 2013, 08:45 PM
 jakotheshadows
Contributing User

Join Date: Aug 2009
Posts: 149
Time spent in forums: 3 Days 12 h 33 m 32 sec
Reputation Power: 36
And also, no the two separate calls do not happen simultaneously. There is a predictable sequence to it.

#13
February 12th, 2013, 08:48 AM
 clifford
Contributing User

Join Date: Aug 2003
Location: UK
Posts: 4,965
Time spent in forums: 1 Month 4 Days 3 h 25 m 52 sec
Reputation Power: 1801
Quote:
 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 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.

#14
February 12th, 2013, 09:13 AM
 clifford
Contributing User

Join Date: Aug 2003
Location: UK
Posts: 4,965
Time spent in forums: 1 Month 4 Days 3 h 25 m 52 sec
Reputation Power: 1801
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==1||n==0)
{
printf( "%d: fact(%d) = 1\n", r, n ) ;
return 1;
}
f=n*fact(n-1);

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
ptr2void agrees!

#15
February 12th, 2013, 08:00 PM
 burle
Registered User

Join Date: Jan 2013
Posts: 6
Time spent in forums: 1 h 37 m 55 sec
Reputation Power: 0
Thank u clifford.

 Viewing: Dev Shed Forums > Programming Languages > C Programming > How multiple recursion is working in c?

## Developer Shed Advertisers and Affiliates

 Thread Tools Search this Thread Search this Thread: Advanced Search Display Modes Rate This Thread Linear Mode Rate This Thread: 5 : Excellent 4 : Good 3 : Average 2 : Bad 1 : Terrible

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts vB code is On Smilies are On [IMG] code is On HTML code is Off
 View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox Forum Jump Please select one User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home -------------------- Programming Languages    PHP Development        PHP FAQs and Stickies    Perl Programming        Perl FAQs and Stickies    C Programming        C Programming FAQs and Stickies    Java Help        Java FAQs    Python Programming        Python Programming FAQs    Ruby Programming        Ruby Programming FAQs    Game Development        Game Development FAQs Programming Languages - More    ASP Programming        ASP Programming FAQs    .Net Development        .Net Development FAQs    Visual Basic Programming        Visual Basic Programming FAQs    Software Design        Software Design FAQs    ColdFusion Development        ColdFusion Development FAQs    Delphi Programming        Delphi Programming FAQs    Regex Programming        Regex Programming FAQs    XML Programming        XML Programming FAQs    Other Programming Languages        Other Programming Languages FAQs Web Design    HTML Programming        HTML Programming FAQs    JavaScript Development        JavaScript Development FAQs    CSS Help        CSS Help FAQs    Flash Help        Flash Help FAQs    Photoshop Help        Photoshop Help FAQs    Web Design Help        Web Design Help FAQs    Website Critiques        Website Critiques FAQs    Search Engine Optimization        Search Engine Optimization FAQs Mobile Programming    Mobile Programming        Mobile Programming FAQs    iPhone SDK Development        iPhone SDK Development FAQs    Android Development        Android Development FAQs    BlackBerry Development        BlackBerry Development FAQs Web Site Management    Business Help        Business Help FAQs    Development Software        Development Software FAQs    Scripts        Scripts FAQs Databases    Database Management        Database Management FAQs    DB2 Development        DB2 Development FAQs    MySQL Help        MySQL Help FAQs    PostgreSQL Help        PostgreSQL Help FAQs    Firebird SQL Development        Firebird SQL Development FAQs    MS SQL Development        MS SQL Development FAQs    Oracle Development        Oracle Development FAQs    LDAP Programming        LDAP Programming FAQs System Administration    Mail Server Help        Mail Server Help FAQs    Apache Development        Apache Development FAQs    Security and Cryptography        Security and Cryptography FAQs    Antivirus Protection        Antivirus Protection FAQs    DNS        DNS FAQs    IIS        IIS FAQs    Networking Help        Networking Help FAQs    FTP Help        FTP Help FAQs Operating Systems    BSD Help        BSD Help FAQs    Linux Help        Linux Help FAQs    UNIX Help        UNIX Help FAQs    Windows Help        Windows Help FAQs    Mac Help        Mac Help FAQs Web Hosting    Web Hosting        Web Hosting FAQs    Free Web Hosting        Free Web Hosting FAQs    Web Hosting Requests        Web Hosting Requests FAQs    Web Hosting Offers        Web Hosting Offers FAQs Computer Hardware    Computer Hardware    CPUs        CPUs FAQs    Cooling        Cooling FAQs    Embedded Programming        Embedded Programming FAQs    Motherboards        Motherboards FAQs    Multimedia Hardware        Multimedia Hardware FAQs Other    Dev Shed Lounge        Dev Shed Lounge FAQs    Development Articles        Development Articles FAQs    Beginner Programming        Beginner Programming FAQs    Hire A Programmer        Hire A Programmer FAQs    Project Help Wanted        Project Help Wanted FAQs Latest News Updated Hourly    Technology News    Business News    Science News Forum Information    Forum Rules/Guidelines        Forum Rules/Guidelines FAQs    Forum Announcements        Forum Announcements FAQs    Dev Shed Gaming Center        Go to the Dev Shed Battle Arena        Go to the Dev Shed Arcade Games        Go to the Legend of the Green Dragon    Suggestions & Feedback        Suggestions & Feedback FAQs

 Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.

© 2003-2013 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap