Recursion

This is a discussion on Recursion within the C Programming forums, part of the General Programming Boards category; I have the following code: Code: int factorial( int n){ if ( n == 0 ) return 1; else return ...

  1. #1
    Registered User
    Join Date
    Aug 2007
    Posts
    270

    Question Recursion

    I have the following code:
    Code:
    int factorial( int n){
      if ( n == 0 )
        return 1;
      else
        return n * factorial ( n-1 );
    }
    i dont get why you have 2 return statements. Because once it reaches 0, it will return 1. But why does it also return the result of: return n * factorial ( n-1 );?

    Thanks

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    If you've gotten to recursion, surely you've gotten to if-else. Edit: Or maybe you mean the stack? Say you call factorial(5). Then the else happens, so you return 5*factorial(4). But we don't know factorial(4), so we do that. That returns 4*factorial(3). But we don't know factorial(3), so we do that. That returns 3*factorial(2). But we have to call factorial(2), and that returns 2*factorial(1), and factorial(1) returns 1*factorial(0). Now, factorial(0) returns 1. Hence factorial(1) returns 1*1=1, hence factorial(2) returns 2*1=2, hence factorial(3) returns 3*2=6, hence factorial(4) returns 4*6=24, hence factorial(5) returns 5*24=120. You call the thing six times, so you need six returns.
    Last edited by tabstop; 11-13-2008 at 08:56 PM.

  3. #3
    Registered User
    Join Date
    Sep 2008
    Posts
    58
    The first return is to get out of the recursion or else it won't know when to stop.

  4. #4
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    Because the factorial is the the product of N and the previous factorial.

    This is just the definition of factorial written in C.

    0! = 1
    N! = N*(N-1)!
    Last edited by King Mir; 11-14-2008 at 06:45 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by King Mir View Post
    0! = 1
    N! = N*(N-1)!
    Minor correction above.

    So the summary is that we return a value from each call to factorial - sometimes that involves another call to factorial, which in turn returns a value back to the original level of factorial. If you change the code to print n at the top of the function, and add a variable to hold the returned value and print that before you return, then you'll see better how it works. It is a bit "magical" before you get your head around it.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 10:37 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 09:24 AM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21