Recursion: See Recursion

[T]here are two things traditionally taught in universities as a part of a computer science curriculum which many people just never really fully comprehend: pointers and recursion. — Joel Spolsky

Let’s try to comprehend the basics of recursion using an example that comes up frequently in programming puzzles: generating all permutations of a set.

Permutations

As a canonical example of using recursion to generate all permutations, I’ll use Permutations.java from Princeton’s introductory CS course. (Yes, I realize the irony of using a Java example after quoting that particular Spolsky article).

Permutations.java solves the following problem:

Given an integer n, print all permutations of the first n letters of the English alphabet.

The provided code solves the problem twice. I’ll be explaining version 1, which prints the permutations in lexicographic order, since this is a common requirement in competitive programming problems.

The key part of the algorithm is in a function called perm1. This function accepts two strings, a prefix and a string of remaining characters. The prefix contains the part of the permutation that has been constructed so far. The second string contains characters that still need to be added to the prefix.

To begin the recursion, we call perm1 with an empty prefix and a string consisting of the first n letters of the alphabet. Here’s the full pseudocode for perm1:

perm1(string prefix, string str)
    if str is empty, print prefix
    else
        for each character c in str
            newPrefix = concatenate c with prefix
            newStr = str without c
            recursively call perm1 with (newPrefix, newStr)

Amazingly, this tiny function solves the whole problem.

perm1 combines an iterative and a recursive strategy. The recursion begins with an empty prefix and a string of length n, and ends with a prefix of length n and an empty string. The first line of the function takes care of terminating the recursion at the base case: once the string is empty, print the result (the prefix), and don’t make any more recursive calls.

The else condition contains the iterative portion of the algorithm: Iterate through each character in the string, and do three steps:

• Concatenate the character to the end of the current prefix, making a new prefix.
• Remove the character from the current string, making a new string.
• Recursively call the perm1 function with the new prefix and the new string.

Since each loop iteration removes one character from str before the recursive call, str will eventually be empty, which will stop the recursion.

Why use recursion to solve this problem? When a programmer calls a function recursively, they can rely on the programming language to keep track of the values of the parameters for the current recursive call. For perm1, the parameters are prefix and str. When the function begins, it uses the values passed by the caller. When it recursively calls itself, these values are saved, and later retrieved when the recursive call returns. The permutation algorithm uses this behavior to generate the appropriate strings in the right order.

Example: “abc”

To illustrate how perm1 works, consider the initial string abc. The diagram below shows the first iteration of the first loop when perm has been called with prefix = "" and str = "abc".

Here’s how the process works, from top to bottom:

• perm is called for the first time with an empty prefix and the initial string abc.

• Since the string is not empty, we begin a loop over the three characters in str. The diagram shows only the first iteration of the loop.

• Inside the loop are two steps: Move a character from str to prefix, and recursively call perm1 with the result. Since this is iteration 0 of the loop, we move the character at position 0. The character is a. That means we call perm1 with prefix = "a" and str = "bc".

• We’re now at recursion depth 1, the first recursive call to perm1. This starts another loop over the string bc. But this time the prefix isn’t empty. It contains the character a.

• In iteration 0 of the current loop, we move str[0] to the prefix, giving us prefix = "ab" and str = "c". Then we call perm1 again, which brings us to recursion depth 2.

• At recursion depth 2, str only has one character, so the loop at this depth only has one iteration. Moving that single character to prefix gives us prefix = "abc" and an empty string.

• Calling perm1 with an empty string tells the function that the process is done, and the answer is in the prefix. We have our first permutation, abc.

• At the bottom of the diagram is a similar process that leads to the second permutation, acb.

At this point we have the two permutations that begin with a. The function returns to iteration depth 0 to find the two permutations that begin with b, followed by the two permutations that begin with c. The outermost loop then terminates, having covered all $3!=6$ permutations of abc.

The Benefit of Recursion

Programmers use recursion to simplify what data they need to keep track of. In this permutation example, we are keeping track of: 1) A prefix containing the start of a permutation, and 2) A string containing characters to be appended to the prefix. The programmer doesn’t have to worry about what the current prefix is, or which characters remain to be added to it.

If you were designing this algorithm from scratch, it might be hard to see where the critical part happened. In a purely iterative solution, you would explicitly construct the permutations. In the recursive solution, this seems to happen automatically. Looking at the perm1 pseudocode, there’s no obvious spot where characters are rearranged. There are just these steps:

1. Loop over the remaining characters, in order.
2. Move the current character from the string of remaining characters to the prefix.
3. Make a recursive call with the new prefix and the new character string.

The trick is in Step 2, specifically the fact that a character can be moved from any position in the string of remaining characters. This means the first character in the prefix can be any of the original characters, the second character can be any of the remaining characters, and so on. This is the definition of a permutation.

Learning to Think Recursively

There’s no shortage of programming puzzles that are amenable to a recursive solution. uHunt Chapter 3 has nine examples just in the starred problem list, and many more in the full list. The key is to combine practice with instruction. Do some reading, then solve a problem, then make sure you understand the solution. Trying to explain the solution in detail using diagrams and/or written descriptions is a good way to demonstrate that you really get it.

(Recursive books image credit: Alexandre Duret-Lutz)