How the solver works: recursive functions

This is the second of three posts that explain how to solve the N-Queens problem. The first post introduced Pidgin Python, a very simple language for writing software. (If you haven’t read it yet, I recommend taking the time to do so before continuing with this post.) This post discusses recursive functions. The third post applies what we develop in the first two posts to explain how our solver for the N-Queens problem works.

To introduce recursive functions, we’ll first write a Pidgin Python program to sum the numbers from 1 to some given number n. This program will use a loop similar to the loop we used in the first post.

The loop approach

function: sum_to_n
input: n
# We will start at 0 and step through the numbers up to n:
# 0, 1, …, n-1, n. We will use the name i to keep track of where we 
# are in that process. We will add each number we encounter to an   
# accumulator, sum_so_far, to keep track of the sum so far.

set i to 0
set sum_so_far to 0
repeat while i is less than n:
    set i to i+1
    set sum_so_far to sum_so_far + i

# Once we exit the loop, we know that i has reached n. In other     
# words, we have added all the numbers from 1 to n to sum_so_far,   
# which is the sum we want.
set output to sum_so_far

The recursive approach

A recursive program is defined as one that applies itself to a subproblem of the problem it is in the process of solving. To apply that definition in this case, we might notice that the sum of the numbers from 1 to n is 1 plus the sum of the numbers from 2 to n. Notice that finding the sum of the numbers from 2 to n is a subproblem of finding the sum of the numbers from 1 to n.

Applying this insight, we write our recursive program to find the sum of numbers from any starting point i to n. Here is a first draft. It’s startlingly short. The operational part is a single line!

function: sum_from_i_to_n
input: i, n

set output to i plus sum_from_i_to_n(i+1, n)

The final line, the line that does all the work, is a generalization of the example above about 1 and 2: the sum of the numbers from i to n is i plus the sum of the numbers from i+1 to n.

We can use this function to solve our original problem: find the sum of the numbers from 1 to n. We do so by running the function with i set to 1.

sum_from_i_to_n(1, n)

If this is not clear to you, spend some time thinking about it. It’s important.

Other than two problems we have not yet faced, this program will find the sum of numbers from any starting point i to n.

Once the idea becomes clear, it may seem like magic. We are writing a function, sum_from_i_to_n, but the function does little more than use itself—even though the function itself is not defined except in terms of itself. It looks like a completely circular definition. How can that possibly work? Well, it does. That is the joy, and what may be considered the mystery, of recursion.

Tidying up

Now for the two problems we have yet to face. The first is the same one we saw in our earlier post: what happens if i is larger than n? Since each recursive application of the function increments i, the function will apply itself repeatedly until the computer runs out of memory and aborts. This can be solved the same way we solved it before: test i to ensure it is not greater than n. If it is, terminate immediately and issue an error message.

The stopping problem

The second problem is the key to recursion: even if i is less than n, the function as written has no way of stopping. The solution is to recall that a recursive function applies itself to a subproblem of the problem it is solving. In other words, each time the function is applied recursively, the problem it is solving is simpler than the one it had been solving. Eventually, the function will be asked to solve a problem that is so simple that an answer can be determined immediately. A problem in a form that can be solved immediately is known as a base case.

With the function sum_from_i_to_n, when i is equal to n, we have reached a base case. When i is equal to n, the sum of the numbers from i to n is simply n—no computation needed. If i is the same as n, the output is set to n, and the function terminates.

We can modify our draft version as follows.

function: sum_from_i_to_n
input: i, n

if i is equal to n:
    set output to n
otherwise:
    set output to i plus sum_from_i_to_n(i+1, n)

Given this added conditional, we can solve our first problem—i is greater than n—at the same time. Rewrite the if arm of the conditional as follows

if i is equal to or greater than n:
    set output to n

With this change, the recursion will stop when it should, when i reaches n. Let’s run this function with i = 1 and n = 4 and watch it work. (See lines 1 - 5 below.)

Line 1 below shows the initial expansion of sum_from_i_to_n(1, 4) to be
1 + sum_from_i_to_n(2, 4).

In lines 2, 3, and 4, the portion after the arrow is the same as in the previous line except that a recursive application is shown for the then-current value of i.
o Line 2 shows the expansion of sum_from_i_to_n(2, 4) from line 1 to be
2 + sum_from_i_to_n(3, 4).
o Line 3 does the same thing for sum_from_i_to_n(3, 4) from line 2.
o Line 4 replaces sum_from_i_to_n(4, 4) from line 3 with 4.
o Finally, line 5 replaces 1 + (2 + (3 + 4)) with that sum, i.e., 10.

The function sum_from_i_to_n(1, 4) is applied repeatedly to a simpler problem until we reach sum_from_i_to_n(4, 4), which is simply 4. In other words, after the first line, each line corresponds to a recursive application of our function.

 1. sum_from_i_to_n(1, 4) → 1 + sum_from_i_to_n(2, 4)
 2.                       → 1 + (2 + sum_from_i_to_n(3, 4))
 3.                       → 1 + (2 + (3 + sum_from_i_to_n(4, 4)))
 4.                       → 1 + (2 + (3 + 4))
 5.                       → 10

With this example, we have completed our discussion of recursion. The next post will use what we have developed in these first two posts to explain the solver for the N-Queens problem.