20. Recursion

[status: partially-written]

20.1. Motivation, prerequisites, plan

Recursion comes up in many very important computer algorithms, to the point where it’s reasonable to say that it is an essential tool for most programmers. When an algorithm can be expressed recursively it almost feels like we’re cheating in how we implement it: we get this complex result from two very simple statements!

The only prerequisite for this chapter is the 10-hour Serious Computer Programming for Youth course.

Our plan is to first try to get a feeling for recursion with some visual examples. Then we state the two key parts of a recursive definition (and hence of a recursive algorithm): the recurrence relation and the initial condition. With this under our belts we take on examples from math and other areas.

20.2. Visual examples

20.3. Word examples

20.4. Components of a recursive definition

A recursive series is defined by two components:

Recurrence relation

Specifies what the next element of a sequence is, based on the previous one. If we are talking about a numbered sequence, then this means defining the \(n\)thelement in terms of the \((n-1)\)thelement (and maybe \(n-2\) and earlier elements as well).

Initial condition

You can’t go on applying the recurrence relation forever, so at some point you have to stop. We do this by specifying an initial condition. For example we can set an element to have a clear value when \(n = 0\) or \(n = 1\).

Let us look at some examples of recursive definitions in simple math.

20.4.1. Simple math

Define power with recursion:

\[3^5 = 3*3^4 = 3*(3*3^3) = 3*(3*(3*3^2)) = 3*(3*(3*(3*3)))\]

which suggests this generalization:

\begin{align} x^n & = 1 & {\rm \; when \; } n = 0 \\ x^n & = x & {\rm \; when \; } n = 1 \\ x^n & = x \times x & {\rm \; when \; } n = 2 \\ x^n & = x \times x^{n-1} & {\rm \; when \; } n > 2 \end{align}

In this you can see that \(x^n\) is defined recursively with recurrence relation \(x^n = x \times x^{n-1}\) and initial condition \(x^0 = 1\).

Factorials are defined like this:

\begin{align} 2! &= 2 \times 1 = 2 \\ 3! &= 3 \times 2 \times 1 = 6 \\ &\dots \\ n! &= n \times (n-1) \times (n-2) \dots \times 2 \times 1 \end{align}

which lends itself to a very simple recursive definition:

\begin{align} n! & = 1 & {\rm \; when \; } & n = 1 \\ n! & = n \times (n-1)! & {\rm \; when \; } & n > 1 \end{align}

This is very easily implemented in Python:

def factorial_recursive(n):
    if n == 1:
        return 1
    else:
        return n * factorial_recursive(n-1)

20.4.2. Programming simple math recursion

In Listing 20.4.1: you can see a simple program which calculates \(x^n\). Go ahead and try it out to calculate powers.

Listing 20.4.1 Program which calculates powers using recursion.
#! /usr/bin/env python3

"""
A demonstration of how to calculate x^n using recursion.
"""

def main():
    x = float(input('give x: '))
    n = float(input('give n: '))
    result = power(x, n)
    print('%g^%d is: %g' % (x, n, result))

def power(x, n):
    if n == 0:
        return 1
    else:
        return x * power(x, n-1)

main()

20.4.2.1. Exercises

Exercise 20.1

Write an analogous program that calculates \(n!\) You may use Listing 20.4.1 as a guide.

Exercise 20.2

The fibonacci numbers, which appear in many beautiful manifestations of nature, are defined recursively:

\begin{align} fib(n) & = 1 & {\rm \; when \; } & n = 0\ or\ n = 1 \\ fib(n) & = fib(n-1) + fib(n-2) & {\rm \; when \; } & n > 1 \end{align}

Now write a program that calculates \(fib(n)\). You may once again use Listing 20.4.1 as a guide.

20.4.3. Recursion with data structures

The list is a very important data structure, and it often lends itself to surprisingly simple recursive algorithms.

A simple example is to reverse a list in python. A list with just one element l = ['dude'] will have an obvious reverse, which is just itself. And if you have reversed a list with \(n\) elements, then to do a list with one more element is easy. Start out with:

l = [2.5, 17, 'dude']

and imagine that you have reversed all but the last element:

# this is not ready to run!
l = [2.5, 17, 'dude']
# we have somehow reversed the first two elements
l_reversed_without_last = [17, 2.5]
# now we complete the task by putting the last element at the start
l_reversed = [l[-1]] + l_reversed_without_last

From this pseudo-code (that will absolutely not work!) you can get an idea for a recursive algorithm:

Recurrence relation

reverse(list) = [last_element] + reverse(list_without_last_element)

Initial condition

reverse(list_with_just_one_element) = that_list_with_just_one_element

Remembering that in Python you can get the last element of a list l with l[-1], and the rest of the list with l[:-1], we can write an inline function to do this:

def reverse_list_recursive(l):
    if len(l) == 1:
        return l
    else:
        return reverse_list_recursive(l[1:]) + [l[0]]

# now run it with:
reverse_list_recursive([2.5, 17, 'dude'])

# do some numbers with:
reverse_list_recursive(list(range(20)))

# now do a much longer list
reverse_list_recursive(list(range(200)))

20.5. Visualizing what the recursion is doing

We clearly agree that the magic of recursion works, but it can be frustrating to not have an intuition of the intermediate steps. Let us modify the function so that it prints how it’s putting together the pieces of the lists in the intermediate stages.

Listing 20.5.1 Reverse a list with a recursive algorithm, breaking it into l[0] and l[1:]. This prints some information on the calls to the recursive algorithm.
def reverse_list_recursive_pivot_0(l):
    """Reverse the list l using a recursive algorithm based on breaking it
    down into l[0] and l[1:]
    """
    if len(l) == 1:
        return l
    else:
        # print information on how the recursion relation is going
        print(f'  RECURSION: reverse({l[1:]}) + {[l[0]]}')
        return reverse_list_recursive_pivot_0(l[1:]) + [l[0]]


# now try it out with a few examples of lists of numbers
for listlen in range(6):
    print('------- reversing list', list(range(listlen+1)), '------')
    result = reverse_list_recursive_pivot_0(list(range(listlen+1)))
    print('RESULT:', result)
    print()

20.6. Towers of Hanoi

The Towers of Hanoi is a puzzle in which you have three pegs and a pile of discs on one of them. The discs always must be piled with bigger discs below smaller discs. The goal is to move the discs from their initial peg to another peg, using the extra peg if you need to.

Listing 20.6.1 Recursive solution to the Towers of Hanoi game
#! /usr/bin/env python3

"""
A demonstration of how to solve the Towers of Hanoi game using
recursion
"""


def main():
    n_disks = int(input('how many discs? '))
    move_tower(n_disks, 'A', 'B', 'C')

def move_tower(height, from_pole, to_pole, interim_pole):
    if height > 0:
        move_tower(height-1, from_pole, interim_pole, to_pole)
        move_disk(from_pole, to_pole)
        move_tower(height-1, interim_pole, to_pole, from_pole)

def move_disk(from_pole, to_pole):
    print('moving disk from', from_pole, 'to', to_pole)

main()

Now look at the program in Listing 20.6.1. This is a surprisingly short program because the information about the state of the pegs and discs is not in any of the program variables! It’s all stored in function stack as part of recursive calls.

Exercise 20.1

Count how many disc movements are made in total to solve the puzzle, and plot that as a function of how many discs you picked for that run.

Exercise 20.2

Find a way to intercept the program to draw (in simple ascii art, or with a canvas as shown in Section 24) the intermediate stages of the solution.

20.7. Should we really use recursion in programming?

We saw in Section 20.6 and we will see again in Section 29 that some problems are expressed very simply using recursive algorithms. Should we always look for recursive solutions?

The trade-offs come when you are dealing with very high numbers of recursive calls. If you imagine yourself reciting this in your head:

Seven factorial is seven times six factorial which is seven times six times five factorial which is … which is seven times six times five times four times three times two times one times zero factorial; that last one is one so I can now finally multiply them all together: seven times six times five times four times three times two times one times one which is fivethousand and fourty.

you can see that you have to keep a lot of stuff in mind. The nonrecursive algorithm:

def factorial_nonrecursive(n):
    assert(n > 0)
    result = 1
    for i in range(1, n+1):
        result = result * i
    return result

never juggles more than two numbers at once in its memory.

Another problem with recursive list-processing algorithms is that they often have to shuffle around copies of the list data. The list reversing algorithm in Listing 20.5.1 shows how list slices like l[1:] cause most of the list data to be copied in memory.