recursion

[Steve Holden]

Gigs_ wrote:
> Steve Holden wrote:
[...]
>>
>> regards
>>  Steve
>  >>> def factorial(n):
>     print "n =", n
>     if n==0:
>         return 1
>     else:
>         return n * factorial(n-1)
> 
>  >>> factorial(3)
> n = 3
> n = 2
> n = 1
> n = 0
> 6
> 
> 
> now i understand. but one question at the end this function return 1. how python 
> knows that it needs to multiply 1 with all recursive returns. (why python didnt 
> sum recursive return with 1?)
> 
> 
> that will be all, thanks in advance

Aah, that's the magic of recursion (not that it's really magic at all).

When you call factorial(3), the function sees the value of n as 3. So 
the if condition is false, so it must execute the return statement.

In order to do that it has to multiply n by the value of factorial n-1. 
So it makes a call to a *new copy* of factorial, and this one has the 
value 2 for n. The if statement again needs to execute the return 
statement, and before it can do that it needs the value of factorial 
n-1, so it makes a call to a *new copy* of factorial, and this one has 
the value 1 for n. The if statement again needs to execute the return 
statement, and before it can do that it needs the value of factorial 
n-1, so it makes a call to a *new copy* of factorial, and this one has 
the value 0 for n. [Are you detecting a pattern here?].

Finally *this* copy of factorial can immediately return the value of 1 
to its caller, which then multiplies that by 1 and returns it ti *its 
caller, which multiplies it by 2 and returns that to *its* caller, when 
multiplies it by 3 and returns the result, 6.

In other words, the computer builds a "stack" of partially-completed 
functions, and unwinds it when the innermost (topmost, whatever) finally 
sees that it can return a result without creating another stacked call 
to factorial.

Hope this straightens it out for you, it's a bit of a head-twister when 
you first come across it.

regards
  Steve
-- 
Steve Holden        +1 571 484 6266   +1 800 494 3119
Holden Web LLC/Ltd           http://www.holdenweb.com
Skype: holdenweb      http://del.icio.us/steve.holden

Sorry, the dog ate my .sigline