Recursion

[Jakle]

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,
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.

 

[Jeff Epler]

"Explanation From the Book Begins Here"++++++++++++++++++

"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.

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

 

[Mensanator]

Subject: Recursion

From: "Jakle" (e-mail address removed)
Date: 9/28/2003 7:48 PM Central Standard Time
Message-id: <[email protected]>

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"++++++++++++++++++

making any more recusive calls.
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.

 

[Jakle]

That's great. You guys have no idea how much that helped. And I love that
debugging tip. For some reason I thought that the 2 statements after the
recursion call, "result = n * recurse" and "return result" weren't executed
till n == 0. If you can't tell, I'm new to this. But I'm dedicated. I want
to thank you guys soooo much for taking the time to help out. I'm sitting
here jumping for joy because it's alittle more clear I can't wait till
it's me helping out in the future. I'm still alittle confused about why the
flow of execution goes down then up again, but I now have the tools to look
at it in a better light. Time to get my nose in the book again, then write
another function using the same logic in order to make sure I understand.
Thanks again

 

[Dennis Lee Bieber]

Jakle fed this fish to the penguins on Sunday 28 September 2003 08:28
pm:

That's great. You guys have no idea how much that helped. And I love
that debugging tip. For some reason I thought that the 2 statements
after the recursion call, "result = n * recurse" and "return result"
weren't executed till n == 0. If you can't tell, I'm new to this. But

They aren't executed until the "first" return from factorial() --
which only happens when n /is/ 0... At that point, the recursive calls
start returning and executing the statements under the factorial() call.

To reduce indentation, I'll use just 3!

Factorial(3)
n has value 3
n is NOT 0 so
res= Factorial(n-1)
Factorial(2)
n has value 2
n is not 0 so
res= Factorial(n-1)
Factorial(1)
n has value 1
n is not 0 so
res= Factorial(n-1)
Factorial(0)
n has value 0
n IS 0 so
return 1
res is now 1
return n * res (1 * 1)
res is now 1
return n * res (2 * 1)
res is now 2
return n * res (3 * 2)

Factorial(3) returns value 6


Each time Factorial makes a recursive call to itself (I know, that is
redundant phrasing) it creates a new "block" of local variables, the
variables in the previous block can not be seen. When a return
statement is encountered, the block of locals is deleted, leaving the
return value visible to the calling block.


--

 

[Tim Rowe]

Each time Factorial makes a recursive call to itself (I know, that is
redundant phrasing) it creates a new "block" of local variables, the
variables in the previous block can not be seen. When a return
statement is encountered, the block of locals is deleted, leaving the
return value visible to the calling block.

I can't remember if the tutorial points it out, but for jakle's sake I
should mention that this means that the recursive implementation of
factorial uses a lot more memory than a simple loop implementation
(and is probably a lot slower too). Factorials are useful for
teaching recursion, but it's not usually the best way to implement a
factorial function [1]. There are some applications that are not so
easy to implement as a loop, though (traversing a tree structure is
usually one of the first that nascent programmers encounter) and then
recursion starts being actually useful.

[1] Some languages depend on recursion much more than Python does, but
they will typically spot cases that can be converted to simple loops
and do that behind the scenes for efficiency.

 

[Bengt Richter]

Jakle fed this fish to the penguins on Sunday 28 September 2003 08:28
pm:


They aren't executed until the "first" return from factorial() --
which only happens when n /is/ 0... At that point, the recursive calls
start returning and executing the statements under the factorial() call.

To reduce indentation, I'll use just 3!

Factorial(3)
n has value 3
n is NOT 0 so
res= Factorial(n-1)
Factorial(2)
n has value 2
n is not 0 so
res= Factorial(n-1)
Factorial(1)
n has value 1
n is not 0 so
res= Factorial(n-1)
Factorial(0)
n has value 0
n IS 0 so
return 1
res is now 1
return n * res (1 * 1)
res is now 1
return n * res (2 * 1)
res is now 2
return n * res (3 * 2)

Factorial(3) returns value 6


Each time Factorial makes a recursive call to itself (I know, that is
redundant phrasing) it creates a new "block" of local variables, the
variables in the previous block can not be seen. When a return
statement is encountered, the block of locals is deleted, leaving the
return value visible to the calling block.

You didn't type that out by hand, did you? ;-)

====< showfact.py >=======================================
def showfact(n, indent=0):
sind = len(' res= Factorial(')*' '*indent
print '%sFactorial(%s)'%(sind, n)
print '%s n has value %s' %(sind, n)
print '%s n %s 0 so'%(sind, ('is not', 'IS')[n==0])
if n==0:
print '%s return 1' %sind
return 1
print '%s res= Factorial(n-1)'% sind
res = showfact(n-1, indent+1)
print '%s res is now %s' %(sind, res)
print '%s return n * res (%s * %s)' % (sind, n, res)
return n * res

def test(n):
print '\nFactorial(%s) returns value %s' % (n, showfact(n))

if __name__ == '__main__':
import sys
try: test(int(sys.argv[1]))
except: print 'Usage: showfact.py <integer arg>'
==========================================================

[ 8:16] C:\pywk\clp>showfact.py
Usage: showfact.py <integer arg>

[ 8:16] C:\pywk\clp>showfact.py 2
Factorial(2)
n has value 2
n is not 0 so
res= Factorial(n-1)
Factorial(1)
n has value 1
n is not 0 so
res= Factorial(n-1)
Factorial(0)
n has value 0
n IS 0 so
return 1
res is now 1
return n * res (1 * 1)
res is now 1
return n * res (2 * 1)

Factorial(2) returns value 2


Regards,
Bengt Richter

 

[Dennis Lee Bieber]

Bengt Richter fed this fish to the penguins on Monday 29 September 2003
08:07 am:

You didn't type that out by hand, did you? ;-)

Yes, I did... It was bedtime for me, and I was designing the "output"
while typing it... <G>

--

 

[Christos TZOTZIOY Georgiou]

Yes, I did... It was bedtime for me, and I was designing the "output"
while typing it... <G>

I am not sure if typing the text was 'harder' (that was Dennis), or
typing the program to produce the same text (that was Bengt, but anybody
would have guessed, right?)

PS I believe Bengt is one of the key persons in the newsgroup; somebody
tempts him enough, and his keyboard gets fire. It seems like 10Kloc are
but a piece of cake for Bengt, just a pass-time between lunch and
dinner... Maybe he *is* a Motie, after all.

Or perhaps I should someday post anonymously: "Hi, I'm a python newbie
and I want to write the perfect operating system, stable, easy and
free", and then try to lure Bengt. Hm... Hope Billy G. doesn't read
the newsgroup.