recursion
Marc 'BlackJack' Rintsch
bj_666 at gmx.net
Fri Sep 14 16:38:16 CEST 2007
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
More information about the Python-list
mailing list