recursion

[Marc 'BlackJack' Rintsch]

On Fri, 14 Sep 2007 15:58:39 +0200, Gigs_ wrote:

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

Because there is a ``*`` and not a ``+`` in the last line of the function.

Let's play this through (I abbreviate the function name to just `f()`):

Execution of f(3) leads to the second return:

r1 f(3):  return 3 * f(2)

This multiplication can't take place until ``f(2)`` is calculated so the
current function call is "suspended" and evaluated later, when the result
of ``f(2)`` is known.  The call in that line is replaces with the result
then.  Calling ``f(2)`` leads to:

r2 f(2):  return 2 * f(1)

The same again, another call to `f()` with 1 as argument:

r3 f(1):  return 1 * f(0)

Now the last call takes the other ``if`` branch:

r4 f(0):  return 1

The 1 is returned to the previus call:

r3 f(1):  return 1 * 1

This can be evaluated now and is returned to its caller:

r2 f(2):  return 2 * 1

Again this is evaluated and returned to its caller:

r1 f(3):  return 3 * 2

And here we have the final result that is returned from the first call to
`f()`.

Ciao,
	Marc 'BlackJack' Rintsch