Chp 8: Recursion

Back To Logic

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.

Factorial Iterative

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

Recursive Factorial

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

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

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 Three Laws of Recursion

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

Code for Recursive Factorial

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.

String Length

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:

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

The Fibonacci Sequence

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 has, however, slow. In the function set for the chapter, I'll present a way to make it quite radically faster.)

First Factor

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.

Stack Overflow

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