Recursion

[Jeff Epler]

> "Explanation From the Book Begins Here"++++++++++++++++++
> 
> >def factorial(n):
> >    if n == 0:
> >        return 1
> >    else:
> >        recurse = factorial(n-1)
> >        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 n-1...
> >        Since 2 is not 0, we take the second branch and calculate
> >        the factorial of n-1...
> >            Since 1 is not 0, we take the second branch and calculate
> >            the factorial of n-1...
> >                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