Page 1 of 2 12 Last
  • Jump to page:
    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    6
    Rep 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. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,379
    Rep Power
    1871
    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
  4. #3
  5. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,109
    Rep Power
    1802
    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 * (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.
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    6
    Rep 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
  8. #5
  9. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2009
    Posts
    149
    Rep 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 02:32 AM.
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    6
    Rep 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.
  12. #7
  13. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,109
    Rep Power
    1802
    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.
  14. #8
  15. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,109
    Rep Power
    1802
    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)
  16. #9
  17. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2009
    Posts
    149
    Rep Power
    36
    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?
  18. #10
  19. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    6
    Rep 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.
  20. #11
  21. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2009
    Posts
    149
    Rep 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);
  22. #12
  23. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2009
    Posts
    149
    Rep Power
    36
    And also, no the two separate calls do not happen simultaneously. There is a predictable sequence to it.
  24. #13
  25. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,109
    Rep Power
    1802
    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.
  26. #14
  27. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,109
    Rep Power
    1802
    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
  28. #15
  29. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    6
    Rep Power
    0
    Thank u clifford.
Page 1 of 2 12 Last
  • Jump to page:

IMN logo majestic logo threadwatch logo seochat tools logo