Previously, we examined how to write subroutines in Python using additional functions. Each function can have one or more parameters, variables representing data that is passed to the function from somewhere else in the program. Each function can also have a return statement that returns a computed result back to the instruction that called this function. For example, here is a simple Python program from lab 4 that illustrates the calling and returning process.
def main():
x = f_to_c(32)
print x
y = 212
print f_to_c(y)
def f_to_c(tempF):
tempC = (5.0/9.0) * (tempF - 32.0)
return tempC
main()
In the example above, the first instruction of main calls the f_to_c function with the value 32. The function sets its parameter tempF to 32 and then performs its computation. Once it hits the return instruction, it jumps back to main where the function call was made, returning the computed value of tempC (which should be 0). The returned value is assigned to the variable x and execution continues in the main function. When we get to the 2nd function call to f_to_c, the value of y (212) is passed to the f_to_c function. The function sets its parameter tempF to 212 this time and then performs its computation, returning its result (which should be 100) back to where the function was called in main, causing the value to be printed.
A recursive function is simply a function that calls itself. In class, we saw how to define the factorial function recursively:
0! = 1
n! = n(n-1)!, n > 0
Let's see how to write this in Python:
def main():
# Computing 8 factorial recursively
print factorial(8)
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
main()
In this example, the value 8 is passed to the factorial function, so n is 8. Since n is not 0, this function will return 8 * factorial(7). To compute this, this function is called again, this time with n = 7. When that result is returned (should be 5040), we can then compute 8 * factorial(7) = 8 * 5040 = 40320 which is returned back to main. The computation of factorial(7) is performed in a similar manner, except when its answer is returned, it is returned back to the factorial function call in factorial itself rather than main.
Tracing the calls, we get something like this:
factorial(8) = 8 * factorial(7)
= 8 * (7 * factorial(6))
= 8 * (7 * (6 * factorial(5)))
= 8 * (7 * (6 * (5 * factorial(4))))
= 8 * (7 * (6 * (5 * (4 * factorial(3)))))
= 8 * (7 * (6 * (5 * (4 * (3 * factorial(2))))))
= 8 * (7 * (6 * (5 * (4 * (3 * (2 * factorial(1)))))))
= 8 * (7 * (6 * (5 * (4 * (3 * (2 * (1 * factorial(0))))))))
= 8 * (7 * (6 * (5 * (4 * (3 * (2 * (1 * 1)))))))
= 8 * (7 * (6 * (5 * (4 * (3 * (2 * 1))))))
= 8 * (7 * (6 * (5 * (4 * (3 * 2)))))
= 8 * (7 * (6 * (5 * (4 * 6))))
= 8 * (7 * (6 * (5 * 24)))
= 8 * (7 * (6 * 120))
= 8 * (7 * 720)
= 8 * 5040
= 40320
We could also write the program this way, which is equivalent assuming n is always greater than or equal to 0:
def main():
# Computing 8 factorial recursively
print factorial(8)
def factorial(n):
if n > 0:
return n * factorial(n-1)
else:
return 1
main()
The nth Fibonacci number is given recursively by the following formula:
fib(1) = 1
fib(2) = 1
fib(n) = fib(n-1) + fib(n-2), n > 2
Here is how we can program this in Python:
def main():
# compute the 6th Fibonacci number recursively
print fib(6)
def fib(n):
if n <= 2:
return 1
else:
x = fib(n-1)
y = fib(n-2)
return x+y
# We could have also written: return fib(n-1) + fib(n-2)
main()
Note that each recursive function has a base case (or stopping case) that is not recursive. In this case, if n is less than or equal to 2, then computing the nth Fibonacci number is easy; it's just 1. Otherwise, we compute the n-1st Fibonacci number recursively, storing its value in x, then we compute the n-2nd Fibonacci number recursively, storing its value in y, and finally we return the sum of x and y as the answer. Computing the n-1st Fibonacci number and n-2nd Fibonacci number are done in a similar, recursive manner.
Here is a trace of the computation done in the program above.
fib(6) = fib(5) + fib(4)
= (fib(4) + fib(3)) + fib(4)
= ((fib(3) + fib(2)) + fib(3)) + fib(4)
= (((fib(2) + fib(1)) + fib(2)) + fib(3)) + fib(4)
= (((1 + fib(1)) + fib(2)) + fib(3)) + fib(4)
= (((1 + 1) + fib(2)) + fib(3)) + fib(4)
= ((2 + fib(2)) + fib(3)) + fib(4)
= ((2 + 1) + fib(3)) + fib(4)
= ((2 + 1) + fib(3)) + fib(4)
= (3 + fib(3)) + fib(4)
= (3 + (fib(2) + fib(1))) + fib(4)
= (3 + (1 + fib(1))) + fib(4)
= (3 + (1 + 1)) + fib(4)
= (3 + 2) + fib(4)
= 5 + fib(4)
= 5 + (fib(3) + fib(2))
= 5 + ((fib(2) + fib(1)) + fib(2))
= 5 + ((1 + fib(1)) + fib(2))
= 5 + ((1 + 1) + fib(2))
= 5 + (2 + fib(2))
= 5 + (2 + 1)
= 5 + 3
= 8
It's usually easier to think about the high-level recursive computation than all of this detail, but this detail shows that our recursive logic works. At the high-level, the nth Fibonacci number is the sum of the previous two Fibonacci numbers (the n-1st and n-2nd Fibonacci numbers). This is what the function is computing overall. The computer keeps track of all of the recursive sub-problems that are generated in the computation.
As one more example, let's look at the Towers of Hanoi puzzle. There are three pegs, labeled A, B, and C. Peg A has n disks in size order, smallest on top to largest on bottom. The goal is to move all disks from the starting peg (A) to the ending peg (C) using the extra peg (B) as necessary so that we move one disk at a time, and we never place a larger disk on top of a smaller disk. In class, we saw that there is a recursive solution to this problem:
1. Move the top n-1 disks from the starting peg to the extra peg recursively.
2. Move one disc from the starting peg to the ending peg.
3. Move the top n-1 disks from the extra peg to the ending peg recursively.
Here's how to translate this to Python:
def main():
# Solve the Towers of Hanoi puzzle for 5 disks
# from peg A to peg C using extra peg B
towers(5, "A", "B", "C")
def towers(numdisks, startpeg, extrapeg, endpeg):
if numdisks =- 1:
print "Move a disk from", startpeg, "to", endpeg
else:
towers(numdisks-1, startpeg, endpeg, extrapeg)
print "Move a disk from", startpeg, "to", endpeg
towers(numdisks-1, extrapeg, startpeg, endpeg)
main()
In this case, the first recursive call simulates algorithm step 1: Move all but one disk from the starting peg to the extra peg using the ending peg as necessary. (Whichever peg is used as the "extra" is always the middle of the three pegs listed.) The second recursive call simulates algorithm step 3: Move all but one disk from the extra peg to the ending peg using the starting peg as necessary.
The stopping cases are when numDisks = 1. When there is only one disk, there is no need for recursion since this is a simple problem to solve so there is only one output statement. Here is the amazing output, which works!
Move top disk from A to C Move top disk from A to B Move top disk from C to B Move top disk from A to C Move top disk from B to A Move top disk from B to C Move top disk from A to C Move top disk from A to B Move top disk from C to B Move top disk from C to A Move top disk from B to A Move top disk from C to B Move top disk from A to C Move top disk from A to B Move top disk from C to B Move top disk from A to C Move top disk from B to A Move top disk from B to C Move top disk from A to C Move top disk from B to A Move top disk from C to B Move top disk from C to A Move top disk from B to A Move top disk from B to C Move top disk from A to C Move top disk from A to B Move top disk from C to B Move top disk from A to C Move top disk from B to A Move top disk from B to C Move top disk from A to C