Recursion

[taurus]

I have the following 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

[tabstop]

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.

[blurx]

The first return is to get out of the recursion or else it won't know when to stop.

[King Mir]

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

[matsp]

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