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):
product = 1
for factor in range(2, n + 1):
product *= factor
return product
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 (somewhat 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 compute 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(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(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 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("am").
We have now our third call to str_len with a_str equal to "am". This returns the value of 1 + str_len("m").
This is our fourth call to str_len_recursive, and then value returne in the else clause is 1 + str_len("").
This is our fifth and final call to str_len. 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, the call whose input was "spam", is 4.
You might have wondered why we'd ever want to give a recursive solution to a problem given that an iterative solutionis always possible. Here's a partial answer: sometimes the recursive solution is easier to find and, once given, more elegant than the iterative solution. The Fibonacci sequence provides a nice example of this.
As I'm sure you recall from the Chapter 3 function set, 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 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
Perhaps you recall that this was tricky to get right back in Chapter 3. Likely you didn't know about the possibility of double assignment (fib, next_fib = next_fib, fib + next_fib) and finally realized that you had to introduce a new variable (perhaps old_a or old_b) to hold a value for later use.
Note that our iterative solution 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, we might say, 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 members - each is the sum of the two members prior to it. We continue until we hit the Base Case.
Here's the code:
def 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 as I'll explain in the next section. 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 the recursive 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 in the function set for the chapter.)
Let's do fib(4). Of course we don't have the base case to begin. Instead, fib(4) becomes fib(3) + fib(2). So if we show the recursive calls made by fib(4) as downward branches in a tree, we have:
fib(4)
/ \
fib(3) fib(2)
(Here's an odd little fact about computer science. When we have structures such as the one above, we call them trees, and those trees always extend downward. Yes, I know that real trees grow up. ) The left call - fib(3) - is not the base case, so it gives to two additional calls - fib(2) and fib(1). The right call - fib(2) - is the base case and so simply returns a 1. Thus we have:
fib(4)
/ \
fib(3) fib(2)
/ \
fib(2) fib(1)
With this, we have hit the base case along all branches. The fib(2) and fib(1) under fib(3) both send back a 1, so fib(3) evaluates to 1 + 1 = 2. The fib(2) on the second level is 1, so fib(4) evaluates to 2 + 1 = 3.
Note that Python always evaluates an expression from left to right (unless parentheses tell it otherwise). This means that the level two fib(3) is evaluated before Python attempts to evaluate the level two fib(2). Moreover, the fib(2) on level 3 evaluates before the fib(1). So the order of evaluation follows down the lefthand side of our tree until we bottom out at fib(2), then goes to the fib(1) on level three, etc. If we were to name the calls to fib as you see below, the order of calls would be a-b-d-e-c.
a. fib(4)
/ \
b. fib(3) c. fib(2)
/ \
d. fib(2) e. fib(1)
Above I mentioned a certain inefficiency in the recursive version of fib. Consider fib(5). This branches into fib(4) and fib(3) on level 2; and then that fib(4) branches into fib(3) and fib(2) on level three. This is shown in the partial tree below.
fib(5)
/ \
fib(4) fib(3)
/ \
fib(3) fib(2)
So we now have two occurrences of fib(3) - one on level two and one on level three. Python will evaluate each of those independently. It would be better of course to evaluate fib(3) only once, store that value and then later retrieve it as necessary. You'll learn how to do this in the function 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.
The idea of course is that we'll first test for divisibility by 2, then by 3, etc. We'll go up to n. When we find a factor, we'll return it.
The iterative implementation is rather obvious I think. We must fire up a for loop whose loop variable will hold potential factors. Here it is:
def first_factor(n):
for f in range(2, n + 1):
if n % f == 0:
return f
Now let's give a recursive solution. That means we'll need a base case and a recursive case. What should the base case be? Test whether our number is divisible by a potential factor, and if so, return that factor. What's the recursive case? Test for divisibility by the next potential factor, which means of course another call to the function.
We do have an issue here. When the function recursively calls itself, how will it send the next potential factor? The solution is to have a second parameter. The first parameter is of course the number whose first factor we wish to find. The second parameter will be the potential factor. (We'll call these n and f as above.)
But this raises another problem. When we first call the function, we should send only the number whose first factor we wish to find. (That's the n.) But the function will have two parameters as we said. The solution is to set a default value for the second parameter. When we first call the function (a call that occurs outside the function), we won't send a second value. Instead it will default to 2; and when later the function recursively calls itself, we will send a value for that second parameter. Indeed we'll send a value one greater than the current value.
Here's the code:
def first_factor(n, f = 2):
# If we send only one value, f will default to 2.
if n % f == 0:
return f
else:
return ff_recursive(n, f + 1)
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.)