Let's write a function that computes $n!$ using a while loop.
def fact_while(n):
#Invariant (a fact that we make sure doesn't change):
#cur_prod == (i-1)!
cur_prod, i = 1, 1
#Note: 1 = (1-1)!, so cur_prod == (i-1)!
while i != n+1: #Equivalently: if not (i == n+1)
cur_prod *= i
i += 1
#Invariant: cur_prod == (i-1)!
#Here, i == n+1, and since cur_prod = (i-1)!, we can return
#cur_prod == ((n+1)-1)! == n
return cur_prod
We can supply default arguments to functions. Here is a simple example:
def f(a = 2, b = 3):
return a + b
Here, the default value of a is 2, and the default value for b is 3. We can canll f() with no arguments at all, and get 2 + 3 back:
f()
The local variables got assigned their default values of 2 and 3 respectively. We can also supply a but not b:
f(10)
In order to be able to supply b but not a, we need named arguments (explained elsewhere.)
We are now ready to implement the same algorithm as above, but without any while- or for-loops:
def fact_iter(n, cur_prod = 1, i = 1):
'''Return n!
Arguments:
n -- a non-negative int
cur_prod, i -- ints such that cur_prod = (i-1)!
'''
if i == n + 1: #same as not (i != n+1)
return cur_prod
#cur_prod = (i-1)!
#cur_prod <- cur_prod*i, i <- i+1
return fact_iter(n, cur_prod*i ,i+1)
The idea is almost all contained in the docstring: we specify that cur_prod and i must be such that
cur_prod = (i-1)!
By itself, this doesn't mean much -- the docstring is just text, not Python code. But it helps us write the function. If we assume that the function works as long as we call it with cur_prod and i such that cur_prod = (i-1)!, we can perform the recursive leap of faith.
Let's start with the base case. If i == n+1, then out job is done, since cur_prod must equal (i-1) != (n+1-1)! = n!, so we can just return cur_prod.
Otherwise, we can call fact_iter again, and try to push i towards n+1. That's exactly what we do in the recursive call. (Note that we take care to make sure that it's still the case that in the new call, cur_prod = (i-1)!.
Finally, we'd like to be able to call fact_iter(n). We can do that, since we specify the default values of cur_prod = 1 and i = 1. (Note that 1 = (1-0)!.)
Everything from fact_while() has a direct equivalent in fact_iter() and vice-versa. You can hopefully see that we can transform any while-loop into a function that uses recursion instead of while-loops.
Here is what the call tree looks like:
(n, 1*1*2*3*...*n, n+1)
/ \
n! / |
| |
\ |
(n, 1*1*2*3, 4)
/ |
n! / |
| |
\ |
(n, 1*1*2, 3)
/ |
n! / |
| |
\ |
(n, 1*1, 2)
/ |
n! / |
| |
\ |
(n, 1, 1)
/
/
n!
Note that this is different from the call tree for the other recursive factorial function we wrote:
def fact(n):
if n == 0:
return 1
return n*fact(n-1)
In fact(n), computation was performed was going "up" the call tree and going "down" the call tree:
0
/|
1 | |
\|
1
/ .
2/ .
\ .
.
/ .
(n-3)! | .
\ |
n-2
/ |
(n-2)! | |
\ |
|
n-1
/ |
(n-1)! | |
\ |
|
n
/
/
n!
We could express this computation as $n\times(...\times(2\times(1\times(1)))....)$
On the other hand, the computation in fact_iter is still essentially a loop, since we are not decomposing the problem into "smaller" subproblems. It's best expressed as simply $1\times 2\times 3\times ... \times n$.
Even though fact_iter is recursive in form, it really is still an iterative approach.