# 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

Point a webcam at the screen.

https://i.stack.imgur.com/0DaD5.jpg (or other paintings – Escher?).

Break sections from broccoli.

Draw koch snowflake or Sierpinski gasket.

## 20.3. Word examples

“This sentence is false.”

“The next sentence is true. The previous sentence is false.”

Read this sentence and do what it says twice.

Dialogs from Godel, Escher, Bach

Quining: “yields falsehood when preceded by its quotation” yields falsehood when preceded by its quotation. https://en.wikipedia.org/wiki/Quine%27s_paradox

Russell’s Paradox. https://en.wikipedia.org/wiki/Russell%27s_paradox

Aristotle’s “law of excluded middle”. https://en.wikipedia.org/wiki/Law_of_excluded_middle

## 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\)^{th}element in terms of the \((n-1)\)^{th}element (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:

which suggests this generalization:

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:

which lends itself to a very simple recursive definition:

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.

```
#! /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

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

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

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.

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

```
#! /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.

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