Recursion

[Mensanator]

>Subject: Recursion
>From: "Jakle" jakle1 at hotmail.com 
>Date: 9/28/2003 7:48 PM Central Standard Time
>Message-id: <xjLdb.565$Vb3.450032 at news1.news.adelphia.net>
>
>Hi all. Need alittle help here. This is an example from "How to Think Like a
>Computer Scientist: Learning with Python, Chapter 5".  It's an open source
>ebook, so if you feel like it you can find it here:
>http://www.ibiblio.org/obp/thinkCSpy/
>
>The example uses factorials to explain more complex recursion.
>
>"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"++++++++++++++++++++++++++++++++
>
>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.
>And how does 1*1=2 ---> The return value (1) is multiplied by n, which is 1,

You've made a mistake here. 1*1=1, not 2. You can always modify the 
program to add some debugging aids. Here, I added a second parameter
to the function so we can track the level of recursion via indenting:

# start

def factorial(n,t):
    print '\t'*t,'factorial of',n
    if n == 0:
	print "\t"*t,'result =',1
        return 1
    else:
        recurse = factorial(n-1,t+1)
        result = n * recurse
	print "\t"*t,'result =',n,' * ',recurse,' = ',result
        return result

# always make the intial call with the second parameter = 1

print factorial(3,1)

# end

The sample run produced is

        factorial of 3
                factorial of 2
                        factorial of 1
                                factorial of 0
                                result = 1
                        result = 1  *  1  =  1
                result = 2  *  1  =  2
        result = 3  *  2  =  6
 6

There are four variables named 'n', one at each level of recursion, that's
why the 'result = ' formula keeps changing. The first parameter is 'n'
(from the line 'factorial of' at the same level of indentation) and the 
second parameter is the result of the lower level of recursion.
Note that at no point are we getting 1*1=2. 

Once you understand how it works, restore the function to its original form.

>and the result is returned. The return value (1) is multiplied by n, which
>is 2, and the result is returned.
>Sorry if I explained my problem oddly. You can see the example in the above
>link, under chapter 5.



--
Mensanator
2 of Clubs   http://members.aol.com/mensanator666/2ofclubs/2ofclubs.htm