12. Recursion

[status: partially-written]

12.1. Motivation, prerequisites, plan

12.2. Visual examples

12.3. Word examples

  • Read this sentence and do what it says twice.
  • Dialogs from Godel, Escher, Bach

12.4. 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*x & {\rm \; when \; } n = 2 \\ x^n & = x*x^{n-1} & {\rm \; when \; } n > 2 \end{align}

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}

12.5. Programming simple math recursion

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

Listing 12.5.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()

12.5.1. Exercises

  • Write an analogous program that calculates \(n!\) You may use Listing 12.5.1 as a guide.
  • 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 12.5.1 as a guide.

12.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 12.6.1:

Listing 12.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()

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.

12.6.1. Exercises

  • 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.
  • Find a way to intercept the program to draw (in simple ascii art, or with a canvas as shown in Section 14) the intermediate stages of the solution.

12.6.2. Further exploration

  • I should give references to visualizations.

12.7. Should we really use recursion in programming?

We saw in Section 12.6 and we will see again in Section 18 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 simpler algorithm:

def factorial_nonrecursive(n):
    result = 1
    for i in range(n):
        result = result * i
    return result

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