Unit 2 — Recursive Functions

Lesson 1 — Reading a recursive definition

A definition is recursive when it uses itself. Think of a set of nesting dolls: to open the big doll you open it and find a smaller doll, which you open in the same way, until you reach the tiny doll that does not open.

A recursive function has two kinds of rules:

• a recursive case, which gives the answer in terms of the same function on a different, usually smaller input, such as f(x - 3) + x;

• a base case, which gives the answer directly, with no call to the function, such as 2 * x - 5.

The base case is the tiny doll. Without it the calls would never stop.

The cases notation

ACSL writes a recursive function as a list of rows inside one big bracket. Each row is a value, then the condition under which that row is used.

f(x) = { f(x - 2) + 1      if x > 3
       { x                 if x <= 3

Read it like this: "to find f(x), look down the rows for the one whose condition is true for your x, and work out that row's value." The conditions never overlap, so exactly one row fits each x. A last row may say otherwise, which means "when no row above fits".

A few notes on how the definitions in this book are written:

For example, floor(7 / 2) is 3, 17 mod 5 is 2, and abs(-4) is 4.

The call-table method

To find f(8) for the definition above, work in two passes.

Pass 1, going down. Start with f(8). Find the row that fits, and write what it turns into. Keep going until you reach a base case, which is a plain number.

Pass 2, coming back up. Now fill in the values from the bottom of the table to the top.

• f(2) = 2

• f(4) = f(2) + 1 = 3

• f(6) = f(4) + 1 = 4

• f(8) = f(6) + 1 = 5

So f(8) = 5.

Solving the opening problem

Now try f(20) from the top of the unit yourself, before you read on. Make the table, then fill in the values.

Coming back up: f(8) = 11, f(11) = 11 + 11 = 22, f(14) = 22 + 14 = 36, f(17) = 36 + 17 = 53, and f(20) = 53 + 20 = 73.

Checking pass 1 with a program

Pass 1 only has to follow the arguments 20, 17, 14, 11, 8 until the base case. A short loop can list them for you. It subtracts 3 while x > 10, just like the first row of the definition, and keeps the numbers in a string.

Run it from this unit's folder:

python assets/l1.py < assets/l1/1.in

It prints 20 17 14 11 8, the first column of your call table.

Conditions that use mod, floor and abs

ACSL conditions are often more than x > 10. Here the row depends on whether x is odd or even:

g(x) = { g(x - 1) + x          if x > 0 and x mod 2 = 1
       { g(floor(x / 2)) + 1   if x > 0 and x mod 2 = 0
       { 0                     if x = 0

Find g(13).

Coming back up: g(0) = 0, g(1) = 1, g(2) = 2, g(3) = 5, g(6) = 6, g(12) = 7, and g(13) = 20.

With abs, the argument can even turn negative on the way down:

h(x) = { h(abs(x) - 5) + 1     if abs(x) > 3
       { x                     if abs(x) <= 3

For h(9): abs(9) = 9 > 3, so h(9) = h(4) + 1. Then abs(4) = 4 > 3, so h(4) = h(-1) + 1. Now abs(-1) = 1 <= 3, so h(-1) = -1, a base case. Coming back up: h(4) = 0 and h(9) = 1.

Lesson 2 — More kinds of recursive functions

ACSL asks about a few different shapes of recursive function. The call-table method works for all of them; only the bookkeeping changes.

Two variables

A function can take two inputs. Each row changes one or both of them.

f(x, y) = { f(x - 2, y + 1) + y     if x > y
          { y - x                   if x <= y

Find f(9, 1).

Coming back up: f(5, 3) = 1 + 3 = 4, f(7, 2) = 4 + 2 = 6, and f(9, 1) = 6 + 1 = 7.

Multiple recursion

In multiple recursion, one row calls the function more than once.

f(x) = { f(x - 1) + 2 * f(x - 2)    if x >= 2
       { x                          if x <= 1

To find f(4) you need f(3) and f(2). Each of those needs two more calls, so the calls branch out like a tree:

                 f(4)
              /        \
          f(3)          f(2)
         /    \        /    \
      f(2)    f(1)   f(1)   f(0)
     /    \
  f(1)    f(0)

The tree for f(4) already has 9 calls, and f(2) is worked out twice. For a bigger x the tree grows very fast.

The table trick. Instead of drawing the tree, work upward from the base cases, one value at a time. Each new value needs only the two values just before it.

So f(4) = 5 and f(6) = 21.

A program can build the same table with a list. Position x of the list holds f(x), so table[x - 1] and table[x - 2] are the two values just before.

Run it from this unit's folder:

python assets/l2.py < assets/l2/1.in

It prints 0 1 1 3 5 11 21, the bottom row of the table above.

Indirect recursion

Intermediate and above.

In indirect recursion, one function calls a second function, which calls the first one back. Neither one calls itself directly, but together they go round in a loop until a base case stops them.

f(x) = { g(x - 1) + 1              if x > 0
       { 0                         if x <= 0

g(x) = { 2 * f(floor(x / 2))       if x > 1
       { x + 1                     if x <= 1

Find f(10). Add a column for which function is being called.

Coming back up: f(1) = 1 + 1 = 2, g(3) = 2 * 2 = 4, f(4) = 4 + 1 = 5, g(9) = 2 * 5 = 10, and f(10) = 10 + 1 = 11.

Does it ever stop?

Before you start a table, check that the calls head toward a base case.

f(x) = { f(x + 2) - 1     if x > 0
       { 5                if x <= 0

For f(3): f(3) needs f(5), which needs f(7), and so on forever. x moves away from the base case, so this f(3) has no value. This is called infinite recursion. ACSL definitions always reach a base case, but when you invent your own, make sure every recursive row moves toward one.

ACSL never asks about a function applied to its own result, such as f(f(x)), so this book does not either.

Lesson 3 — Recursion in Python

A Python function can call itself. Here is the opening problem's f, written as a Python function. Compare it with the definition row by row.

Watching the calls

Add two print lines to see the calls happen: one when a call starts, and one just before it returns.

The call stack

When f(17) calls f(14), the call f(17) is not finished: it still has to add 17. Python remembers every unfinished call, each with its own x, in a pile called the call stack.

f(8)     <- running now; it is a base case, so it returns 11
f(11)    waiting to add 11
f(14)    waiting to add 14
f(17)    waiting to add 17

A new call goes on top of the pile. When the top call returns, it is removed, and the call below it carries on with the returned value. Because each call has its own x, the x in f(11) stays 11 while f(8) runs.

The pile cannot grow forever. Python stops a program with a RecursionError when calls go about 1000 deep. That happens when a function has no base case, or when a recursive case moves away from it:

mod, floor and abs in Python

The ACSL operations have Python partners you already know:

Here is g from Lesson 1.

Two variables, multiple and indirect recursion

Every kind of definition from Lesson 2 goes into Python the same way: one branch per row.

For indirect recursion, write both functions. Python looks up g only when f actually runs, so it does not matter that f is written first.

Returning two things at once

Sometimes you want a function to report two results, for example its value and how many calls it took. Return a tuple, and unpack it where you call the function.

Put it together: here is a complete solution to the programming part of the opening problem. It reads x and prints f(x). It is saved as assets/l3.py.

Run it from this unit's folder:

python assets/l3.py < assets/l3/1.in