[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.
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(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.
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
perm1function 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
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.
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:
permis called for the first time with an empty prefix and the initial string
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
prefix, and recursively call
perm1with the result. Since this is iteration
0of the loop, we move the character at position
0. The character is
a. That means we call
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
In iteration 0 of the current loop, we move
strto the prefix, giving us
prefix = "ab"and
str = "c". Then we call
perm1again, which brings us to recursion depth 2.
At recursion depth 2,
stronly has one character, so the loop at this depth only has one iteration. Moving that single character to
prefix = "abc"and an empty string.
perm1with an empty string tells the function that the process is done, and the answer is in the prefix. We have our first permutation,
At the bottom of the diagram is a similar process that leads to the second permutation,
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
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:
- Loop over the remaining characters, in order.
- Move the current character from the string of remaining characters to the prefix.
- 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)