Think Functional! began with a bit of logic. We learned about variables. And functions. And iteration and selection. It then turned to data types. We learned about strings, files, lists, tuples, dictionaries and sets. (Of course the two weren't neatly separated. We do logic on data. But at times the focus was logic and at others it was data.)
We now return to logic. Indeed we return to a study of functions. We'll find that, if we're careful about it, we can have a function call itself. That's a delightful idea, isn't it? It's a bit as if, in the middle of a recipe, the recipe tells us to go make the recipe! How can we get a dish that way? You'll see.
We've already met the factorial function. Here was our first definition:
If n is a positive integer, then n! is the product of all positive integers from 1 to n.
So 1! = 1, 2! = 1 * 2, 3! = 1 * 2 * 3, etc.
This suggests (demands?) an iterative algorithm:
def factorial(n):
f = 1
for i in range(2, n + 1):
f *= i
return f
A few test runs:
>>> factorial(3)
6
>>> factorial(6)
720
>>> factorial(12)
479001600
We may define the factorial function in a second, quite different way. Assume as before that n is a positive integer.
Clause One: If n = 1, then n! = 1.
Clause Two: If n > 1, then n! = n * (n - 1)!.
Extraordinary! The definition makes use of the term it defines! (The recipe says to make the recipe.) That's illegal, right? Don't we get ourselves into a nasty circle?
No, it's not illegal. It does move us around in a circle. But not forever. All is well in the end. Let's apply the definition to compute 4!.
Clause 2: 4! = 4 * 3! Think of this as a promise, the promise to compute 4! once the value of 3! is delivered. So let's attempt to deliver it!
Clause 2: 3! = 3 * 2!. Another promise! Promises on top of promises! Now we need 2!.
Clause 2: 2! = 2 * 1!. A third promise! When will the promises end? Now actually.
Clause 1: 1! = 1. Now we can keep a promise! Send this 1 back to Step 3.
2! = 2 * 1! = 2 * 1 = 2. Promise kept! Now we can keep another. Back to Step 2 we go.
3! = 3 * 2! = 3 * 2 = 6. Second promise kept! Now we can keep our first promise and finish the computation. Back to Step 1 we go.
4! = 4 * 3! = 4 * 6 = 24. All promises kept! Finished!
Let's reflect on what just happened. Yes, we did circle a bit. Clause 2 first. Back to Clause 2. Back again to Clause 2. But that circle was not infinite. Each time we circled back around, we got closer to Clause 1; and when Clause 1 was finally reached, we circled no more. Clause 1 delivered not a promise but a value.
If you want a picture, think not of a circle but of a spiral. Each call to Clause 2 takes us around and also down. Down towards Clause 1. When we reach Clause 1, we circle no more.
Let's have terms for the two sorts of case. Call them the Base Case and the Recursive Case. The Recursive Case asks us to evaluate the function again. The Base Case does not; instead it returns a value.
The structure of the recursive factorial definition is universal. It's found in all recursive definitions. That structure is captured in the (pompously named) "Three Laws of Recursion".
A recursive definition has both a Base Case and a Recursive Case. The latter calls the function again. The former does not.
Each successive call to the Recursive Case takes us closer to the Base Case.
When the Base Case is reached, a value is returned; and that return then initiates a sequence of computations - promises kept - that results in a value returned to the first function call.
The recursive definition of the factorial function given above becomes Python quite easily.
def factorial(n):
if n == 1:
return 1 # The Base Case
else:
return n * factorial(n - 1) # The Recursive Case
Beware the beginner's mistake (of which I've been guilt many times). Both the Base and the Recursive Case can't simply name a value. Each must return a value.
So, we can implement the factorial function both iteratively and recursively. This isn't uncommon. Indeed any iterative algorithm can be made recursive if we wish. I'll show you a few examples. In each, I'll first give an iterative and then a recursive algorithm.
Iterative string length:
def str_len_iterative(a_str):
count = 0
for char in a_str:
count += 1
return count
How do we implement str_len recursively? Here's the basic idea:
The length of a string is 0 if the string is empty.
Otherwise the length is 1 plus the length of the string minus its first character.
In code:
def str_len_recursive(a_str):
if a_str == '': # The Base Case
return 0
else:
return 1 + str_len_recursive(a_str[1:])
Perhaps we should pause for a moment and trace the recursive algorithm by hand. Let's say that we send "spam" to str_len_recursive.
a_str isn't the empty string. So we do the else clause, which will return 1 + str_len_recursive("pam").
Thus we call str_len_recursive again; and this time, a_str has the value "pam". "pam" isn't the empty string, so we skip to the else clause and return 1 + str_len_recursive("am").
We have now our third call to str_len_recursive with a_str equal to "am". This returns the value of 1 + str_len_recursive("m").
This is our fourth call to str_len_recursive, and then value returne in the else clause is 1 + str_len_recursive("").
This is our fifth and final call to str_len_recursive. a_str now has the value "", and so we execute the if clause. The value returned is 0.
The 0 is passed back to Step 4, which then has the value 1 + 0 = 1.
That 1 is passed back to step 3, which then has the value 1 + 1 = 2.
That 2 is passed back to step 2, which now has the value 1 + 2 = 3.
Finally that 3 is passed back to Step 1, which now has the value 1 + 3 = 4.
So then the value of the initial call to str_len_recursive, the call whose input was "spam", is 4.
The Fibonacci Sequence begins with a 1 and a second 1. Every member thereafter is the sum of the previous two. Thus the third member is 1 + 1 = 2, the fourth 1 + 2 = 3, the fifth 2 + 3 = 5. Etc. The function below returns the nth member of the Fibonacci Sequence. The algorithm is iterative.
def iter_fib(n):
if n == 1 or n == 2:
return 1
else:
fib, next_fib = 1, 1
for i in range(n - 2): # Compute from the 3rd member on. Thus n - 2.
fib, next_fib = next_fib, fib + next_fib
return next_fib
This is a forwards calculation. We begin with the first two members and calculate the next. We continue to calculate the next until we reach the nth.
The recursive alternative is a backwards calculation. We say first that if n is greater than two, the nth member of the Fibonacci Sequence is the sum of members n - 1 and n - 2. We say the same about those two prior member - each is the sum of the two members prior to it. We continue until we hit the Base Case.
Here's the code:
def recur_fib(n):
if n == 1 or n == 2:
return 1
else:
return fib(n - 1) + fib(n - 2)
Of the two, the recursive function is quite obviously more elegant - it exactly mirrors the usual definition of the Fibonacci sequence. (It has, however, slow. In the function set for the chapter, I'll present a way to make it quite radically faster.)
I think it might be helpful to fully trace a call to recur_fib. It can help us understand recursion (and I suspect you still feel a bit shaky on that if this is your first encounter with it), and it can make clear just why the recursive implementation, as given, is really very inefficient. (I don't mean for you to draw the conclusion that recursion is always inefficient. That just isn't true. Sometimes it is, sometimes it isn't. And when it is, it can often be sped up quite radically, as you will do with fib in the exercise set.)
Next we'll write a function that takes a positive integer 2 or greater and returns the smallest of its factors that's greater than 1. This will be useful to you later.
First the iterative variant:
def ff_iterative(n):
for f in range(2, n + 1):
if n % f == 0:
return f
Now the recursive:
def ff_recursive(n, f = 2):
# Send only one value. f will default to 2.
if n % f == 0:
return f
else:
return ff_recursive(n, f + 1)
(Note that I here made use of a default value for the parameter f. I do hope you recall how that works. We need not send a value for f when we call the function; and if we don't, it gets the default value of 2. But if we do send a value for f, the default of 2 will not be used.)
I feel naughty about this one. The recursive algorithm seems contrived. It certainly is. Contrived to emulate iteration. I introduced a second parameter - the f above, whose value defaults to 2 - that acts very much as a loop variable. But I did wish to make a point, the point that any iteration can be emulated recursively. Should it? No, I don't think it should. (Sorry Haskellers.) Iteration is often the natural solution. But if we wished, we could do away with iteration.
Remember the metaphor of promises. Each recursive call is a promise made.
Of course those promises must be remembered for later. They must be stored away. Somewhere. We call the storehouse of promises "the stack".
The stack isn't infinite. It can hold only so many promises. If we fill it up, we will get an error. The infamous stack overflow error. (My Python actually said "maximum recursion depth exceeded". But that means "stack overflow". I like "stack overflow". I'll use "stack overflow".) Here's an example:
def broken_factorial(n):
# Oh no! Where's the Base Case?
return n * broken_factorial(n - 1)
We don't have a Base Case. It's all recursion, and the stack doth finally overflow. (I actually snuck in a print(n) before the recursive call. The final value printed when I called broken_factorial with 0 was -972. So my stack was 973 deep. It held 973 promises. I find that quite brave. I'd complain long before someone made that many chained promises to me. I think I'd probably throw my hands up at 3.)