Data Structures and Algorithms with C · Lecture Notes

Chapter 3: Recursion, Binary Search and Backtracking

Some problems contain a smaller copy of themselves. The factorial of a number rests on the factorial of one less. Searching a sorted array reduces to searching half of it. Moving three disks requires knowing how to move two. These notes describe the recursive algorithms that solve such problems. They first examine how recursion works on the machine, that is, the call stack and the stack frame. Then they write binary search with a loop and with recursion, derive the recurrence relation from the towers of Hanoi, and generate permutations. The last part is devoted to the backtracking method: subset generation, satisfiability (SAT), n-queens, and the knight's tour are solved with it. Every piece of code is given in C, traced step by step, and its time and memory costs are computed with justification.

Learning outcomes

Think recursively
Express a problem as a base case and a shrinking subproblem; compare recursion with a loop.
Follow the stack
Draw the stack frame of each call (parameters, local variables, return address) and compute the memory cost of recursion.
Binary search
Write iterative and recursive binary search in C, trace it on an array, and show the O(log n) bound.
Recurrence relations
Set up and solve the recurrence h(n) = 2h(n − 1) + 1 for the towers of Hanoi; show that permutation generation is O(n·n!).
Backtracking
Tell brute force and backtracking apart; solve subset generation, SAT, and n-queens with these methods.
Heuristics
Explain why Warnsdorff's rule for the knight's tour is much faster than backtracking.

3.1Recursive algorithms

Someone new to programming learns first the loop as a way to repeat a job. A loop runs the same body again and again as long as a condition holds. Recursion achieves repetition another way: a function calls itself to do a small part of the job. This idea, which looks odd at first sight, is very old in mathematics. Definitions and proofs by induction have the same structure.

3.1.1What is recursion?

If the solution logic used for the whole of a problem also holds for its parts, a recursive algorithm can be written. The factorial is the plainest example. The identity n! = n · (n − 1)! ties the factorial of n to the factorial of a smaller number. (n − 1)! is tied to (n − 2)! by the same rule. The chain stops at 1! = 1.

Definition 3.1

Recursion is a function calling itself with a smaller input. A function that calls itself is called recursive. If a function calls itself directly, there is direct recursion: fact → fact. If a function calls another function, which at the end of the chain calls the first function again, there is indirect recursion: A → B → A.

A familiar example of indirect recursion is expression parsers. The function expr(), which parses an arithmetic expression, calls the function term() to read terms. When a new expression begins inside parentheses, term() calls expr() again. The two functions never call themselves directly, but the chain forms a closed cycle. When writing indirect recursion in C, the declaration (prototype) of the second function must be given before the first function; otherwise the compiler does not recognize a name it has not yet seen.

3.1.2Base case and recursive step

A function that calls itself must stop somewhere. The factorial chain stops at 1! = 1, because this value is known without referring to another factorial. Every recursive algorithm consists of these two parts.

Definition 3.2

The base case is the smallest instance, solved directly without resorting to recursion. The recursive step reduces the problem to a smaller instance of the same kind and builds the real solution from the solution of that instance. Every recursive call must come a little closer to the base case.

The last sentence of the definition is essential for the correctness of recursion. The word "smaller" is expressed with a measure: n in the factorial, the number of elements in the range in binary search, the number of disks in the towers of Hanoi. The measure must decrease at every call and reach its smallest value in the base case. If the measure does not decrease, the calls go on forever. On a real machine "forever" does not last long, because every call takes up space in memory and the allocated memory runs out quickly.

Two questions are asked when writing a recursive function. First, which is the smallest instance and what is its answer? Second, if the answer to an instance one size smaller were known, how would the real answer be built? The second question is the essence of recursive thinking. One does not think about how the smaller instance is solved; one takes it as solved. This assumption is the same as the "let it hold for n − 1" assumption in a proof by induction.

Common mistake

Forgetting the base case or writing a step that never reaches it. The function long f(int n) { return n * f(n - 1); } has no base case; the calls go past n = 0 and continue with negative numbers, and the program crashes with a stack overflow. If a base case is written but the step does not approach it, the result is the same: the base case if (n == 1) return 1; never catches the call f(0). In the factorial the condition n <= 1 is safer because it covers both 0 and 1.

Beginners often ask a question: does the recursive solution not use a lot of memory? To answer it, one must first be able to write recursive code, and then to compute the complexity of that code. A judgment of "it uses a lot of memory" made without having learned to write recursive code remains baseless. That is also why these notes are ordered this way: code first, measurement afterwards. The memory cost turns into a concrete number once the call stack is examined.

3.1.3A first example: factorial

The recursive definition of the factorial transfers to C almost one to one:

long fact(int n) {
  if (n <= 1)
    return 1;              /* base case */
  return n * fact(n - 1);
}

int main(void) {
  printf("%ld\n", fact(3));
  return 0;
}

The function returns a value of type long, because the factorial grows very fast. The if (n <= 1) in the first line catches the base case and returns 1. The last line is the recursive step: the expression n * fact(n - 1) first has fact(n - 1) computed and multiplies the returned value by n. The function main calls fact(3) and prints the result with the format %ld; the output is 6.

The reading of the code is the same as the reading of the definition: "if n is at most 1 the factorial is 1, otherwise it is n times the factorial of one less." A version with a loop does not have this sentence; in its place there is a counter and an accumulating variable. The biggest gain of recursion is this readability.

The correctness of the code is shown by induction. For n ≤ 1 the function returns 1 and 0! = 1! = 1. For n > 1, if fact(n - 1) is assumed to return (n − 1)!, the function returns n · (n − 1)! = n!. The base case and the step together give correctness for every n ≥ 0.

The size of the type long varies with the system, and this difference shows up immediately in the factorial. On 64-bit Linux and macOS long is 64 bits; its largest value is 263 − 1 ≈ 9.2·1018 and 20! ≈ 2.4·1018 fits within this limit. On Windows, however, long is 32 bits; its largest value is 231 − 1 = 2,147,483,647. 12! = 479,001,600 fits, 13! = 6,227,020,800 does not. Signed integer overflow is undefined behavior in C: the program may print a wrong number or behave unexpectedly. When the code of these notes was compiled with the option -fsanitize=undefined and tried on Windows, the call fact(13) reported exactly this error. For large factorials, long long (at least 64 bits) or big-number libraries are used.

3.2The call stack

Recursion is a definition on paper, but on a computer it works through a real mechanism. Understanding this mechanism is necessary both for tracing recursive code and for computing its memory cost. The mechanism is called the call stack, and it is used at every function call, recursive or not.

3.2.1The stack frame

When a function is called, control does not pass to the body of the function at once. First some preparation is done. The return address, that is, where the program will go back to when the function ends, is saved. The values of the parameters are copied to a place the function can reach. Room is allocated for the function's local variables. All this information is gathered in a single record that sits consecutively in memory.

Definition 3.3

A stack frame (activation record) is the record that holds the parameters, local variables, and return address of a function call, together with a pointer to the previous frame. The frames of the active calls sit on top of one another, in the order of calling, in a region of memory called the call stack.

As its name suggests, the call stack is a stack structure: last in, first out. When a function is called, its frame is added to the top of the stack. When the function ends with return, its frame is removed from the top and control passes to the return address in the frame. When the program starts, only the frame of main is on the stack. This first frame too holds a return address and a pointer to the previous frame; when main ends, control returns to the operating system.

system stack (grows from bottom to top)main()• return address• pointer to previous frame• local variablesbinsearch(list, 18, 0, 9)• parameters: list, searchnum, left, right• local: middle• return address → mainnew call on top
Figure 3.1: The system stack when main calls binsearch(list, 18, 0, 9). The frame of the new call is added on top; it holds the parameters, the local variable middle, and the return address to main.

Figure 3.1 shows this arrangement. In the figure the stack grows from bottom to top; the bottom frame is that of main. When binsearch is called, its frame is added on top. In this frame there are four parameters (list, searchnum, left, right), one local variable (middle), and the return address to main. One must note that the parameter list is not the array itself. In C an array parameter turns into a pointer carrying the address of the array's first element. It is this address that sits in the frame; the ten elements of the array stay in the frame of main and are not copied.

The frame layout of a real compiler varies with the processor and the compiler. Some parameters may be carried in processor registers instead of memory. Still, the logic is the same everywhere: every active call has its own frame, and these frames are kept in a stack order. This logic is enough for understanding recursion.

Recursion has no special case. When a function calls itself, a new frame is opened as well. Several calls of the same function can be on the stack at once, and each has its own copies of the parameters and local variables. The n in one call is entirely separate from the n in another.

3.2.2Code trace: fact(3)

How the call fact(3) changes the stack can be followed step by step. Table 3.1 gives, at each step, the line being executed, the current value of n, and the contents of the stack. The stack is written from left to right; the rightmost frame is the top of the stack.

Table 3.1: Trace of fact(3) and the call stack.
StepLine executednStack (bottom to top)Event
1printf(…, fact(3))—mainmain calls fact(3).
2if (n <= 1)3main | fact(3)3 > 1, not the base case.
3return n * fact(n - 1);3main | fact(3)The multiplication waits; fact(2) is called first.
4if (n <= 1)2main | fact(3) | fact(2)2 > 1, not the base case.
5return n * fact(n - 1);2main | fact(3) | fact(2)The multiplication waits; fact(1) is called first.
6if (n <= 1) return 1;1main | fact(3) | fact(2) | fact(1)Base case: 1 is returned. The stack is at its deepest.
7return n * fact(n - 1);2main | fact(3) | fact(2)2 · 1 = 2 is returned, the frame closes.
8return n * fact(n - 1);3main | fact(3)3 · 2 = 6 is returned, the frame closes.
9printf(…, fact(3))—main6 is printed.

The first half of the trace is a descent. At step 3 fact(3) starts computing the expression 3 * fact(2) but cannot do the multiplication, because the second factor is not yet known. So it calls fact(2) and its own frame waits on the stack. The same happens for fact(2) at step 5. At step 6 fact(1) reaches the base case and returns 1 without making any call. At this moment there are four frames on the stack: main and three calls of fact.

call stackmain()fact(n=3)fact(n=2)fact(n=1)→ 1
Figure 3.2: The call stack when fact(1) reaches the base case. Each of the three fact frames has a separate n.

The second half is an ascent. The frame of fact(1) is removed and control returns to the place where fact(2) left off, the unfinished multiplication. In the frame of fact(2) the n is still 2. That is why it matters that each box in Figure 3.2 has its own copy of n. While fact(1) was running, n was 1, but this was only in the frame of fact(1). The multiplication gives 2 · 1 = 2 and fact(2) ends. In the same way fact(3) computes 3 · 2 = 6. Finally main prints 6 and only main is left on the stack.

This trace shows the general behavior of recursive functions. The calls first descend to the base case; the real computation is mostly done on the way back. In the factorial all the multiplications are done during the ascent, from the innermost call outward: first 2 · 1, then 3 · 2.

3.2.3The memory cost of recursion

Every recursive call means a new frame. Frames go away only when the call ends. Consequently the number of frames on the stack at any moment equals the current length of the recursion chain. The largest value of this length is called the recursion depth.

Theorem 3.1 (Stack cost of recursion)

For a function with recursion depth d and frames of constant size, the extra memory used on the call stack is O(d).

The size of a frame depends on the number of parameters and local variables; these numbers are fixed by the code and do not change with the input. Let the frame size be c bytes. At any moment there are at most d recursive frames on the stack, because the recursion depth is the greatest length the call chain can reach. The memory used is at most c · d bytes, that is, O(d). □

For fact(n) the depth is n: the chain fact(n), fact(n − 1), …, fact(1) opens n frames. The extra memory is O(n). The time cost is also Θ(n), because each of the n calls does a constant number of operations (one comparison, one multiplication, one return).

The size of the call stack is limited. The operating system sets aside a fixed stack area for each thread; this area is 1 MB by default on Windows and mostly 8 MB on Linux. Even a function that spends a few tens of bytes per frame fills this area if it descends to hundreds of thousands of levels, and the program crashes with a stack overflow. Recursion of depth n is therefore dangerous for large n; recursion of depth log n, on the other hand, causes no trouble in practice. Even binary search on an array of a billion elements descends no deeper than 30 frames.

Common mistake

Computing only the time cost of a recursive function and forgetting the stack cost. fact and the factorial with a loop run in the same Θ(n) time, but the recursive version uses O(n) and the loop version O(1) extra memory. The stack cost of a recursive algorithm is the total size of the frames in the deepest call chain.

3.3Recursion or a loop?

It is often possible to solve the same problem both with recursion and with a loop. Which to choose depends on a balance among readability, memory, and speed.

3.3.1Two factorials

The two versions of the factorial side by side:

/* recursive */
long fact(int n) {
  return n <= 1 ? 1 : n * fact(n - 1);
}

/* with a loop */
long fact_loop(int n) {
  long f = 1;
  while (n > 1)
    f *= n--;
  return f;
}

The recursive version has shrunk to a single line. The conditional operator ?: is the expression form of the if–else construct: if the condition is true it gives the value before the colon, otherwise the one after. The loop version uses an accumulating variable named f. The line f *= n--; does two things: first it multiplies f by n, then it decrements n by one. The postfix -- operator uses the old value in the expression and decrements the variable afterwards. In the call fact_loop(4), f becomes 4, 12, 24 in turn, and the loop stops when n = 1.

In the loop version, changing the parameter n does not affect the caller. In C parameters are passed by value: the function works with a copy of the caller's variable. After the call fact_loop(x), x remains unchanged.

3.3.2Comparison

The differences between the two approaches are collected in Table 3.2.

Table 3.2: Comparison of recursion and a loop.
CriterionRecursiveLoop
ReadabilityVery close to the definitionNeeds state variables
Extra memoryO(depth) stackO(1)
Call costOne frame per stepNone
RiskStack overflow in deep recursionInfinite loop
Where it is naturalTrees, divide and conquer, backtrackingFlat scans, counters

The "call cost" row of the table is about speed. At every call a frame is set up, parameters are copied, and on return the frame is removed. These jobs are a few machine instructions, but more expensive than one iteration of a loop. On a simple job such as the factorial, the recursive version runs a little slower than the loop version. The asymptotic order is the same; the difference lies only in the constant factor.

The "where it is natural" row is more important. In the factorial a loop is as clear as recursion. In tree traversal, in the towers of Hanoi, or in backtracking this is not so. In these problems a call makes several subcalls and one must remember where each subcall left off. Recursion leaves this bookkeeping to the call stack; the loop version asks the programmer to keep the same record by hand.

3.3.3Turning recursion into a loop

Every recursive algorithm can be turned into a loop, and every loop into recursion. The method of conversion is to imitate the call stack: the programmer defines an array or stack structure, puts into it the information that recursion would have saved, and processes it with a loop. The following function computes the factorial this way:

long fact_stack(int n) {
  int stack[64], top = 0;       /* array imitating the call stack */
  long f = 1;
  while (n > 1)                   /* descent: push the factors */
    stack[top++] = n--;
  while (top > 0)                 /* return: do the pending products */
    f *= stack[--top];
  return f;
}

The first loop corresponds to the descent phase of recursion. In each round it pushes a pending factor (n, n − 1, …, 2) into the array. The second loop is the ascent phase: it takes the factors in reverse order and multiplies them into the accumulator. The size of the array stack is chosen as 64; since the factorial no longer fits a 64-bit number at n = 21, this size is sufficient. The information the recursive fact keeps on the call stack is exactly this array. For the factorial this conversion is an unnecessary trouble, because the multiplications are independent of order and a single variable suffices. In problems such as tree traversal, however, an explicit stack is the most natural way to a nonrecursive solution.

The choice is a balance. If code readability comes first and the depth is small (for example O(log n)), recursion is a good choice. If the depth can be large or the cost of each call matters, a loop is preferred.

3.4Tail recursion

Some recursive functions have a special form: the recursive call is the last thing the function does. Functions of this form can be converted into loops mechanically, and the compiler can do this conversion itself.

3.4.1Definition and the accumulating parameter

Definition 3.4

If the recursive call is the last job of the function, that is, no work remains to be done after the call returns, this recursion is called tail recursion. Such a call is called a tail call.

fact is not tail recursive. In the line return n * fact(n - 1); a multiplication is done after the recursive call returns. The value of n must be saved for this multiplication; so the frame has to stay on the stack until the subcall ends. The tail-recursive version of the factorial uses an extra parameter to get rid of the pending multiplication:

long fact_tail(int n, long acc) {
  if (n <= 1) return acc;
  return fact_tail(n - 1, n * acc);  /* last job: the call */
}
/* first call: fact_tail(n, 1) */

acc (accumulator) is the accumulating parameter and carries the partial product computed so far. The multiplication is done before the recursive call, while the argument is computed: n * acc. When the call returns, no work remains; the returned value is passed upward as is. In the base case the accumulator is the full result and is returned directly. In the first call the accumulator is 1, because 1 is the identity of multiplication.

fact_tail(4, 1)fact_tail(3, 4)fact_tail(2, 12)fact_tail(1, 24)→ 24 returns directly
Figure 3.3: The call chain of fact_tail(4, 1). The partial product advances in the parameter; the 24 returned by the innermost call is passed upward without any further operation.
Example 3.1

Tracing the call fact_tail(4, 1):

  1. fact_tail(4, 1): n = 4 > 1; fact_tail(3, 4 · 1) = fact_tail(3, 4) is called.
  2. fact_tail(3, 4): fact_tail(2, 3 · 4) = fact_tail(2, 12) is called.
  3. fact_tail(2, 12): fact_tail(1, 2 · 12) = fact_tail(1, 24) is called.
  4. fact_tail(1, 24): base case; acc = 24 is returned.
  5. 24 passes through three frames without any further operation and reaches the original caller.

In fact the multiplications were done on the way back, from the inside out: 2 · 1, 3 · 2, 4 · 6. In fact_tail they are done on the way down, from the outside in: 4 · 1, 3 · 4, 2 · 12. Because multiplication is commutative and associative, the result is the same.

3.4.2The compiler and the tail call

Since after a tail call there is no work waiting in the frame, there is no point in keeping the frame. Instead of opening a new frame, the compiler updates the parameters in the existing frame with the new values and jumps to the start of the function. This transformation is called tail call optimization. The result is the same machine code as the loop version, and the stack cost drops to O(1).

The C standard does not guarantee this optimization. GCC and Clang often turn tail calls into jumps at the -O2 level; in a build with optimization off (-O0), each call opens a new frame. It is therefore not right in C to rely on a tail recursion whose depth could be very large. Such a function is easy to turn into a loop by hand: the parameters become loop variables, new values are assigned to the parameters in place of the recursive call, and the base case becomes the exit condition of the loop. In this way fact_tail turns into fact_loop.

Common mistake

Taking a call that stands at the end of a line for tail recursion. In the line return n * fact(n - 1); the call appears last in the text, but the last operation performed is the multiplication. The criterion is not the order of writing but whether any work remains after the call returns. In the line return fact_tail(n - 1, n * acc); the result of the call is returned as is; this is a tail call.

3.5Binary search

Searching is the job of finding a desired value in a data set. The best that can be done in an unsorted array is to look at the elements one by one; this is called linear search and needs n comparisons in the worst case. If the array is sorted, much better can be done. In a sorted array a single comparison tells in which half the sought value lies. Binary search uses this information at every step.

3.5.1The problem and the COMPARE macro

Definition 3.5

Binary search is a routine that finds the sought value in an array sorted in ascending order. At each step it looks at the element in the middle of the range. If the middle element equals the sought value, it returns its index. If it is smaller than the sought value, it discards the left half; if larger, the right half, and continues the search in the remaining half. If the range becomes empty, the value is not in the array and the result is −1.

All the binary search examples in this chapter use the same test array:

04113218319424527633736839940
Figure 3.4: The test array list: ten elements in ascending order. The numbers above the boxes are indices.

The routine returns not the sought value itself but its index. There are two reasons. First, the sought value is already known; what one really wants to know is its place in the array. Once the index is known, the other fields of the record at that position can also be reached. Second, the "not found" information must not be confused with values. Had the routine returned list[i], the −1 chosen as the error marker could be confused with a real −1 element in the array. Since array indices in C start from 0, −1 matches no valid index and safely carries the meaning "absent".

The result of a comparison is one of three cases: less, equal, or greater. To keep the code simple, a macro is defined that turns these three cases into a number:

#define COMPARE(x, y) ((x) < (y) ? -1 : (y) < (x) ? 1 : 0)

COMPARE(x, y) gives −1 if x < y, 1 if x > y, and 0 if they are equal. The macro is written with two nested conditional operators. If the first condition (x) < (y) is true, the result is −1. Otherwise the second condition (y) < (x) is tested; if true the result is 1, otherwise 0. Wrapping the macro parameters in parentheses at every occurrence follows from the text substitution rule of the preprocessor. In a call such as COMPARE(a + 1, b) the parentheses prevent the expression from being grouped wrongly because of operator precedence.

The result of the macro can be tied to three separate branches in a switch statement. For numeric comparison the difference x - y could also have been used, but with large numbers the difference can overflow. Since the macro does no subtraction, it does not carry this risk.

3.5.2Iterative binsearch()

The version of binary search written with a loop is this:

int binsearch(int list[], int searchnum,
              int left, int right) {
  while (left <= right) {
    int middle = (left + right) / 2;
    switch (COMPARE(list[middle], searchnum)) {
      case -1: left = middle + 1; break;
      case 0: return middle;
      case 1: right = middle - 1;
    }
  }
  return -1;
}

The function takes four parameters. list is the starting address of the sorted array, and searchnum is the value to be found. left and right are the left and right end indices of the range in which the search continues. To search the whole array, binsearch(list, x, 0, n - 1) is called. The ends of the range are closed: the elements at indices left and right are part of the range too.

The condition while (left <= right) checks that the range is not empty. In a closed range the case left = right is a range of one element and must still be searched; that is why the condition is written with <=, not <. In each round of the loop the middle index is computed with middle = (left + right) / 2. In C the quotient of two integers is an integer with the fractional part dropped; (0 + 9)/2 gives 4.

The switch statement divides into three branches according to the result of COMPARE(list[middle], searchnum):

  • case -1: the middle element is smaller than the sought value. The sought value, if present, is to the right of middle. The left end is set to middle + 1; middle is no longer in the range, because it has been looked at. break makes control leave the switch and return to the start of the loop.
  • case 0: equality. The sought value has been found and its index is returned. return leaves the switch, the loop, and the function all at once.
  • case 1: the middle element is larger than the sought value. The sought value, if present, is to the left of middle; the right end is set to middle - 1. Since this is the last branch, the switch ends anyway even without a break.

The loop ends when the range becomes empty (left > right) and the function returns −1. In every round of the loop the range shrinks by at least one element: either a branch ends with return, or left increases, or right decreases. The loop therefore always terminates.

Common mistake

Updating the ends as left = middle or right = middle. When two elements remain in the range, for example with left = 2, right = 3, middle becomes 2. If the sought value is on the right, the assignment left = middle leaves left at 2 and the loop goes around forever with the same range. Adding ±1 both guarantees termination and removes the element already looked at from the range.

3.5.3Code trace: searching for 18

Tracing the call binsearch(list, 18, 0, 9) shows how the range narrows. Table 3.3 gives the variable values in each round.

Table 3.3: Trace of binsearch(list, 18, 0, 9).
Roundleftrightmiddlelist[middle]COMPAREAction
1094241right = 3
203113−1left = 2
3232180return 2

In the first round the range is the whole array. The middle index is (0 + 9)/2 = 4, and the middle element is 24. Since 24 > 18, COMPARE gives 1: if 18 is present it is to the left of 24. The right half, indices 4–9, is discarded with a single comparison and right = 3. In the second round the middle is (0 + 3)/2 = 1 and the element is 13. Since 13 < 18, the left side is discarded: left = 2. In the third round the middle is (2 + 3)/2 = 2 and list[2] = 18 equals the sought value. The function returns 2. In an array of ten elements the value has been found with three comparisons.

04113218319424527633736839940▲ leftmiddle▲ right
Figure 3.5: The third round: left = middle = 2, right = 3. The gray cells are the discarded parts; list[2] = 18 is found.

3.5.4Code trace: 25 is not in the array

An unsuccessful search shows how the loop ends. The call binsearch(list, 25, 0, 9) proceeds as in Table 3.4.

Table 3.4: Trace of binsearch(list, 25, 0, 9).
Roundleftrightmiddlelist[middle]COMPAREAction
109424−1left = 5
2597361right = 6
3565271right = 4
—54———left > right: return -1

In the first round 24 < 25 comes out and the search moves to the right half: left = 5. In the second round the middle is (5 + 9)/2 = 7; since 36 > 25, right = 6. In the third round the middle is (5 + 6)/2 = 5 and the element is 27; since 27 > 25, right = 4. Now left = 5 > right = 4 and the range is empty. The loop condition comes out false and the function returns −1.

When the loop ends, the place left points to also carries information. left = 5 is the index where 25 would be placed without breaking the order if it were in the array: between 24 and 27. Throughout the loop every element to the left of left stays smaller than the sought value and every element to the right of right stays larger. When the range empties, these two regions meet and left points to the first larger element. Programs that insert into a sorted array use this observation.

04113218319424527633736839940left = 5 > right = 4: range empty
Figure 3.6: The end of the unsuccessful search: left = 5 > right = 4, the range is empty and the function returns −1.

3.5.5Recursive binsearch()

Binary search has a recursive structure: a search in half of the range is also a binary search. The version that, instead of a loop, calls itself with a shrunken range is this:

int binsearch(int list[], int x, int l, int r) {
  int m;
  if (l > r) return -1;          /* range empty */
  m = (l + r) / 2;
  switch (COMPARE(list[m], x)) {
    case -1: return binsearch(list, x, m + 1, r);
    case 0:  return m;
    case 1:  return binsearch(list, x, l, m - 1);
  }
  return -1;                     /* unreachable */
}

To keep the code short, the parameter names are abbreviated: x is the sought value, l and r the left and right ends of the range, and m the middle index. The function has two base cases. The first is the range being empty (l > r); the value has not been found and −1 is returned. The second is the case 0 branch; the value has been found and its index is returned. The other two branches are the recursive step. If the middle element is smaller, the search continues in the range [m + 1, r], and if larger, in the range [l, m − 1].

Both recursive calls begin with return: the result of the subcall is passed upward unchanged. These calls are tail calls. The line return -1; at the end of the function is never reached, because COMPARE gives only −1, 0, or 1, and all three branches end with return. The reason for writing the line is the compiler: a compiler that cannot know that the switch covers every possibility sees a path that ends without returning a value and issues a warning. This line prevents that warning.

Common mistake

Writing while instead of if in the recursive version. In a body that begins with while (l <= r), every branch leaves with return, so the loop runs only once and the result comes out right. Still the code is misleading: a reader expects a loop, whereas the repetition is provided by recursion. In the recursive version the range check must be done with if.

Common mistake

Not returning the result of the recursive call. If case -1: binsearch(list, x, m + 1, r); break; is written, the subcall finds the value correctly but the returned value is thrown away. The function then reaches the line return -1; and returns −1 even when the sought value is in the array. The result of a recursive call must either be returned or used in a variable.

3.5.6Code trace: the recursive version and the call stack

The recursive call binsearch(list, 18, 0, 9) tries the same middle indices (4, 1, 2) as the iterative version. The difference is that each round is done in a separate frame. Table 3.5 shows the changes in the call stack.

Table 3.5: Trace of the recursive binsearch(list, 18, 0, 9).
StepStack (bottom to top)l, r, mEvent
1main | bs(0, 9)0, 9, 4list[4] = 24
2main | bs(0, 9)0, 9, 424 > 18, case 1: binsearch(list, 18, 0, 3)
3main | bs(0, 9) | bs(0, 3)0, 3, 1list[1] = 13
4main | bs(0, 9) | bs(0, 3)0, 3, 113 < 18, case -1: binsearch(list, 18, 2, 3)
5main | bs(0, 9) | bs(0, 3) | bs(2, 3)2, 3, 2list[2] = 18
6main | bs(0, 9) | bs(0, 3) | bs(2, 3)2, 3, 2case 0: return 2
7main | bs(0, 9) | bs(0, 3)0, 3, 12 returns unchanged from the case -1 frame
8main | bs(0, 9)0, 9, 42 returns unchanged from the case 1 frame
9main—2 is returned to main

In the table bs(l, r) abbreviates the call binsearch(list, 18, l, r). In the descent phase each call halves the range and opens a new frame. At the deepest point, in steps 5 and 6, there are three binsearch frames on the stack above main. When the base case returns 2, the ascent begins. bs(2, 3) returns 2 to bs(0, 3), which is waiting in its case -1 branch. That in turn returns 2, without doing any operation, to bs(0, 9), which is waiting in its case 1 branch. Finally 2 reaches main.

04113218319424527633736839940▲ ml=0 r=9 m=4l=0 r=3 m=1l=2 r=3 m=2
Figure 3.7: The deepest moment of the recursive binary search. The three frames on the right hold the ranges [0, 9], [0, 3], and [2, 3]; the topmost frame finds the value at m = 2.

In the ascent phase no computation is done. In the factorial there were multiplications on the way back; here the returned value is passed on unchanged. This difference comes from whether the two functions are tail recursive. If tail call optimization is on, the compiler reduces these three frames to a single frame and the code works the same way as the iterative version.

In an unsuccessful search the depth can be one more. The call binsearch(list, 25, 0, 9) opens four frames with the ranges [0, 9], [5, 9], [5, 6], and [5, 4]. The last frame sees the empty range and immediately returns −1. In the iterative version this last check corresponds to the loop condition coming out false.

3.5.7Complexity

The speed of binary search comes from the range shrinking by at least half in every round. The number of elements in the range shrinks from n to n/2, n/4, …, and the last comparison is made when it has dropped to 1 at the latest.

Theorem 3.2 (Round bound of binary search)

In a sorted array of n ≥ 1 elements, binary search, whether the value is found or not, runs at most ⌊log2 n⌋ + 1 rounds. The time cost is O(log n).

Let there be s elements in the range at the start of a round. After the middle element is removed, ⌊(s − 1)/2⌋ elements remain on the left and ⌈(s − 1)/2⌉ = ⌊s/2⌋ on the right. Whichever half is taken, the new range has at most ⌊s/2⌋ elements. Since initially s = n, after k rounds at most ⌊n/2k⌋ elements remain in the range. For round (k + 1) to be possible, the range must not be empty: n/2k ≥ 1, that is, k ≤ log2 n. The round number k + 1 can be at most ⌊log2 n⌋ + 1. Since a constant number of operations is done in each round, the time is O(log n). □

The same result is obtained with a recurrence relation. Let T(n) be the cost of searching in a range of n elements. One round halves the range at a constant cost c:

T(n) = T(n/2) + c, T(1) = c

Expanding the relation gives T(n) = T(n/4) + 2c = T(n/8) + 3c = … = T(n/2k) + kc. When n/2k = 1, that is, for k = log2 n, one gets T(n) = c(log2 n + 1). This is O(log n).

Table 3.6 shows what logarithmic growth means. Linear search looks at every element of the array in the worst case; binary search looks at only a few.

Table 3.6: Numbers of rounds (comparisons) in the worst case.
nBinary search (max rounds)Linear search
10410
1,000101,000
1,000,000201,000,000
1,000,000,000301,000,000,000

In the test array n = 10 and at most ⌊log2 10⌋ + 1 = 3 + 1 = 4 rounds are needed. For 18 three rounds sufficed. An example that needs four rounds is 40: the middle indices 4, 7, 8, and 9 are tried in turn. These numbers were verified by searching for all values from 0 to 41 in the test array; no search exceeds four rounds. On an array of a million elements, too, when all successful and unsuccessful searches were tried, the maximum number of rounds came out as 20.

The memory cost differs in the two versions. The iterative version uses only a few variables; the extra memory is O(1). The recursive version opens a frame for each round; the depth equals the number of rounds and the extra memory is O(log n). For a billion elements that means 30 frames; in practice it is negligible.

Binary search has two preconditions. First, the array must be sorted; in an unsorted array the decision to discard half would be wrong and an existing value might not be found. Second, the element at any index must be reachable in O(1) time. An array satisfies this condition: list[middle] is found in one step by adding middle element sizes to the starting address. In a linked list, however, reaching the middle node requires moving node by node from the beginning. Each round takes O(n) steps and the gain of binary search is lost.

Common mistake

Computing the middle index with (left + right) / 2 on very large arrays. With a 32-bit int, the sum of two indices can exceed 231 − 1; this is signed overflow and undefined behavior. This happens only in arrays of more than a billion elements, but when it does, it is a hard bug to find. The safe form is left + (right - left) / 2; the difference never overflows and the result is the same.

3.6The towers of Hanoi

The factorial and binary search make a single recursive call at each step. The towers of Hanoi is the first example that makes two recursive calls. Two calls make the number of calls grow quickly and require a new tool to compute the cost of the algorithm: the recurrence relation.

3.6.1The problem

There are three towers (pegs): source, auxiliary, and destination. On the source tower sit n disks. The disks have different sizes and each disk is larger than the one on top of it; the largest disk is at the bottom and the smallest on top. The goal is to move all the disks to the destination tower in the same order, with the help of the auxiliary tower. There are two rules:

  1. In each move only one disk is moved; the topmost disk of a tower is taken and put on top of another tower.
  2. A disk cannot be placed on top of a smaller disk.
source321auxdest
Figure 3.8: The towers of Hanoi with three disks, initial state. The disks are on the source tower, arranged from largest to smallest.

With one or two disks the problem is easy. A single disk is moved directly to the destination. With two disks, the small disk is moved to the auxiliary tower, the large disk to the destination, and the small disk to the destination: three moves. With three disks a solution can be found by trial and error, but with ten disks this way does not work. A systematic method independent of the number of disks is needed.

3.6.2The recursive solution

The key to the solution is to focus on the largest disk. At some point the largest disk must be moved to the destination tower. At that moment there can be no disk on top of the largest disk, because only the topmost disk can be moved. The destination tower must also be empty, because the largest disk cannot be placed on any disk. All the remaining n − 1 disks must then be on the auxiliary tower. This observation divides the solution into three steps:

  1. The top n − 1 disks are moved from the source to the auxiliary tower, with the help of the destination tower.
  2. The largest disk is moved from the source to the destination.
  3. The n − 1 disks are moved from the auxiliary to the destination tower, with the help of the source tower.

The first and third steps are an instance of the same problem with n − 1 disks; only the roles of the towers have changed. In these steps the largest disk sits at the bottom of either the source or the destination. In both cases, because it is larger than all the other disks, it blocks no move; one can act as if it were not there. The base case is a single disk and is solved with one move. The C code of the algorithm is this:

void hanoi(int n, char *src, char *aux,
           char *dst) {
  if (n == 1)
    printf("%s -> %s\n", src, dst);
  else {
    hanoi(n - 1, src, dst, aux);
    printf("%s -> %s\n", src, dst);
    hanoi(n - 1, aux, src, dst);
  }
}
/* main: hanoi(3, "A", "B", "C"); */

The towers are represented by their names (strings of type char *). The code does not really move disks in memory; it only writes the moves to be made. printf("%s -> %s\n", src, dst) reports that the topmost disk of the source tower is moved to the destination tower. If n = 1, a single move is written. Otherwise the first recursive call hanoi(n - 1, src, dst, aux) is made. In this call one must note that the second and fourth arguments have swapped places: the destination of the n − 1 disks is the auxiliary tower of the original problem, and the helper tower is the original destination. Then the move of the largest disk is written. The second call hanoi(n - 1, aux, src, dst) moves the n − 1 disks from the auxiliary tower to the destination, using the source as the helper.

3.6.3Code trace: hanoi(3, "A", "B", "C")

In the problem with three disks, A is the source, B the auxiliary, and C the destination. The order of the calls and the moves written are given in Table 3.7. The calls in the table have the form hanoi(n, src, aux, dst).

Table 3.7: Trace of hanoi(3, "A", "B", "C").
StepActive callStack depthEventPrinted
1hanoi(3, A, B, C)1to move 2 disks A → B, hanoi(2, A, C, B) is called
2hanoi(2, A, C, B)2to move 1 disk A → C, hanoi(1, A, B, C) is called
3hanoi(1, A, B, C)3base caseA -> C
4hanoi(2, A, C, B)2disk 2 is moved; then hanoi(1, C, A, B)A -> B
5hanoi(1, C, A, B)3base caseC -> B
6hanoi(3, A, B, C)1disk 3 is moved; then hanoi(2, B, A, C)A -> C
7hanoi(2, B, A, C)2to move 1 disk B → A, hanoi(1, B, C, A)
8hanoi(1, B, C, A)3base caseB -> A
9hanoi(2, B, A, C)2disk 2 is moved; then hanoi(1, A, B, C)B -> C
10hanoi(1, A, B, C)3base caseA -> C

The stack depth is given without counting main. The program prints seven lines: A -> C, A -> B, C -> B, A -> C, B -> A, B -> C, A -> C. The first three moves carry the two small disks to B. The fourth move takes the largest disk to C. The last three moves carry the two disks on B to C, on top of the largest disk. Every move obeys the rules; this can also be verified by playing out the program's output step by step on a board.

AB21C3
Figure 3.9: The state after the fourth move (step 6): disks 1 and 2 are on the auxiliary tower (B), and the largest disk 3 is on the destination tower (C).

Two numbers in the table stand out. The total number of calls is seven, and each call performs exactly one printf; the base cases write one move each, and the other calls write the move in the middle. The stack depth never exceeds 3. In a problem with n disks one call chain descends as n, n − 1, …, 1; the depth is n and the stack cost is O(n).

3.6.4The call tree

All the calls of a recursive algorithm can be drawn as a tree. Each node is a call; the subcalls a call makes are its children. In Hanoi every call has two children: the left child is the first recursive call and the right child the second. Figure 3.10 gives the tree of the call hanoi(3, "1", "2", "3"), with the towers named 1, 2, and 3. In each box are written, in order, n, the source, the auxiliary, and the destination.

3,1,2,32,1,3,21,1,2,31,3,1,22,2,1,31,2,3,11,1,2,3
Figure 3.10: The call tree of hanoi(3, "1", "2", "3"). Each box is the frame of a call: n, src, aux, dst.

The tree carries the whole history of the call stack. At any moment the contents of the stack are the path from the root to the node currently running. For example, while the leftmost leaf (1, 1, 2, 3) is running, the stack contains the root (3, 1, 2, 3), its left child (2, 1, 3, 2), and the leaf itself. The length of the path is at most the height of the tree; this once more shows that the stack depth is n.

The order of the moves is obtained by an inorder traversal of the tree: first the left subtree, then the node itself, then the right subtree. The order in the code is the same: the first recursive call, the printf, the second recursive call. The move of each node is "source → destination" and is written after its left subtree has finished. This traversal gives the following seven moves:

1→3 · 1→2 · 3→2 · 1→3 · 2→1 · 2→3 · 1→3

When the program is run with the same call, this order also comes out.

3.6.5The recurrence: how many moves?

Let h(n) be the number of moves of the problem with n disks. The algorithm moves n − 1 disks twice and makes one move in between. The base case is a single move:

h(1) = 1, h(n) = h(n − 1) + 1 + h(n − 1) = 2·h(n − 1) + 1

Definition 3.6

A recurrence relation is an equation that expresses the value of a function in terms of the values of the same function at smaller inputs. To solve a recurrence is to write the function as a closed formula that does not refer to itself.

The cost of recursive algorithms is naturally expressed with a recurrence relation, because the algorithm itself has the same form. The simplest solution method is to expand the relation by substituting repeatedly:

h(1) = 1
h(n) = 2·h(n−1) + 1
     = 4·h(n−2) + 2 + 1
     = 8·h(n−3) + 4 + 2 + 1
     = …
     = 2ⁿ⁻¹·h(1) + 2ⁿ⁻² + … + 1
     = 2ⁿ − 1

In each line h(n − k) is replaced by 2·h(n − k − 1) + 1. After k steps the coefficient becomes 2k and the sum 2k−1 + … + 2 + 1 accumulates on the right. At k = n − 1 the base case is reached: h(n) = 2n−1·h(1) + 2n−2 + … + 2 + 1. Since h(1) = 1, this is the geometric sum 2n−1 + 2n−2 + … + 1 and equals 2n − 1. The value of the sum is easily seen with binary numbers: the number made of n one-bits is one less than 2n.

Theorem 3.3 (Number of Hanoi moves)

The recursive algorithm moves n disks in 2n − 1 moves. No method that obeys the rules can finish in fewer moves.

Number of moves. Induction: for n = 1, h(1) = 1 = 21 − 1. If h(n − 1) = 2n−1 − 1 is assumed, then h(n) = 2(2n−1 − 1) + 1 = 2n − 1.

Lower bound. Let m(n) be the least number of moves needed to move n disks; m(1) = 1. The largest disk must be moved at least once. Just before its first move, all the other n − 1 disks must have been gathered on the third tower; this takes at least m(n − 1) moves. After the last move of the largest disk, those n − 1 disks must be brought to the destination, on top of it; this also takes at least m(n − 1) moves. Hence m(n) ≥ 2·m(n − 1) + 1, and by induction m(n) ≥ 2n − 1. Since the algorithm makes exactly this number of moves, it is optimal. □

Table 3.8: Number of moves 2n − 1 by number of disks.
nMoves
11
23
37
415
101,023
201,048,575
6418,446,744,073,709,551,615

Table 3.8 shows the speed of exponential growth. Each new disk doubles the number of moves. According to legend, priests in a temple are moving a tower of 64 disks, and when the job is finished the world will end. 264 − 1 ≈ 1.8·1019 moves, at one move per second, take about 585 billion years. This is more than forty times the present age of the universe.

The time cost of the algorithm is Θ(2n). The number of calls also equals the number of moves, because each call writes exactly one move, and it satisfies the relation c(n) = 2c(n − 1) + 1. The stack cost is O(n). By the theorem there is nothing better: writing a cleverer program cannot reduce the number of moves, because this number comes from the problem itself. Hanoi is a problem whose output length is exponential, and no algorithm can finish without writing the output.

It is sometimes said that some problems can be solved only with recursion. The theoretical counterpart of this saying is not exactly so: every recursion can be turned into a loop with an explicit stack. What the saying really stresses is that for problems like Hanoi recursion is the only natural expression. Hanoi also has solutions with loops, but none is as clear as the three-line idea above.

3.7Permutation generation

In Hanoi the output was of exponential length. In permutation generation the output grows even faster: n elements have n! arrangements. This problem uses recursion for the first time inside a loop and introduces the basic idea of backtracking, undoing a choice that was made.

3.7.1The problem and the recursive idea

Definition 3.7

An arrangement of the elements of a set in a certain order is called a permutation. A set of n ≥ 1 elements has n! = n · (n − 1) · … · 1 different permutations. The permutation problem is to print all of these arrangements.

The number n! comes from a simple counting rule. Any one of the n elements can come in the first position. One of the remaining n − 1 elements comes in the second, one of the remaining n − 2 in the third. The choices are multiplied: n · (n − 1) · … · 1. For example the set {a, b, c} has 3! = 6 arrangements: abc, acb, bac, bca, cab, cba.

The same counting rule gives a recursive algorithm. The arrangements of the set {a, b, c, d} divide into four groups:

  • those that begin with a and are followed by an arrangement of {b, c, d},
  • those that begin with b and are followed by an arrangement of {a, c, d},
  • those that begin with c and are followed by an arrangement of {a, b, d},
  • those that begin with d and are followed by an arrangement of {a, b, c}.

Each group asks for the arrangements of a set of three elements. The problem with three elements reduces in the same way to problems with two elements, and those to problems with one element. A single element has a single arrangement; this is the base case.

3.7.2Implementing with swaps: perm()

To turn the idea into code, there is no need to keep the set of "remaining elements" in a separate array. All the elements sit in a single character array. The index i shows which position of the array is currently being filled. The positions list[0..i−1] are the fixed prefix; in the positions list[i..n−1] are the elements not yet placed. Each candidate is brought to position i in turn by a swap, the remaining positions are arranged by recursion, and then the array is restored to its former state by swapping back.

A macro with three arguments is used for the swap:

#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

The macro exchanges the values of x and y through the temporary variable t. The three assignments are combined into a single expression with the comma operator; the comma operator evaluates expressions from left to right in order. The reason the macro is preferred to a function is that in C a function must take addresses (pointers) in order to change the caller's variables. The macro, on the other hand, is substituted as text in the preprocessor and works directly on list[i] and list[j]. The permutation function is this:

void perm(char *list, int i, int n) {
  int j, temp;
  if (i == n) {                  /* one arrangement */
    for (j = 0; j < n; j++) printf("%c", list[j]);
    printf("\n");
  } else
    for (j = i; j < n; j++) {
      SWAP(list[i], list[j], temp);
      perm(list, i + 1, n);
      SWAP(list[i], list[j], temp);
    }
}

perm(list, i, n) prints all arrangements of the remaining positions while the first i positions of the array list are fixed. i == n is the base case: all positions are fixed and the array is a permutation. In this case the first for loop prints n characters, followed by a line break. If it is not the base case, the second for loop takes j from i to n − 1. Three things are done in each round:

  1. SWAP(list[i], list[j], temp): the element at position j is brought to position i. When j = i the element is swapped with itself and the array does not change.
  2. perm(list, i + 1, n): position i is now fixed; all arrangements of the remaining positions are printed.
  3. SWAP(list[i], list[j], temp): the same swap is repeated and the array returns to its state at the start of the loop round.

The variable temp is declared as int; a char is put into it and assigned back to a char. This conversion loses no value, because every char value fits in an int. The first call of the function, to arrange the whole array, has the form perm(list, 0, n). list must be a modifiable array: the declaration char s[] = "abc"; creates such an array, but giving a string constant, as in perm("abc", 0, 3), is undefined behavior. String constants may live in read-only memory, and the swap can crash the program.

3.7.3Code trace: perm("abc", 0, 3)

The call perm(list, 0, 3) with the array char list[] = "abc" prints six arrangements. Table 3.9 gives all the steps of the trace. In the stack column p(i) abbreviates the call perm(list, i, 3).

Table 3.9: Trace of perm("abc", 0, 3).
StepStacki, jActionlistPrinted
1p(0)0, 0swap with itself, perm(i = 1)abc
2p(0) p(1)1, 1swap with itself, perm(i = 2)abc
3p(0) p(1) p(2) p(3)3, —base caseabcabc
4p(0) p(1)1, 2list[1] ↔ list[2], perm(i = 2)acb
5p(0) p(1) p(2) p(3)3, —base caseacbacb
6p(0) p(1)1, 2swap back list[1] ↔ list[2]abc
7p(0)0, 1list[0] ↔ list[1], perm(i = 1)bac
8p(0) p(1)1, 1swap with itself, perm(i = 2)bac
9p(0) p(1) p(2) p(3)3, —base casebacbac
10p(0) p(1)1, 2list[1] ↔ list[2], perm(i = 2)bca
11p(0) p(1) p(2) p(3)3, —base casebcabca
12p(0) p(1)1, 2swap back list[1] ↔ list[2]bac
13p(0)0, 1swap back list[0] ↔ list[1]abc
14p(0)0, 2list[0] ↔ list[2], perm(i = 1)cba
15p(0) p(1)1, 1swap with itself, perm(i = 2)cba
16p(0) p(1) p(2) p(3)3, —base casecbacba
17p(0) p(1)1, 2list[1] ↔ list[2], perm(i = 2)cab
18p(0) p(1) p(2) p(3)3, —base casecabcab
19p(0) p(1)1, 2swap back list[1] ↔ list[2]cba
20p(0)0, 2swap back list[0] ↔ list[2]abc

In the table the own loop of the call p(2) has been abbreviated. When i = 2, j takes only the value 2; a swap with itself is made, p(3) is called, and the swap back is again with itself. These steps do not change the array.

0b1a2c▲ i▲ j 0c1b2a▲ i▲ j
Figure 3.11: Two swaps of the outer loop. (a) i = 0, j = 1: a and b change places, the array becomes bac (step 7). (b) i = 0, j = 2: a and c change places, the array becomes cba (step 14).

The output order is abc, acb, bac, bca, cba, cab. The last two lines do not follow dictionary order: cba comes before cab. The reason is the swap at step 14. In the round j = 2 a and c change places and the array becomes cba; b sits in the second position and a in the third. Because the subcall starts in this order, cba is printed first. All the arrangements come out exactly once; only their order is different.

The swaps back at steps 13 and 20 are essential for the correctness of the algorithm. Each round of the outer loop expects to find the array as abc. Had the swaps back not been made, the round j = 1 would have left the array as cba and the round j = 2 would have swapped list[0] and list[2], that is, c and a. In that case the arrangements starting with b would never be produced and those starting with a would be produced a second time. When the program is run and the array is printed after the call, abc is seen: every call leaves the array as it found it.

Common mistake

Forgetting the second SWAP. The code compiles and prints six lines, but some arrangements repeat and some never appear. The error can go unnoticed on small inputs. In every backtracking algorithm, a change made before the recursive call must be undone after the call.

3.7.4The recursion tree and complexity

The calls of perm form a tree. At the root no position is fixed. Each level fixes one more position, and the children of a node are the elements that can come to that position. The leaves are the completed arrangements.

·aababcacacbbbabacbcbcaccbcbacacab
Figure 3.12: The recursion tree of perm("abc", 0, 3). The root has no fixed prefix; each level fixes one position. The leaves give the six arrangements in the order of the output.

In the tree of Figure 3.12 the root has three children (a, b, c), each of them has two children (ab, ac, …), and those have one child each. Sibling branches must see the same starting array; the second SWAP repairs the array for this reason. The number of nodes at each level of the tree gives the number of calls. At level k the first k positions are fixed, and these positions can be filled in n · (n − 1) · … · (n − k + 1) different ways:

number of calls = 1 + n + n(n − 1) + … + n!

For n = 3 there are 1 + 3 + 6 + 6 = 16 calls, for n = 4 there are 1 + 4 + 12 + 24 + 24 = 65. These numbers were also verified by a program, by adding a counter to the function. The last two terms of the sum are n! and the earlier ones shrink quickly; the total is about e · n! ≈ 2.72 · n!. The number of leaves is exactly n!.

What determines the time is the writing at the leaves. Each leaf writes n characters; n! leaves come to n · n! characters in all. The work done at the internal nodes (swaps and loop checks) is constant per call and totals O(n!). The total time is Θ(n · n!). The permutation problem is sometimes briefly called O(n!) in some sources; this notation describes the number of arrangements but overlooks the factor of n for writing each arrangement. The stack cost equals the depth: n + 1 frames, that is, O(n).

Factorial growth is even faster than exponential growth. At n = 10 there are 10! = 3,628,800 arrangements and the number of characters to be written exceeds 36 million. At n = 20 the number of arrangements is 2.4·1018; even a machine that produces a billion arrangements per second finishes this job in 77 years. A solution based on trying all arrangements in turn can therefore be used only for very small n.

3.8Brute force and backtracking

Permutation and subset generation are ways of systematically walking through all the candidate solutions of a problem. Many problems can be solved by this walk: candidates are generated and each is tested against the rules. The rest of this chapter examines this approach and its clever form, backtracking.

3.8.1Two approaches

Definition 3.8

In the brute force approach all possible candidate solutions are generated and each is tested separately. In the backtracking approach the solution is built step by step. The moment a partial solution breaks a rule, all the candidates in that branch are pruned: the last choice is undone and the next option is tried.

Brute force relies on the speed of the computer. It is easy to set up and always gives the right answer, because it skips no candidate. Its problem is the number of candidates. A problem made of n yes/no decisions has 2n candidates, and a problem asking for an ordering of n elements has n!. Both reach numbers that no machine could finish once n passes a few dozen.

Backtracking walks through the same candidates, but with one difference: a candidate is tested before it is completed. If a partial solution is seen to break the rule, none of the candidates that begin with that partial solution are generated. For example, when placing eight queens, if the first two queens threaten each other, all placements of the other six queens are eliminated at once. Because this elimination resembles cutting off a branch of a tree, it is called pruning. The worst-case cost often stays in the same order as brute force, but in practice the number of candidates tried becomes much smaller.

One should never be fully sure of the data structure and method chosen when solving a problem. A solution that works by brute force is a starting point that calls for a search for something better. This attitude can be summed up in the sentence "there is a better solution method and we just have not found it". Backtracking and the heuristic rule in the knight's tour are products of such a search.

3.8.2The general pattern of backtracking

All backtracking algorithms follow the same skeleton. The following pseudocode gives this skeleton:

void backtrack(partial) {
  if (is_complete) { print; return; }
  for (each candidate choice)
    if (valid) { choose; backtrack(...); undo; }
}

The function takes a partial solution. If the partial solution is complete, it is printed and the function returns; this is the base case. If it is not complete, every candidate choice that could extend the partial solution by one step is tried in turn. A choice that obeys the rules is added to the partial solution (choose), the function calls itself, and when the call returns the choice is undone (undo). For choices that do not obey the rules, the recursive call is never made; that is pruning.

The permutation code fits this pattern exactly. The partial solution is the fixed prefix. The candidate choices are the elements list[i..n−1]. Choosing is the first SWAP and undoing the choice is the second SWAP. In permutations every choice obeys the rules, so there is no pruning. In the n-queens problem, however, the valid test does real work and cuts most of the branches.

Backtracking is sometimes wrongly understood as "rewinding the scenario from the end to the beginning". The method does not build the solution from the end to the start. It builds the partial solution forward; when it hits a dead end, it undoes only the last choice and continues forward from the same point with another choice. The only thing gone back to is the last decision point.

3.8.3Subset generation

Printing all subsets of a set is the plainest backtracking example. A set of n elements has 2n subsets, because there are two options for each element: it is taken into the subset or it is not. The algorithm makes these decisions in turn:

void subsets(char *s, int n, int i,
             int pick[]) {
  int j;
  if (i == n) {                  /* decisions done */
    printf("{");
    for (j = 0; j < n; j++)
      if (pick[j]) printf("%c", s[j]);
    printf("}\n");
    return;
  }
  pick[i] = 1; subsets(s, n, i + 1, pick);
  pick[i] = 0; subsets(s, n, i + 1, pick);
}

s is the character array holding the elements, and n is the number of elements. The array pick holds the decisions: if pick[j] is 1, element j has been taken, and if 0 it has not. i shows for which element the next decision will be made. i == n is the base case: all decisions have been made and the elements for which pick is 1 are printed inside braces. If it is not the base case, two calls are made. First, with pick[i] = 1, element i is taken and the function is called for the remaining decisions. Then, with pick[i] = 0, the element is left out and the same call is repeated.

In the code the step "undo the choice" does not appear as a separate line. The assignment pick[i] = 0 does two jobs at once: it undoes the choice of the first branch and makes the choice of the second branch. When leaving the function, pick[i] stays 0, but this does no harm. A caller one level up always reassigns pick[i] before reading it; and the printing at the base case reads only the values assigned up to that point.

Table 3.10: Output of subsets("abc", 3, 0, pick) and the decisions.
No.abcpickPrinted
1taketaketake[1, 1, 1]{abc}
2taketakeskip[1, 1, 0]{ab}
3takeskiptake[1, 0, 1]{ac}
4takeskipskip[1, 0, 0]{a}
5skiptaketake[0, 1, 1]{bc}
6skiptakeskip[0, 1, 0]{b}
7skipskiptake[0, 0, 1]{c}
8skipskipskip[0, 0, 0]{}

In Table 3.10 the decisions resemble a binary counter counting backwards: the array pick goes 111, 110, 101, …, 000. The reason is that the decision "take" is tried before "skip". The {} in the last row is the empty set; the empty set is also a subset of every set.

0a1b2c→ {bc}
Figure 3.13: The fifth leaf: a is not taken, b and c are taken; {bc} is printed.

The complexity computation is similar to Hanoi. Each call makes two calls and the depth is n. The call tree is a perfect binary tree with n + 1 levels: it has 2n leaves and 2n+1 − 1 nodes in all. For n = 3 there are 15 calls, for n = 4 there are 31. Each leaf does O(n) work by walking through the array pick from beginning to end. The total time is Θ(n · 2n) and the stack cost is O(n). The calling function allocates the array pick once and all calls use the same array; in each frame only a pointer to the array sits.

3.9The satisfiability (SAT) problem

Subset generation walked over two options for each element. The same walk can also be applied to assigning the values true or false to logical variables. The problem of this section is one of the most famous problems of computer science and shows the limits of brute force clearly.

3.9.1The problem

Definition 3.9

Let x1, x2, …, xn be logical variables that take the value true (T) or false (F). A formula is built from these variables with the operators ∧ (and), ∨ (or), and ¬ (not). The satisfiability problem (SAT for short) asks: is there an assignment of values to the variables that makes the formula true?

The formula examined in this section is:

(x1 ∧ ¬x2) ∨ (¬x1 ∧ x3) ∨ ¬x3

The formula is the disjunction of three terms, and if one of the terms is true the formula is true. For example, if x3 = F, the last term ¬x3 is true and so is the formula. Thus one sees at once that the formula is satisfiable. The question is how a computer program will find this.

The brute force solution is to try all assignments. Since each of the three variables takes two values, there are 23 = 8 assignments: {F, F, F}, {F, F, T}, …, {T, T, T}. With n variables the number of assignments is 2n. In each assignment the formula is evaluated once; if the size of the formula is |F|, this takes O(|F|) time. The total cost is O(2n · |F|).

Exponential cost cannot be overcome by parallel hardware either. Even if the work is divided equally among m processors, the cost is O(2n/m). In a formula with 100 variables there are 2100 ≈ 1.3·1030 assignments; even a million processors bring this number down only to the order of 1024.

No polynomial-time algorithm is known for SAT. The problem is the first member of the class of problems called NP-complete. If a polynomial-time algorithm is found for one of the problems in this class, all the problems in the class can be solved in polynomial time. So far no such algorithm has been found, but it has not been proved that none exists. The special form in which each clause has at most two variables (2-SAT) is solved in polynomial time; when the clauses have three variables (3-SAT) the problem is NP-complete again. The classification of problems in this way is the subject of the theory of computation course.

∨∨∧x1¬x2∧¬x1x3¬x3
Figure 3.14: The tree of the formula (x1 ∧ ¬x2) ∨ (¬x1 ∧ x3) ∨ ¬x3. Internal nodes are operators, leaves are variables.

3.9.2The formula tree and postorder evaluation

The natural way to evaluate a formula in a program is to store it as a tree. In the tree of Figure 3.14 each internal node is an operator. The ∧ and ∨ nodes have two children. The ¬ node has a single operand and it sits in the right child. The leaves are variables; the same variable may appear in several leaves. The definition of the tree in C and the evaluation function are as follows:

typedef enum { NOT_N, AND_N, OR_N, TRUE_N, FALSE_N } logic;
typedef struct tree_node *tree_ptr;
struct tree_node {
  tree_ptr left, right;
  logic data;
  short value;
};

void post_eval(tree_ptr L) {
  if (L) {
    post_eval(L->left);
    post_eval(L->right);
    switch (L->data) {
      case NOT_N: L->value = !L->right->value; break;
      case AND_N: L->value = L->left->value
                         && L->right->value; break;
      case OR_N:  L->value = L->left->value
                         || L->right->value; break;
      case TRUE_N:  L->value = 1; break;
      case FALSE_N: L->value = 0; break;
    }
  }
}

The first line defines an enumeration that names the node types. NOT_N, AND_N, and OR_N are the operator nodes. TRUE_N and FALSE_N are for the leaves: when an assignment is made, the type of each leaf becomes one of these two, according to the value of the variable in that assignment. The second line defines the name tree_ptr to mean "pointer to struct tree_node". The structure itself is in the third declaration: two child pointers, the type of the node (data), and the computed value of the node (value).

Placing the typedef before the structure definition is valid in C. At this point struct tree_node is still an incomplete type, but to define a pointer to it one need not know the contents of the type. This lets the structure contain fields that point to nodes of its own type. A structure cannot have a field of its own type (the value itself, not a pointer); that would mean a structure of infinite size.

There are two details in the choice of names. English names such as enum { not, and, or, true, false } cause trouble. true and false are defined as macros in the C99 header <stdbool.h> and became keywords in C23; not, and, and or are macros standing in for operators in the header <iso646.h>. If one of these headers is included, the enumeration does not compile. The second detail is that a typedef with no name written at the end, such as typedef struct tree_node {…};, defines no name. The compiler accepts this line but issues a warning. The code above uses names that do not clash.

The appearance of the node in memory is also worth examining. On a 64-bit system each of the two pointers takes 8 bytes and they make up the first 16 bytes of the structure. The field data (an enum, 4 bytes) starts at byte 16 and the field value (short, 2 bytes) at byte 20. The compiler adds 2 bytes of padding at the end of the structure and rounds the size up to 24 bytes, a multiple of 8. This padding ensures that in an array of structures every pointer sits at an address that is a multiple of 8. These numbers were measured with sizeof and offsetof; they may differ with another compiler or on a 32-bit system.

The nodes of the tree are created at run time with malloc. The code in the slides does not show this part; for a complete program the following two helper functions suffice:

tree_ptr new_node(logic v, tree_ptr l, tree_ptr r) {
  tree_ptr p = malloc(sizeof *p);
  if (p == NULL) {               /* allocation failed */
    fprintf(stderr, "out of memory\n");
    exit(EXIT_FAILURE);
  }
  p->data = v;
  p->left = l;
  p->right = r;
  p->value = 0;
  return p;
}

void tree_free(tree_ptr L) {     /* postorder: children first */
  if (L) {
    tree_free(L->left);
    tree_free(L->right);
    free(L);
  }
}

new_node asks for memory of the size of one node. The expression sizeof *p gives the size of the type p points to; since no type name is written, the expression stays correct even if the type of p changes. If malloc cannot allocate memory, it returns NULL. If p->data were written without checking this, the program would write through a null pointer and crash; that is why the return value is tested at once. tree_free gives back all the nodes of the tree. It deletes the two children first, then the node itself. The order matters: had the node been freed first, the field L->left would be read from freed memory, which is undefined behavior. If the program ends without the tree being deleted, the operating system reclaims the memory anyway, but in a long-running program, if a new tree is built for each assignment and not deleted, a memory leak results.

The formula tree and the assignment are set up like this:

tree_ptr leaf[5];   /* leaves: x1, x2, x1, x3, x3 */

tree_ptr build_formula(void) {
  int k;
  for (k = 0; k < 5; k++)
    leaf[k] = new_node(FALSE_N, NULL, NULL);
  /* (x1 AND NOT x2) OR (NOT x1 AND x3) OR NOT x3 */
  return new_node(OR_N,
           new_node(OR_N,
             new_node(AND_N, leaf[0], new_node(NOT_N, NULL, leaf[1])),
             new_node(AND_N, new_node(NOT_N, NULL, leaf[2]), leaf[3])),
           new_node(NOT_N, NULL, leaf[4]));
}

void set_leaves(tree_ptr root, int x1, int x2, int x3) {
  (void)root;            /* leaves are reached directly through leaf[] */
  leaf[0]->data = x1 ? TRUE_N : FALSE_N;
  leaf[1]->data = x2 ? TRUE_N : FALSE_N;
  leaf[2]->data = x1 ? TRUE_N : FALSE_N;
  leaf[3]->data = x3 ? TRUE_N : FALSE_N;
  leaf[4]->data = x3 ? TRUE_N : FALSE_N;
}

The five leaves are kept in the array leaf. While the tree is built, the addresses of these leaves are given as children to the appropriate operator nodes. set_leaves places an assignment into the tree: it makes the type of each leaf TRUE_N or FALSE_N according to the value of the variable it represents. The structure of the tree does not change; only the leaves change.

post_eval computes the value of the tree with a postorder traversal: first the left subtree, then the right subtree, and the node itself last. This order is mandatory, because the value of an operator node depends on the values of its children and the children must be computed before it. The function starts with if (L); for an empty subtree (NULL) it does nothing. This check stops the recursion both at the leaves and at the empty left child of a ¬ node. The switch statement computes the value according to the type of the node. The NOT_N node inverts the value of the right child. The AND_N and OR_N nodes combine the values of the two children with C's && and || operators. The leaves take the value 1 or 0 according to their type.

Example 3.2

For the assignment x1 = x2 = x3 = T, the tree is evaluated from the bottom up as follows:

  1. Leaves: x1 = T, x2 = T, x1 = T, x3 = T, x3 = T.
  2. ¬ nodes: ¬x2 = F, ¬x1 = F, ¬x3 = F.
  3. ∧ nodes: x1 ∧ ¬x2 = T ∧ F = F, ¬x1 ∧ x3 = F ∧ T = F.
  4. The inner ∨: F ∨ F = F. The ∨ at the root: F ∨ ¬x3 = F ∨ F = F.

The root comes out false: this assignment does not satisfy the formula.

∨=F∨=F∧=Fx1=T¬=Fx2=T∧=F¬=Fx1=Tx3=T¬=Fx3=T
Figure 3.15: The tree evaluated at the assignment 111. No term is true; the root is false.

3.9.3All assignments by brute force

Three nested loops could be written to walk over the eight assignments. A shorter way is to use a single loop that counts from 0 to 7 and to distribute the bits of the counter among the variables:

int m, x1, x2, x3;
for (m = 0; m < 8; m++) {    /* 2^3 assignments */
  x1 = (m >> 2) & 1;
  x2 = (m >> 1) & 1;
  x3 = m & 1;
  set_leaves(root, x1, x2, x3);
  post_eval(root);
  if (root->value)
    printf("%d%d%d\n", x1, x2, x3);
}

The three-bit binary representation of m is an assignment. The expression (m >> 2) & 1 shifts m two bits to the right and takes the rightmost bit; this is bit number 2 of m and is assigned to x1. In the same way bit 1 goes to x2 and bit 0 to x3. For m = 5 the binary representation is 101 and one gets x1 = 1, x2 = 0, x3 = 1. In each round the assignment is placed into the tree, the tree is evaluated, and if the root is true the assignment is printed.

Table 3.11: The value of the formula at the eight assignments.
mx1x2x3x1 ∧ ¬x2¬x1 ∧ x3¬x3Root
0000FFTT
1001FTFT
2010FFTT
3011FTFT
4100TFTT
5101TFFT
6110FFTT
7111FFFF

Table 3.11 shows that seven of the eight assignments satisfy the formula. The program prints the lines 000, 001, 010, 011, 100, 101, and 110; only the assignment x1 = x2 = x3 = 1 does not satisfy the formula. This output was verified by turning the code into a complete program and running it.

The SAT question asks only "is there an assignment?". To answer it, it is not necessary to print all assignments; a routine that returns at the first assignment that comes out true suffices. Such a routine stops at 000, the first assignment for this formula. Had the formula been unsatisfiable, the routine would have had to try all eight assignments. The worst case of brute force is the case in which the answer is "no".

3.9.4Kinds of SAT and precomputation

The satisfiability question can be asked in different forms:

Circuit satisfiability (CIRCUIT-SAT)
Is there an assignment of inputs that makes the output of a given logic circuit 1? A circuit is a network made of gates (AND, OR, NOT).
Formula satisfiability (Formula SAT)
Whether a propositional formula built with ∧, ∨, and ¬, as in this section, can be made true.
3-CNF-SAT
The formula is the ∧ of clauses; each clause is the ∨ of three variables (or their negations). Example: (x1 ∨ ¬x1 ∨ ¬x2) ∧ (x3 ∨ x2 ∨ x4) ∧ (¬x1 ∨ ¬x3 ∨ ¬x4). CNF stands for conjunctive normal form.

The brute force solution has a notable efficiency detail. The formula tree is built only once. At each assignment the structure of the tree stays the same and only the leaves change. Had the tree been built from scratch at each assignment, a chain of malloc and free would have run eight times. A data structure prepared once for a job that will be done many times is called precomputing. Precomputing may not change the order of the algorithm but it greatly reduces the constant factor.

Precomputing is also used in text search. When searching for a word in a text, if the structure of the word itself is examined beforehand and written into a table, there is no need to back up during the search. The Knuth–Morris–Pratt algorithm is a well-known example of this idea. The topics of greedy algorithms, branch and bound, and precomputing, in algorithm analysis books, describe ways of looking for something better than brute force.

3.10The n-queens problem

In permutation and subset generation every choice was valid; backtracking amounted only to undoing the choice. In the n-queens problem most choices break the rules, and pruning gives a real gain.

3.10.1The problem and the representation

Definition 3.10

The n-queens problem: place n queens on an n × n chessboard so that none threatens another. In chess a queen threatens every square along its row, its column, and its two diagonals. Hence there cannot be two queens in the same row, in the same column, or on the same diagonal.

Since two queens cannot stand in the same row, the n queens are spread over the n rows one each. This observation simplifies the representation: a solution is an array q of n elements, and q[r] is the column number of the queen in row r. The row rule is satisfied automatically by this representation. The column rule is that the values in q are all different. For the diagonal rule a test is needed.

If two queens at the squares (i, q[i]) and (r, c) are on the same diagonal, the row difference and the column difference are equal. Advancing in columns as much as the distance between rows is walking on a line of 45 degrees. Since the new queen is always placed in a lower row, r > i and the row difference is r − i. The column difference can go in two directions; the absolute value is taken:

|q[i] − c| = r − i

In the brute force solution the queen of each row is put in one of n columns and nn candidates result. For n = 8 this is 88 = 16,777,216, that is, about 16.8 million candidates. Applying the column rule from the start and trying only the permutations brings the number down to 8! = 40,320. Backtracking tries even fewer.

3.10.2safe() and place()

The backtracking solution consists of two functions. The first tests whether a square conflicts with the queens in the previous rows:

int q[8];  /* q[r]: column of the queen in row r */

int safe(int r, int c) {
  int i;
  for (i = 0; i < r; i++)
    if (q[i] == c || abs(q[i] - c) == r - i)
      return 0;         /* same column or diagonal */
  return 1;
}

The array q is defined as global, so that both functions reach it without taking it as a parameter. The size of the array is 8, so the code works for n = 8 at most. safe(r, c) says whether a queen can be put in column c of row r. The loop looks only at rows 0 … r − 1, because there are no queens in the lower rows yet. For each earlier queen two conditions are tested: q[i] == c catches the same column and abs(q[i] - c) == r - i catches the same diagonal. If there is a conflict, the function returns 0 at once. If the loop ends without finding a conflict, the square is safe. The function abs is in the header <stdlib.h>; if this header is not included, the compiler gives a warning or an error for an undeclared function.

The second function places the queens row by row:

int place(int r, int n) {
  int c;
  if (r == n) return 1;             /* solution */
  for (c = 0; c < n; c++)
    if (safe(r, c)) {
      q[r] = c;
      if (place(r + 1, n)) return 1;
    }
  return 0;                  /* backtrack */
}

place(r, n) tries to place the remaining queens starting from row r. It returns 1 if it succeeds and 0 if it fails. r == n is the base case: all rows have been filled and a solution has been found. If it is not the base case, the loop tries the columns from left to right. When a safe column is found, the queen is put there (q[r] = c) and the function calls itself for the next row. If the subcall returns 1, the solution is complete and the 1 is passed upward at once. If the subcall returns 0, this placement has reached a dead end; the loop continues with the next column. If no column works, the function returns 0 and the row above tries its next column.

There is no explicit line in the code that undoes the choice. The reason is the representation: q[r] is overwritten at the next attempt, and safe looks only at rows smaller than r. Values left over from a failed attempt are never read. The undoing is done implicitly, by r being kept in the frames on the stack.

3.10.3Code trace: 4 queens

The call place(0, 4) proceeds as in Table 3.12. The squares are written in the form (row, column) and rows and columns start from 0.

Table 3.12: Trace of place(0, 4).
StepRowColumns triedResultq
100(0, 0) safe[0, –, –, –]
210 ×, 1 ×, 2(1, 2) safe[0, 2, –, –]
320 ×, 1 ×, 2 ×, 3 ×no column, return 0[0, 2, –, –]
413(1, 3) safe[0, 3, –, –]
520 ×, 1(2, 1) safe[0, 3, 1, –]
630 ×, 1 ×, 2 ×, 3 ×no column, return 0[0, 3, 1, –]
722 ×, 3 ×no column, return 0[0, 3, –, –]
81—no columns left, return 0[0, –, –, –]
901(0, 1) safe[1, –, –, –]
1010 ×, 1 ×, 2 ×, 3(1, 3) safe[1, 3, –, –]
1120(2, 0) safe[1, 3, 0, –]
1230 ×, 1 ×, 2(3, 2) safe[1, 3, 0, 2]
134—r = n: solution, return 1[1, 3, 0, 2]

The first part of the trace shows that the queen placed in the upper left corner does not lead to a solution. At step 2, column 0 of the second row is in the same column as the first queen and column 1 is on the same diagonal; the first safe column is 2. At step 3 every column of the third row is under threat: columns 0 and 2 fall foul of the column rule, and 1 and 3 of the diagonals of the queen at (1, 2). The function returns 0 and the second row tries its next column, 3.

VV××××r → VVVV
Figure 3.16: 4 queens. (a) Step 3: the queens at (0, 0) and (1, 2) threaten all squares of the third row (×). (b) Step 13: the solution found, q = [1, 3, 0, 2].

Steps 4–7 show that the second attempt also reaches a dead end. No square is left in the fourth row, and the remaining columns of the third row are under threat too. At step 8 the second row returns 0, having tried its last column. Now the queen of the first row must move. At step 9 the queen is put at (0, 1) and this time a safe square is found in every row. At step 13 r = 4 = n and the solution q = [1, 3, 0, 2] is found. The returned 1 passes through four frames and reaches the original caller.

If the assignments q[r] = c in the table are counted, eight placements are seen to have been made: (0, 0), (1, 2), (1, 3), (2, 1), (0, 1), (1, 3), (2, 0), (3, 2). Brute force would have tested 44 = 256 candidates. These numbers were verified by adding a counter to place and running the program.

Common mistake

Writing the diagonal test in only one direction. The condition q[i] - c == r - i catches the diagonal going from upper right to lower left and misses the diagonal in the other direction. Taking the absolute value with abs covers both directions at once. Another mistake is to run the loop of safe up to i ≤ r; in that case an old value in q[r] is read and correct squares may be rejected.

3.10.4The gain from pruning

An upper bound for the worst-case cost of backtracking is easily found. Because of the column rule, at most n − r columns can be candidates in row r; the columns of the earlier queens are closed. At the first level of the call tree there are at most n nodes, at the second level at most n(n − 1) nodes, and the number of leaves is at most n!. The upper bound O(n!) given for the cost comes from here; the safe checks made at each node add only a polynomial factor to this class. This is a rough bound: the diagonal rule prunes most of the tree early, and the real cost stays far below n!. The stack cost equals the depth, O(n).

Table 3.13: The first solution, the number of placements, and the total number of solutions for small values of n.
nFirst solution qPlacementsNumber of solutions
4[1, 3, 0, 2]82
5[0, 2, 4, 1, 3]510
6[1, 3, 5, 0, 2, 4]314
7[0, 2, 4, 6, 1, 3, 5]940
8[0, 4, 7, 5, 2, 6, 1, 3]11392

The values in Table 3.13 were computed by a program. The placements column counts the assignments q[r] = c made up to the first solution. For eight queens, backtracking finds a solution with only 113 placements; compared with the 16.8 million candidates of brute force, the difference is striking. The column for the number of solutions was found by changing the algorithm so that it does not stop at the first solution but counts all solutions. There are 2 solutions for 4 and 92 for 8. The number of placements does not grow regularly with n: for 5 and 7 the first attempts succeed at once, while for 6 many dead ends are entered. The cost of backtracking depends closely on the structure of the input.

3.11The knight's tour and Warnsdorff's rule

Backtracking always finds the solution, but slows down as the number of candidates grows. In some problems a good selection rule leads to the solution without any need to go back. The knight's tour is the classic example of this situation.

3.11.1The problem

Definition 3.11

The knight's tour: a chess knight is to visit all the squares of a board, passing through each square exactly once. The knight moves in an L shape: two squares horizontally and one vertically, or two squares vertically and one horizontally.

A knight in the middle of the board can go to eight squares. On the edges and in the corners this number decreases; a knight in a corner reaches only two squares. The moves are kept in a table as the row change Δi and the column change Δj:

Table 3.14: The eight moves of the knight.
Move01234567
Δi−2−1+1+2+2+1−1−2
Δj+1+2+2+1−1−2−2−1
x01234567
Figure 3.17: The eight squares a knight at x can go to; the numbers are the order in the move table.

The table goes around the moves clockwise: move 0 takes the knight two rows up and one column right, and move 2 takes it one row down and two columns right. Working with the table makes it possible to try all the moves with a single loop instead of writing eight separate ifs. From the square (i, j), move k goes to the square (i + Δi[k], j + Δj[k]); the square must be inside the board and not yet visited.

3.11.2Backtracking and the heuristic

The backtracking solution is similar to n-queens. The knight is put on a square and each move is tried in turn. If no empty square is left for the knight to go to and not all squares have been visited, there is a dead end; the last move is undone and the next move is tried. This method always finds a solution if one exists. But it is brute force in nature. At every square there are up to eight options. In the 64 squares of an 8 × 8 board a wrong early choice may lead to a dead end noticed much later. The algorithm then has to undo, one by one, the millions of partial tours it has built up to that point.

Definition 3.12

A heuristic rests on a rule that makes a choice that looks "clever" at each step. In most cases it finds a good or near-optimal solution, but it does not guarantee this.

Heuristic rules are used in everyday life too. In the game Minesweeper, the player looks at the numbers on the open squares and picks the square that looks safest. This choice is correct most of the time, but sometimes it comes down to luck. A heuristic algorithm works in a similar way: it is fast and usually successful, but inputs on which it fails can be found.

3.11.3Warnsdorff's rule: a trace on a 5×5 board

The oldest known heuristic rule for the knight's tour is the one proposed by H. C. von Warnsdorff in 1823. The rule says that the next place the knight goes to should be the square whose onward count is nonzero but smallest. The onward count of a square is the number of empty squares that can be reached directly from that square.

The logic of the rule is to use up the hard-to-reach squares first. Corner and edge squares can be reached from only a few squares. If the knight moves away without visiting these squares, the paths by which it could come back fill up over time, and the square becomes unreachable. Going to the square with the smallest onward count visits these squares early and does not leave the dead end to the end. The squares in the middle, since they can be reached by many paths, cause no trouble even if they are left for last.

On a 5×5 board a tour starting from the upper left corner, that is, the square (0, 0), can be traced. In case of a tie, the order in the move table (0 to 7) decides. Table 3.15 gives the important steps of the tour. The candidates are the empty squares the knight can go to from that square; the number next to them is the onward count.

Table 3.15: Selected steps of the Warnsdorff tour on a 5×5 board.
Square no.PositionCandidates (onward count)Chosen
1(0, 0)(1, 2): 5, (2, 1): 5(1, 2), table order in a tie
2(1, 2)(0, 4): 1, (2, 4): 3, (3, 3): 3, (3, 1): 3, (2, 0): 3(0, 4)
3(0, 4)(2, 3): 5(2, 3)
4(2, 3)(4, 4): 1, (4, 2): 3, (3, 1): 2, (1, 1): 3, (0, 2): 3(4, 4)
5(4, 4)(3, 2): 5(3, 2)
9(0, 2)(1, 4): 2, (1, 0): 2(1, 4), table order in a tie
16(3, 4)(4, 2): 1, (2, 2): 4(4, 2)
24(1, 0)(2, 2): 0(2, 2), the last empty square

At the second square the effect of the rule is clearly seen. Among five candidates the upper right corner (0, 4) is chosen, because from there only one empty square can be reached. If the corner were not visited now, once the only path leading to it filled up, the corner would remain unreachable forever. At the fourth square the same logic makes the lower right corner, (4, 4), the choice. At the twenty-fourth square only one candidate remains and its onward count is 0. The "nonzero" condition of the rule does not apply here: this square is the last empty square of the board and the tour is completed with it.

155 1213333 11492032419215101382542118236111671217225
Figure 3.18: The Warnsdorff tour. (a) Square 1: two candidates, both with onward count 5. (b) Square 2: the corner (0, 4) has onward count 1 and is chosen. (c) The completed tour: the numbers are the order of visit; square 25 is the middle of the board.

In the completed tour 25 squares have been visited without ever going back. The order of visit, row by row, is: 1 14 9 20 3 / 24 19 2 15 10 / 13 8 25 4 21 / 18 23 6 11 16 / 7 12 17 22 5. The corners were used up at steps 1, 3, 5, and 7, that is, at the beginning of the tour; the middle square is left to the very end. This tour was produced by applying the rule in a small program, with the candidates and onward counts of every step, and compared with the values in the slides.

The cost of Warnsdorff's rule is very low. On an n × n board n2 moves are made. At each move at most 8 candidates are examined, and the onward count of each candidate is computed by looking at at most 8 neighbors. The work per move is constant (at most 8 × 8 = 64 square checks); the total work is O(n2). The memory is O(n2) for the board itself. Backtracking, on the other hand, tries an exponential number of partial tours in the worst case.

The rule does not always succeed. Depending on how ties are broken and on the starting square, the knight sometimes runs into a dead end. In that case Warnsdorff's rule can be combined with backtracking: the candidates are sorted by onward count and tried in that order, and one goes back at a dead end. Since the rule only determines the order of the attempts, the guarantee of a solution is preserved. In practice going back is very rarely needed.

3.12Complexity summary

The time and memory costs of the algorithms examined in these notes are given together in Table 3.16. The memory column is the total of the call stack and the extra structures the algorithm uses; the input itself is not counted.

Table 3.16: Complexity of the algorithms in the chapter.
AlgorithmTimeStack / extra memoryRemark
fact (recursive)Θ(n)O(n)the tail version can be reduced to O(1)
Binary search (iterative)O(log n)O(1)the array must be sorted
Binary search (recursive)O(log n)O(log n)tail recursion
HanoiΘ(2n)O(n)2n − 1 moves, optimal
PermutationsΘ(n · n!)O(n)n! arrangements
Subset generationΘ(n · 2n)O(n)2n subsets
SAT (brute force)O(2n · |F|)O(|F|)|F|: size of the formula tree
n-queens (backtracking)O(n!) upper boundO(n)pruning tries far fewer in practice
Knight's tour (Warnsdorff)O(n2)O(n2)heuristic; backtracking is exponential

The table falls into two groups. The algorithms in the first three rows are polynomial-time and run comfortably on large inputs. Most of the rest are exponential or factorial time. In Hanoi, permutation, and subset generation this cost is unavoidable, because the output itself has that size. In SAT and n-queens the output is small (an assignment or a placement), but the best known general methods for finding it take exponential time. Warnsdorff's rule is an example of reducing an exponential search to polynomial time with a heuristic choice; in return it gives up the guarantee of a solution.

The stack column has a notable regularity: in all the recursive algorithms the stack cost is the recursion depth. Even when the time is exponential, the depth is often n. That is why algorithms like Hanoi or permutation are limited not by stack overflow but by lack of time.

3.13Common mistakes

  1. Forgetting the base case or writing a step that never reaches it. The calls never stop and the program crashes with a stack overflow. Every recursive function must have a measure that decreases at every call and a base case that catches the smallest value of that measure.
  2. Not returning the result of the recursive call. If binsearch(...) is written and the returned value is thrown away, the function returns a wrong value even though it found the right answer. A tail call must be written as return binsearch(...).
  3. Using binary search on an unsorted array or a linked list. In an unsorted array the decision to discard half is wrong and an existing value may not be found. In a linked list reaching the middle takes linear time and the logarithmic gain is lost.
  4. Returning the value of the element found. The value can be confused with the error marker −1 and the position information is lost. Binary search must return the index.
  5. Forgetting to undo the choice in backtracking. If the second SWAP in permutations or pick[i] = 0 in subset generation is not written, sibling branches see a corrupted starting state. Some solutions repeat and some never appear.
  6. Running an exponential algorithm with a large n because "the machine is fast". Hanoi with 64 disks takes hundreds of billions of years, and permutations of 20 elements take decades. The order of growth must be computed before the algorithm is chosen.
  7. Not taking the stack cost of deep recursion into account. A recursion of depth n, if n is in the hundreds of thousands, fills a call stack of a few megabytes. Tail recursion is not a guarantee in C; in such cases a loop is preferred.
  8. Overlooking overflow. long is 32 bits on Windows and fact(13) overflows. In binary search (left + right) / 2 can overflow on very large arrays. Signed overflow is undefined behavior and can silently give wrong results.

3.14Summary

  • Recursion: a function calling itself with a smaller input. The base case is the smallest instance solved without recursion; the recursive step shrinks the problem and comes closer to the base case at every call.
  • The call stack: every call opens a stack frame that holds its parameters, local variables, and return address. A recursion of depth d uses O(d) extra memory; the same variable has a separate copy in each frame.
  • Recursion and loops: every recursion can be turned into a loop with an explicit stack. Recursion is close to the definition; a loop works with O(1) memory and without call cost.
  • Tail recursion: the recursive call is the last job; it is achieved with an accumulating parameter and the compiler can turn it into a jump. The C standard does not guarantee this optimization.
  • Binary search: in a sorted array it halves the range in every round and runs at most ⌊log2 n⌋ + 1 rounds: O(log n). It returns an index, and −1 means "absent". The iterative version uses O(1) and the recursive version O(log n) extra memory.
  • The towers of Hanoi: the solution of the recurrence h(n) = 2h(n − 1) + 1 is 2n − 1, and this number is optimal. The call tree is the history of the stack; the moves are ordered by an inorder traversal.
  • Permutations: n! arrangements are generated with swap, recursion, and swap back. The number of calls is about e · n! and the time is Θ(n · n!).
  • Backtracking: the partial solution is built step by step, a branch is pruned when a rule is broken, and the last choice is undone. Subset generation and n-queens are solved with this method; SAT was solved by brute force, trying all assignments.
  • SAT: an assignment that makes a logical formula true is sought. Brute force tries 2n assignments; the formula tree is built once and evaluated with a postorder traversal. The problem is NP-complete.
  • Heuristics: Warnsdorff's rule takes the knight at each step to the square with the smallest onward count, and the tour is mostly completed in O(n2) time without ever going back. One never stops looking for a better solution.

3.15Key terms

  • recursion
  • recursive
  • base case
  • call stack
  • stack frame
  • stack overflow
  • tail recursion
  • binary search
  • recurrence relation
  • permutation
  • swap
  • brute force
  • backtracking
  • subset
  • satisfiability (SAT)
  • postorder
  • n-queens problem
  • heuristic

3.16Test Yourself

  1. Which calls does fact_tail(5, 1) make and what does it return? With tail call optimization off, how many fact_tail frames are on the stack at most?

    Answer

    The calls are fact_tail(5, 1), fact_tail(4, 5), fact_tail(3, 20), fact_tail(2, 60), fact_tail(1, 120); the last call is the base case and returns 120. The 120 is passed upward without any operation. With the optimization off, five frames are on the stack at the same time; with it on, a single frame suffices.

  2. In the test array ({4, 13, 18, 19, 24, 27, 33, 36, 39, 40}), which middle indices does the iterative binsearch try when searching for 39, and how many rounds does it run?

    Answer

    The middle indices are 4 (24 < 39, left = 5), 7 (36 < 39, left = 8), and 8 (list[8] = 39). The function returns 8 in three rounds.

  3. How many calls does the recursive binsearch(list, 5, 0, 9) make on the same array? With which ranges is it called and what is the result?

    Answer

    Four calls are made: [0, 9] (middle 24), [0, 3] (middle 13), [0, 0] (middle 4), and [1, 0]. The last range is empty and −1 is returned; this value is passed back through three frames. At the deepest moment there are four binsearch frames on the stack.

  4. How many lines does hanoi(5, "A", "B", "C") print, how many times does the function call itself in total (including the first call), and how deep does the stack of hanoi frames get at most?

    Answer

    25 − 1 = 31 lines are printed. Since each call does exactly one printf, the number of calls is also 31. The depth equals the number of disks: 5 frames.

  5. For char s[] = "abcd";, what are lines 7–10 of the output of perm(s, 0, 4)? How many calls are made in total?

    Answer

    The first six lines begin with a (abcd, abdc, acbd, acdb, adcb, adbc). Then the array becomes bacd and lines 7–10 are bacd, badc, bcad, bcda. The number of calls is 1 + 4 + 12 + 24 + 24 = 65.

  6. How many lines does subsets("abcd", 4, 0, pick) print, and what is the fifth line? How many times is the function called in total?

    Answer

    24 = 16 lines are printed. The order goes {abcd}, {abc}, {abd}, {ab}, {acd}, …; the fifth line is {acd}. The call tree is a perfect binary tree with 5 levels: 25 − 1 = 31 calls.

  7. Which assignments (in the order x1x2x3) satisfy the formula (x1 ∨ ¬x2) ∧ x3? How many nodes does the formula tree have?

    Answer

    x3 = 1 is needed, and either x1 = 1 or x2 = 0: 001, 101, and 111. The tree has six nodes: the ∧ at the root, its left child ∨, the children of ∨, x1 and ¬, the right child of ¬, x2, and the right child of the root, x3.

  8. What is the first solution found by the call place(0, 6)? How many solutions are there in all on a 6×6 board?

    Answer

    The first solution is q = [1, 3, 5, 0, 2, 4]; 31 placements are made before it is reached. There are 4 solutions on a 6×6 board; despite there being 10 on 5×5, there are fewer on 6×6.

  9. Why can fact(13) give a wrong result on Windows? Up to which n does fact work correctly on 64-bit Linux?

    Answer

    On Windows long is 32 bits and its largest value is 2,147,483,647. 13! = 6,227,020,800 exceeds this limit; signed overflow is undefined behavior. On 64-bit Linux long is 64 bits; 20! ≈ 2.43·1018 fits, 21! ≈ 5.1·1019 does not. A correct result is obtained for n ≤ 20.

  10. How is a recursive function that finds the largest element of an array written? What is the stack depth?

    Answer

    The base case is n = 1 and the single element is returned; the recursive step finds the largest of the first n − 1 elements and compares it with the last element:

    int largest(int a[], int n) {
      int m;
      if (n == 1) return a[0];        /* base case */
      m = largest(a, n - 1);          /* largest of the first n-1 */
      return a[n - 1] > m ? a[n - 1] : m;
    }

    Each call decreases n by one; the depth is n and the stack cost is O(n). On the test array the function returns 40. The call is not a tail call, because a comparison is made after the return.

3.17Further reading

  • E. Horowitz, S. Sahni, and S. Anderson-Freed, Fundamentals of Data Structures in C (2nd ed.), Section 1.2: the source of the binary search, permutation, and SAT examples in these notes; it gives recursive algorithms and their analyses in the same C language.
  • R. Sedgewick, Algorithms in C, Chapter 5: describes recursion, divide and conquer, and call trees with detailed drawings.
  • T. H. Cormen et al., Introduction to Algorithms (3rd ed.), Chapters 4 and 34: methods for solving recurrence relations and the theory of NP-completeness, with the place of SAT in that theory.
  • N. Wirth, Algorithms + Data Structures = Programs (1976): a classic textbook that builds the general pattern of backtracking in Pascal and illustrates it with problems such as eight queens.

3.18References

  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009 (Chapter 4: recurrences; Chapter 34: NP-completeness, SAT).
  2. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Silicon Press, 2008 (Section 1.2: recursive algorithms).
  3. R. Sedgewick, Algorithms in C, Addison-Wesley (Chapter 5: recursion).
  4. N. Wirth, Algorithms + Data Structures = Programs, Prentice-Hall, 1976.

Related pages: Chapter 3 slides · © Sercan Külcü. All rights reserved.