Recursion
Jeff Epler
jepler at unpythonic.net
Mon Sep 29 03:13:48 CEST 2003
> "Explanation From the Book Begins Here"++++++++++++++++++
>
> >def factorial(n):
> > if n == 0:
> > return 1
> > else:
> > recurse = factorial(n1)
> > result = n * recurse
> > return result
> >
> > The flow of execution is as follows.
> > If we call "factorial" with the value 3:
> >
> > Since 3 is not 0, we take the second branch and calculate the
> > factorial of n1...
> > Since 2 is not 0, we take the second branch and calculate
> > the factorial of n1...
> > Since 1 is not 0, we take the second branch and calculate
> > the factorial of n1...
> > Since 0 is 0, we take the first branch and return 1
> > without making any more recusive calls.
> > The return value (1) is multiplied by n, which is 1,
> > and the result is returned.
> > The return value (1) is multiplied by n, which is 2, and the
> > result is returned.
> > The return value (2) is multiplied by n, which is 3, and the
> > result, 6, becomes the return value of the function that started
> > the whole process.
> "Example Ends Here"++++++++++++++++++++++++++++++++
>
On Mon, Sep 29, 2003 at 12:48:29AM +0000, Jakle wrote:
> I thought I understood what was going on untill "Since 0 is 0...", but after
> that I get lost. Where are the variables being stored.
Each separate invocation of 'factorial' has an associated value for a
variable named 'n'. So on the 'Since 0 is 0' step, there are 4
invocations of 'factorial', one with n==0, one with n==1, etc. This is
what 3.10 "Variables and parameters are local" intends to explain:
 When you create a local variable inside a function, it only exists
 inside the function, and you cannot use it outside. For example:

 def catTwice(part1, part2):
 cat = part1 + part2
 printTwice(cat)

 This function takes two arguments, concatenates them, and then prints
 the result twice. We can call the function with two strings:

 >>> chant1 = "Pie Jesu domine, "
 >>> chant2 = "Dona eis requiem."
 >>> catTwice(chant1, chant2)
 Pie Jesu domine, Dona eis requiem. Pie Jesu domine, Dona eis requiem.

 When catTwice terminates, the variable cat is destroyed. If we try to
 print it, we get an error:

 >>> print cat
 NameError: cat

 Parameters are also local. For example, outside the function printTwice,
 there is no such thing as bruce. If you try to use it, Python will
 complain.
So not only do catTwice and printTwice have different local names, each
invocation of catTwice (or factorial) has its own values for local
names.
Jeff
More information about the Pythonlist
mailing list