Chapter 4: Recursion

4.1What is recursion?

Methods call other methods: main calls System.out.println, a sort calls a helper that swaps two elements. In recursion, the method called is the caller itself. Why doesn't it loop forever, how do we design one, and how does it run line by line?

4.1.1An everyday example

You are in a long line at a box office and want to know your position. You can't walk to the front without losing your place, and you can see only the person directly ahead.

So you ask them, “What's your position?” If they don't know, they ask the person ahead, and the question moves forward. The person at the front has nobody ahead and simply says “1.” The answer then travels back, each person adding 1 to what they hear (“you're 1st, so I'm 2nd”), until it reaches you.

The process in Figure 4.1 has three parts:

• Same question, shorter line. Everyone follows the same rule, each time for a line one person shorter.
• A stopping point. The person at the front answers without passing the question on; without them, it would travel forever.
• The way back. Each person adds their share, 1, as the answer returns. The real computation happens here.

A recursive method works the same way: it calls itself on a smaller input, answers the smallest input directly, and builds its answer from the smaller one on the way back. Each person is one call, and just as each person remembers something of their own, each call has its own variables.

4.1.2Base case and recursive step

The classic example is the factorial: n! is the product of the integers from 1 to n, so 4! = 4 · 3 · 2 · 1 = 24. Since 4! contains 3 · 2 · 1 = 3!, we have 4! = 4 · 3!, and likewise for every n > 1. The factorial can thus be defined in terms of itself:

n! = 1 (if n ≤ 1)  ·  n! = n · (n − 1)! (if n > 1)

The first line answers the smallest inputs outright; the second builds a large answer from a smaller one. For 4! we apply the second line three times, then the first: 4! = 4 · 3! = 4 · 3 · 2! = 4 · 3 · 2 · 1! = 4 · 3 · 2 · 1 = 24.

The definition translates into Java almost word for word:

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

// in main:
System.out.println(factorial(4));

Line 2 catches the base case and returns 1. The last return is the recursive step: factorial(n - 1) runs the same method on a smaller input, and its result is multiplied by n. The call in main prints 24.

If every call makes another call, the chain must break somewhere, and the base case is where. Without it the calls never end; each takes some memory, memory runs out, and Java stops the program with a StackOverflowError (Section 4.2.3).

Figure 4.2 shows recursion's two directions. Going down, nothing is multiplied; each call just remembers its n and waits. Coming up, the multiplications happen: 2 · 1 = 2, 3 · 2 = 6, 4 · 6 = 24.

At the deepest point four calls of factorial sit in memory, each with its own n: 4, 3, 2, 1. While factorial(1) runs with n = 1, the n of factorial(4) is still 4, ready for its multiplication. Each call gets its own area of memory, a frame (Section 4.2).

4.1.3Thinking recursively

Picturing the whole chain of calls is exhausting and usually unnecessary. Ask three questions instead:

1. Base case: What is the smallest input, and its answer?
2. Reduction: How does the problem reduce to a smaller one of the same kind? Typically to n − 1, n / 2, or index i + 1.
3. Combination: How is the larger answer built from the smaller one?

For the third question we assume the smaller problem is solved correctly. Writing factorial(n), we don't ask how factorial(n - 1) works; we trust it to return (n − 1)! and think only about the last step: multiply by n.

This is no trick; it is mathematical induction. To prove a statement for every natural number, show it for the smallest one, and show that if it holds for n − 1 it holds for n. Then it holds for 1, hence 2, hence 3, without a break. Likewise, if the base case is right and each step builds a correct answer from a correct smaller one, the method is correct for every input.

One more condition: every recursive call must move the input closer to the base case. If the input doesn't shrink, or skips past the base case, the chain never reaches its start.

Take a simple method: countdown(n) prints n down to 1, one per line, then “Done”.

The three answers turn directly into code:

void countdown(int n) {
  if (n == 0) {     // base case
    System.out.println("Done");
    return;
  }
  System.out.println(n);
  countdown(n - 1); // recursive step
}
countdown(3);       // in main

Lines 2–5 are the base case: print “Done” and leave. The return matters; without it, execution would fall through to line 6, print 0, and call countdown(-1). Line 6 prints n; line 7, the recursive step, solves the smaller problem.

4.1.4Code trace: countdown(3)

The surest way to understand recursion is to trace a small input line by line. Here main calls countdown(3); at each step we note the running call, the waiting ones, and the output.

Here cd abbreviates countdown. The Calls column grows in steps 2–5 and shrinks in steps 6–9; at its longest, 5 calls are in memory, counting main. In total countdown is called 4 times: n = 3, 2, 1, 0.

Nothing is printed on the way back (steps 6–9): each call returns from line 7 at the end of the method with nothing left to do. All printing happens on the way down, because the print comes before the call. Swap the two lines and the output changes.

4.1.5Work before or after the call?

Whether work comes before or after the recursive call decides the result. These two methods differ only in where the print goes.

void countdown2(int n) {
  if (n == 0) return;
  System.out.print(n + " ");
  countdown2(n - 1);   // call after
}

void countUp(int n) {
  if (n == 0) return;
  countUp(n - 1);      // call first
  System.out.print(n + " ");
}

countdown2(3) prints 3 2 1: each call prints its number before moving on, so printing happens as the calls go down.

countUp(3) prints 1 2 3. Each call first makes the recursive call and waits: countUp(3) waits for countUp(2), which waits for countUp(1), which calls countUp(0), a base case that returns at once. So countUp(1) prints first, then countUp(2) resumes and prints 2, then countUp(3) prints 3. Printing happens as the calls come back.

The first call to finish is the last to start, so work after the call runs in reverse order of the calls. That pending work waits in memory with its call until its turn. This is what lets us print a singly linked list backward (4.8.3) and move the second half of the disks in the Towers of Hanoi (4.5.3).

4.2The call stack

Several calls of one method can sit in memory at once, each with its own variables. Where does Java keep them, and in what order? Once that is clear, both the output and the memory cost of a recursive method are easy to find.

4.2.1Frames and the call stack

Each method call gets a small area of memory holding its parameters, its local variables, and the place to resume when it finishes, the return address. When factorial(3) calls factorial(2), the return address is “where n * … is computed.”

The call stack follows the rule of the stack data structure: last in, first out, or LIFO. Method calls behave this way by nature: if main calls f and f calls g, then g finishes first, then f, then main.

Three properties of the call stack explain recursion:

• Only the top frame runs. Each frame below waits for the call just above it.
• One method can have several frames on the stack. That is recursion, and each frame has its own n.
• A finished call's frame is removed. Its return value goes to the caller, now on top, which resumes at the return address.

Figure 4.4 also shows recursion's memory cost. Four frames are on the stack at once; for factorial(n) there are n + 1, counting main. Each frame has a fixed size, so memory is O(n).

In general, a recursive method's memory cost depends not on the total number of calls but on the most frames on the stack at once — the length of the deepest call chain. In binary recursion the two numbers differ enormously (Section 4.6.5).

4.2.2Code trace: factorial(4)

Now we trace factorial(4) (Section 4.1.2), watching the call stack at each step:

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

// in main:
System.out.println(factorial(4));

Two lines matter in each call. Line 2 separates out the base case. Line 4 calls factorial(n - 1), multiplies the result by n, and returns it; until the call returns, the frame holds the multiplication as unfinished work.

Steps 2–8 are the descent: each pushes a frame, and nothing is multiplied. Step 9 reaches the base case and produces the first value, 1. Steps 10–13 are the return: each pops a frame, and the frame below completes its multiplication. Emptying the stack this way is called unwinding.

The cost is easy to read off: 4 calls, each doing constant work (a comparison, at most one multiplication, a return), so time is O(n). At its deepest the stack holds 4 frames plus main, so memory is O(n) too. A loop needs only O(1) memory; the recursive version pays for short code that mirrors the definition.

4.2.3Stack overflow

The call stack is finite. The JVM (Java Virtual Machine) gives each thread a fixed amount of stack memory, which depends on the JVM and operating system and can be set with the -Xss option. Every frame uses some of it, so with default settings recursion depth is usually limited to a few thousand to a few tens of thousands of calls.

The following method adds up the numbers from 1 to n:

long sumTo(int n) {        // 1 + 2 + … + n
  if (n == 0) return 0;
  return n + sumTo(n - 1);
}
// in main:
System.out.println(sumTo(10_000));   // 50005000
System.out.println(sumTo(1_000_000)); // error

sumTo(10_000) prints 50005000; its 10,001 frames fit in the default stack. sumTo(1_000_000) fills the stack before reaching the base case — there is no room for a million frames — and Java stops with:

Exception in thread "main"
  java.lang.StackOverflowError
    at Example.sumTo(Example.java:3)
    at Example.sumTo(Example.java:3)
    …

The lines below the message, a dump of the call stack at the failure, form a stack trace. One line, Example.sumTo(Example.java:3), repeated thousands of times points straight at recursion.

For scale: a method that did nothing but call itself reached a depth of about 21,800 with default settings, and sumTo, with a slightly larger frame, less. The exact value varies by machine and doesn't matter. What matters is that a limit exists and its order of magnitude: tens of thousands is usually fine; millions almost always overflow.

The sum needs no recursion. A loop takes O(n) time and O(1) memory, and the formula 1 + 2 + … + n = n(n + 1)/2 takes O(1) time. For n = 1,000,000 that is 500,000,500,000, too big for an int — hence the long.

4.2.4Forgetting the base case

Stack overflow usually comes not from a huge input but from a faulty base case. Three typical faults give the same result for different reasons.

1. No base case.

int f(int n) {
  return n * f(n - 1);
}

Every call calls again. For f(3) the inputs run 3, 2, 1, 0, −1, …; nothing returns, and the stack fills.

2. The base case can't be reached.

if (n == 1) return 1;
return n * f(n - 1);

The base case catches only n = 1. For f(0) the inputs run 0, −1, −2, … and never reach 1. The test n <= 1 fixes this: f(0) returns 1 at once. The same happens when the input drops by 2: n * f(n - 2) with base case n == 1 stops for odd numbers but runs 2, 0, −2, … for even ones.

3. The problem doesn't shrink.

if (n <= 1) return 1;
return n * f(n);

The base case is right, but the step doesn't shrink the input: f(n) calls f(n). f(1) works; f(2) calls f(2) forever, never nearer the base case.

The rule: every possible input, including 0 and negatives, must reach a base case in finitely many steps. After writing a recursive method, ask which inputs end directly in a base case, and whether every other input moves toward one with each call. Unless both answers are “yes,” some inputs overflow.

4.3Linear recursion

In every example so far, each call made at most one recursive call, so the calls form a straight, unbranched chain. This section covers three such problems — summing an array, reversing an array, computing powers — and the last shows how shortening the chain changes the cost.

4.3.1Definition and summing an array

factorial, countdown, and sumTo are linear, as are array sum and reversal, powers, and the length of a linked list.

To sum an integer array recursively, we first need a form that can shrink: instead of “the sum of the array,” take “the sum of the first n elements,” so n can be reduced. Then the three questions of Section 4.1.3 apply:

• Base case: for n = 0 the part is empty and sums to 0.
• Reduction: use the sum of the first n − 1 elements.
• Combination: add the last element, a[n - 1].

Indices start at 0, so the first n elements are a[0], …, a[n - 1], and the last is a[n - 1], not a[n]:

int sum(int[] a, int n) {      // sum of the first n elements
  if (n == 0)
    return 0;                   // base case
  return sum(a, n - 1) + a[n - 1];
}

The second parameter says which part we are working on. The array is never changed or copied: Java passes arrays by reference, so every frame's a refers to the same array, and each call carries just a reference and an integer. The first call is sum(a, a.length).

Figure 4.6 is recursive thinking in a nutshell: to write sum(a, 4) you needn't know how sum(a, 3) got 13; you trust it and add the last element.

4.3.2Code trace: sum(a, 4)

int sum(int[] a, int n) {      // sum of the first n elements
  if (n == 0)
    return 0;                   // base case
  return sum(a, n - 1) + a[n - 1];
}
// in main:
int[] a = {4, 3, 6, 2};
System.out.println(sum(a, 4));

Each call first asks for the sum of a smaller part and leaves its own element for the way back.

The stack is deepest at step 5: main and 5 sum frames. The additions happen on the way back, from a[0] to a[3], because the addition follows the call, as in countUp (4.1.5).

Cost: n elements take n + 1 calls, each doing a comparison, an addition, and an array access, so time is O(n); the stack reaches n + 1 frames (plus main), so memory is O(n).

The same pattern handles other properties, such as the largest element. Its base case is n = 1, where the answer is a[0] (an empty part has no largest element); the step compares the largest of the first n − 1 with the last: Math.max(largest(a, n - 1), a[n - 1]). Again O(n) time and O(n) stack.

4.3.3Reversing an array

To reverse an array in place, swap the two end elements, then reverse the part between them, which is two elements shorter.

The part is given by its first and last indices: a[i..j] is i through j, inclusive. The first call is reverse(a, 0, n - 1).

• Base case: if i >= j, 0 or 1 elements remain, and such a part is its own reverse.
• Reduction and combination: swap a[i] and a[j], then reverse the inner part a[i+1..j-1].

void reverse(int[] a, int i, int j) {
  if (i >= j)
    return;                    // base: 0 or 1 elements
  int t = a[i]; a[i] = a[j]; a[j] = t;  // the ends
  reverse(a, i + 1, j - 1);    // the inner part
}
// in main:
int[] a = {2, 7, 4, 9, 1, 6};
reverse(a, 0, a.length - 1);

Two things are new. The method returns nothing (void); it changes the array itself, and every call sees the same array. And the work comes before the call, so nothing is left for the way back.

Each call shortens the part by 2, so n elements need ⌊n/2⌋ swaps (⌊ ⌋ rounds down), plus one final call that hits the base case: ⌊n/2⌋ + 1 calls. Arrays of 6 and of 7 elements both take 3 swaps and 4 calls (the middle of 7 stays put). Time and stack memory are O(n).

4.3.4Code trace: reverse(a, 0, 5)

Tracing reverse(a, 0, 5) on a = {2, 7, 4, 9, 1, 6}, with each call's i, j, and the array after its swap:

During call 4 the stack holds main and 4 reverse frames. Then calls 4, 3, 2, 1 return with nothing left to do, since the recursive call is the last line. Result: 6 1 9 4 7 2, 3 swaps, 4 calls.

4.3.5Powers, slow and fast

xⁿ is x multiplied by itself n times, which gives a recursion at once: xⁿ = x · xⁿ⁻¹, x⁰ = 1.

long power(long x, int n) {
  if (n == 0) return 1;
  return x * power(x, n - 1);
}

Correct but slow: n drops by only 1 per call, so power(x, n) makes n + 1 calls, with O(n) time and stack. For n = 1,000,000 the stack overflows.

A faster way uses x¹⁰ = (x⁵)²: compute x⁵ once and square it, halving the exponent. An odd exponent sets one x aside: x⁵ = x · (x²)². In general:

xⁿ = (x^n/2)² (n even)  ·  xⁿ = x · (x^(n−1)/2)² (n odd)

Java's integer division rounds down, so for odd n, n / 2 is (n − 1)/2, and both cases use n / 2. For example:

2¹⁰ = (2⁵)²,   2⁵ = 2 · (2²)²,   2² = (2¹)²,   2¹ = 2 · (2⁰)²

long fastPower(long x, int n) {
  if (n == 0) return 1;           // base case
  long y = fastPower(x, n / 2);   // x^(n/2)
  if (n % 2 == 0) return y * y;   // n even
  return x * y * y;               // n odd
}
// in main:
System.out.println(fastPower(2, 10));

The key is y on line 3: x^n/2 is computed once and squared as y * y. Writing fastPower(x, n / 2) * fastPower(x, n / 2) would compute it twice and lose the gain (see 4.4.3). Line 4 handles an even exponent; line 5, reached only for an odd one, multiplies by one more x.

Each call halves n, and ⌊log₂ n⌋ halvings bring it to 1; adding the calls for 1 and for the base case 0 gives ⌊log₂ n⌋ + 2 calls (for n ≥ 1). Time and stack are O(log n).

Table 4.5 makes the two growth rates concrete. When n grows a thousandfold, power makes a thousand times as many calls, fastPower only about 10 more. For an exponent of a million, power overflows while fastPower needs 21 frames. Shrinking by a constant factor, not a constant amount, makes the difference.

4.3.6Code trace: fastPower(2, 10)

On the way down only the exponent is halved; every multiplication happens on the way back.

The result, 1024, takes 5 calls; power(2, 10) would take 11. The returned values 1, 2, 4, 32, 1024 are 2⁰, 2¹, 2², 2⁵, 2¹⁰, and the exponents 0, 1, 2, 5, 10 are the prefixes of 1010, 10 in binary (1, 10, 101, 1010); the odd-exponent steps match its 1 digits.

4.4Binary recursion

When a call calls itself twice, two branches grow from each call and the calls form a tree. The best-known example is Fibonacci; this section covers what its tree costs and how to avoid that cost. Binary search, at the end, also has two calls in its code, but its calls form a chain.

4.4.1Fibonacci numbers

The Fibonacci sequence starts 0, 1, and each later number is the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … It turns up in nature (sunflower seeds, leaf arrangements) and in computer science (the analysis of some data structures).

The definition is recursive by nature:

F(0) = 0,   F(1) = 1,   F(n) = F(n − 1) + F(n − 2) (n ≥ 2)

Two base cases are needed because the step reaches back two terms; with only F(0), F(1) = F(0) + F(−1) would be undefined. In code:

int fib(int n) {
  if (n <= 1) return n;    // base case
  return fib(n - 1) + fib(n - 2);
}

Line 2 catches both base cases, since F(n) = n for n ≤ 1. Line 3 makes two recursive calls and adds the results.

The call tree is the basic tool for analyzing binary recursion: its node count is the total number of calls, and its depth the most frames on the stack at once. In the Fibonacci tree the same value is computed many times, and this repetition sets the cost of fib.

4.4.2Code trace: the call tree of fib(4)

int fib(int n) {
  if (n <= 1) return n;    // base case
  return fib(n - 1) + fib(n - 2);
}
// in main:
System.out.println(fib(4));

The rule to remember: Java evaluates left to right, so in fib(n - 1) + fib(n - 2) the call fib(n - 1) finishes completely before fib(n - 2) starts.

F(4) = 3 takes 9 calls: one each for fib(4) and fib(3), two for fib(2), three for fib(1), two for fib(0). Call 7 is pure waste: call 3 already found fib(2), but nothing stored it.

The tree also gives the memory cost: the frames on the stack are the path from the root to the running node. The longest path, fib(4) → fib(3) → fib(2) → fib(1), has 4 frames (5 with main); despite 9 calls, the stack never holds more.

4.4.3What recursion costs

A recursive method's time is its total work. If each call does constant work, the total is proportional to the number of calls, so finding the cost means counting calls.

For factorial this is easy. Let T(n) be the work of factorial(n) and c a call's own constant work; then T(n) = T(n − 1) + c. The chain is n calls long, so time and stack are O(n). Such equations are recurrence relations (Section 4.6).

fib is different: each call makes two, and the same subproblems are solved again and again.

int fib(int n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

The call count grows very fast. Let C(n) be the calls made by fib(n). For n ≤ 1, C(0) = C(1) = 1; otherwise we count the call itself plus both subtrees: C(n) = C(n − 1) + C(n − 2) + 1. This resembles the Fibonacci recurrence, and so does its solution.

For fib(4) this gives 2 · F(5) − 1 = 9, matching the trace. Fibonacci numbers grow by a factor of about 1.6 per step (approaching the golden ratio φ ≈ 1.618), so the calls grow like 1.6ⁿ: exponential growth, the work multiplying by about 1.6 each time n grows by 1.

Memory is still O(n): however large the tree, the stack holds one root-to-node path, at most n long. fib's problem is time, not memory.

4.4.4Avoiding repeated work

Numbers make exponential growth tangible. Table 4.8 gives fib(n) and its call count for a few n.

fib(40) makes over 331 million calls for just 41 distinct subproblems, fib(0) to fib(40). Nearly every call re-solves a solved problem. There are two cures.

1. Memoization. Store each value in an array the first time it is computed, and read it from there when it is needed again.

long[] memo = new long[91];     // 0: not computed yet
long fibMemo(int n) {
  if (n <= 1) return n;
  if (memo[n] != 0) return memo[n];
  memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
  return memo[n];
}

memo holds F(0) to F(90), all within long range (which ends at F(92)). Cells start at 0, meaning “not computed”; this is safe since F(n) ≠ 0 for n ≥ 2. After the base case, the method returns a stored value if there is one; otherwise it makes the two calls, stores the result in memo[n], and returns it.

fibMemo(40) makes 79 calls. The left call, fibMemo(n - 1), computes and stores every value up to n − 1, so the right call, fibMemo(n - 2), finds its value ready and returns at once. Each k ≥ 2 thus has one computing call and one quick call on its right (or a base case like fibMemo(0)), plus the bottom fibMemo(1): 2n − 1 calls, 79 for n = 40. Time is O(n); stack depth and the memo array are O(n) too.

2. A loop. Computing the sequence from the front needs only the last two terms at each step.

long fibLoop(int n) {
  long a = 0, b = 1;              // F(0), F(1)
  for (int i = 0; i < n; i++) {
    long t = a + b;  a = b;  b = t;
  }
  return a;
}

a and b hold two consecutive terms, starting at F(0) and F(1). Each iteration computes the next term, t = a + b, and slides the window forward; after n iterations a = F(n).

After six iterations it returns a = 8 = F(6). The loop takes O(n) time and O(1) memory, opens no frames, and can't overflow the stack: the best choice for Fibonacci.

4.4.5Recursive binary search

To find x in a sorted array, look at the middle element. If it equals x, done. If x is smaller, it can only be in the left half; if larger, only in the right half. Either way the same search repeats on half the array — a naturally recursive algorithm.

The part searched is a[lo..hi], with two base cases:

• Empty range (lo > hi): x is not in the array; return −1.
• Middle element is x: return the middle index.

int binarySearch(int[] a, int x, int lo, int hi) {
  if (lo > hi) return -1;       // base: empty range
  int mid = (lo + hi) / 2;
  if (a[mid] == x) return mid;  // base: found
  if (x < a[mid])
    return binarySearch(a, x, lo, mid - 1); // left half
  return binarySearch(a, x, mid + 1, hi);   // right half
}
System.out.println(binarySearch(a, 23, 0, 9));

The code has two recursive calls (lines 6 and 7), but each call makes only one: left if the if holds, right otherwise. The calls form a chain, not a tree, so binary search is linear recursion; it appears here to contrast the two shapes.

The range halves each call: T(n) = T(n/2) + c, solved by O(log n) time and stack (4.6.3). Ten elements take at most 5 calls, 10⁶ at most 21, counting the final call on an empty range.

4.4.6Code trace: binarySearch(a, 23, 0, 9)

Search a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} for x = 23 with binarySearch(a, 23, 0, 9).

Call 3 returns 5 from the base case; calls 2 and 1 pass it straight on, computing nothing new. The answer takes 3 calls as the range shrinks from 10 to 5 to 2 elements.

4.5The Towers of Hanoi and backtracking

The Fibonacci tree showed recursion used badly, repeating the same work. Here too the call tree grows exponentially, but every node does different, necessary work: in Hanoi each node is a disk move, in backtracking each leaf is a wanted subset or permutation. The output itself is exponential, so the cost is unavoidable, and recursion is the clearest way to produce it.

4.5.1The Towers of Hanoi

The Towers of Hanoi is a classic puzzle. Rod A holds n disks, largest at the bottom; the goal is to move them all to rod C, using rod B as a helper, under two rules:

• Each move takes one disk, the top disk of some rod.
• A disk may be placed only on a larger disk or on an empty rod.

Move by move, the puzzle is hard; recursively, it nearly solves itself. Consider the largest disk. At some point it moves from A to C, and at that moment A can hold nothing above it and C must be empty, so the other n − 1 disks must all be on B. Hence a three-step plan:

1. Move the top n − 1 disks from A to B (using C as the helper).
2. Move the largest disk from A to C.
3. Move the n − 1 disks from B to C (using A as the helper).

Steps 1 and 3 are the same problem with n − 1 disks and the rods in different roles. The largest disk is never disturbed meanwhile, and any disk may sit on it, so for the smaller problem it might as well not exist. The base case, one disk, moves straight from source to target.

4.5.2Seven moves for three disks

For three disks: 2 disks from A to B (3 moves), disk 3 from A to C, then 2 disks from B to C (3 moves) — 7 moves in all.

Figure 4.17 shows the plan's three steps: moves 1–3 gather the small disks on B, move 4 moves the largest disk, and moves 5–7 stack the small disks on it at C. Moves 1–3 and 5–7 are the same job, “move 2 disks,” with different rods.

Let T(n) be the moves needed for n disks. Then T(1) = 1 and, from the plan, T(n) = 2T(n − 1) + 1, giving T(2) = 3, T(3) = 7, T(4) = 15 — each one less than a power of two.

2ⁿ − 1 grows fast: 20 disks need 1,048,575 moves. Legend has temple priests moving a 64-disk tower, the world ending when they finish. That is about 1.8 · 10¹⁹ moves, some 585 billion years at one move per second.

4.5.3Code trace: hanoi(3, 'A', 'B', 'C')

The plan goes straight into Java, with parameters n (disks), from (source), via (helper), and to (target).

void hanoi(int n, char from, char via, char to) {
  if (n == 1) {
    System.out.println("1: " + from + "→" + to);
    return;
  }
  hanoi(n - 1, from, to, via);
  System.out.println(n + ": " + from + "→" + to);
  hanoi(n - 1, via, from, to);
}
// in main:
hanoi(3, 'A', 'B', 'C');

Lines 2–5, the base case, move one disk and print, say, “1: A→C”, the number being the disk. Line 6 is step 1, moving n − 1 disks to the helper; note that target and helper swap roles: hanoi(n - 1, from, to, via). Line 7 moves disk n. Line 8 is step 3, moving n − 1 disks from the helper to the target with the source as helper: hanoi(n - 1, via, from, to).

The seven lines printed are the seven moves of Figure 4.17. The call tree has 7 nodes — one H(3,…), two H(2,…), four H(1,…) — each printing one line, so calls equal moves: 2³ − 1 = 7.

Time is O(2ⁿ), since each of the 2ⁿ − 1 calls does constant work. Memory is O(n): at most n hanoi frames (for n, …, 1 disks), n + 1 with main.

There is another pattern: disk 1 moves on every odd-numbered move, 2ⁿ⁻¹ times in all, and in general disk k moves 2^n−k times, the largest just once — the node counts of the tree's levels. In the Towers of Hanoi simulator you can solve the puzzle by hand with 1–6 disks or step through the shortest solution, and compare your move count with the minimum (2ⁿ − 1; 63 for 6 disks). Each tower acts as a stack: only the top disk can be taken.

4.5.4Backtracking

Some answers are the result of a series of choices: which way to turn at each junction of a maze, which digit to put in each empty sudoku square, which elements of a set to pick. The general method for such problems is backtracking.

Why undo? The solution under construction (a list, say) is usually one object shared by all calls. A change left in place by one branch would make the next branch start from the wrong state; undoing it lets every branch start from the same state.

As in Hanoi, each call makes several recursive calls. The call tree of all choices tried is a decision tree, each root-to-leaf path one sequence of choices. Classic examples: listing subsets or permutations, finding a path through a maze, sudoku, and the n-queens problem (placing n queens on a chessboard so none attacks another).

4.5.5Listing subsets

To print all subsets of a set — {1, 2, 3} has 8: {1, 2, 3}, {1, 2}, {1, 3}, {1}, {2, 3}, {2}, {3}, and the empty set — decide for each element in turn whether it is in. Each element has two options, independent of the rest, so n elements give 2ⁿ decision sequences, that is, 2ⁿ subsets.

The tree becomes a method with three parameters: the array a, the index i to decide, and the list s of elements chosen so far.

void subsets(int[] a, int i, List<Integer> s) {
  if (i == a.length) {              // base case
    System.out.print(s + " "); return;
  }
  s.add(a[i]);                      // take a[i]
  subsets(a, i + 1, s);
  s.remove(s.size() - 1);           // undo
  subsets(a, i + 1, s);             // try without a[i]
}
// in main:
subsets(new int[]{1, 2, 3}, 0, new ArrayList<>());

Each part matches the decision tree:

• Base case (lines 2–4): i == a.length means every element is decided; we are at a leaf, and s is printed.
• Left branch (lines 5–6): add a[i] and decide the next element.
• Undo (line 7): remove a[i], restoring the list to its state at the call's start.
• Right branch (line 8): go on without a[i].

s.remove(s.size() - 1) removes the last element by index, which is always this call's a[i], since subcalls undo their own additions. s.remove(a[i]) on a List<Integer> is a trap: a[i] is an int, so Java takes it as an index and removes the wrong element.

The decision tree is a complete binary tree with 2^k nodes at level k (k = 0, …, n): 2ⁿ⁺¹ − 1 calls in all, 15 for n = 3. Printing at each leaf costs O(n), so time is O(n · 2ⁿ); the stack depth is n + 1, so memory is O(n).

4.5.6Code trace: subsets of {1, 2, 3}

Table 4.12 lists the 15 calls of subsets(new int[]{1, 2, 3}, 0, new ArrayList<>()) in starting order, with each call's i, its s on entry, and its first action.

The output, [1, 2, 3] [1, 2] [1, 3] [1] [2, 3] [2] [3] [], lists the leaves left to right, since each call explores “take” fully before “skip.” Swapping the branches reverses the order but not the subsets.

The stack holds at most main and 4 subsets frames, a root-to-leaf path (i = 0, 1, 2, 3).

4.5.7Listing permutations

To print every ordering, or permutation, of some letters — A, B, C have 6: ABC, ACB, BAC, BCA, CAB, CBA — backtracking picks one of 3 letters first, one of the remaining 2 next, and the last one third: 3 · 2 · 1 = 3! = 6.

void perm(char[] ch, boolean[] used, StringBuilder s) {
  if (s.length() == ch.length) { // base case
    System.out.print(s + " "); return;
  }
  for (int k = 0; k < ch.length; k++) {
    if (used[k]) continue;       // letter already used
    used[k] = true; s.append(ch[k]); // choose
    perm(ch, used, s);
    used[k] = false;             // undo
    s.deleteCharAt(s.length() - 1);
  }
}

ch holds the letters, used[k] records whether ch[k] is already in the word, and s is the word being built. When the word has every letter (line 2), it is printed. Otherwise each unused letter is tried: mark and append it (line 7), recurse on the rest (line 8), then clear the mark and remove the letter (lines 9–10).

A call makes one recursive call per remaining letter — 3 at the root, then 2, then 1 — so the count varies: multiple recursion. n letters give n! leaves and at most about 2.72 · n! nodes (16 nodes for n = 3). Each node runs an O(n) loop and each leaf prints n letters, so time is O(n · n!); stack depth is n + 1, memory O(n).

4.6Recurrence relations

So far we have counted calls one by one, which works for small inputs but gives no general rule. A better way is to write the cost as an equation and solve it with the call tree. Every method in this chapter fits one of five equation types (Table 4.13).

4.6.1What is a recurrence relation?

Let T(n) be a method's total work on input size n: its own work plus that of its recursive calls. The latter is the same method's cost on smaller inputs, so T(n) is written in terms of smaller values of T.

To write one, answer three questions about the method:

1. What does the base case cost? Usually a constant, written c.
2. How many recursive calls are made, and how much smaller are their inputs?
3. How much work does the method itself do outside the calls?

fastPower, for example, makes one call on n / 2 and otherwise does a comparison and at most two multiplications, so T(n) = T(n/2) + c. Table 4.13 lists the chapter's recurrences.

The easiest solution method is the call tree. Each node does c work, so T(n) ≈ c · (number of calls): solving the recurrence means counting nodes.

4.6.2T(n) = T(n − 1) + c

This is linear recursion shrinking the input by 1. We solve it by substituting the recurrence into itself, called unrolling:

T(n) = T(n − 1) + c
     = T(n − 2) + 2c
     = T(n − 3) + 3c
     …
     = T(0) + n · c
     = c + n · c   →  O(n)

Each step adds a c and lowers n by 1, so after k steps T(n) = T(n − k) + k · c; at k = n, T(n) = c + n · c, which is O(n).

The tree is a chain (Figure 4.23) of n + 1 calls, all on the stack at once, since the first can't finish before the last returns; memory is O(n). factorial, sum, countdown, slow powers, and list length fit here.

For reverse the input drops by 2: T(n) = T(n − 2) + c, which unrolls to T(n − 2k) + k · c and bottoms out after about n/2 steps. Half the calls, but still O(n): shrinking by any constant amount gives a linear chain.

4.6.3T(n) = T(n/2) + c

This is recursion that halves the input. Unrolling:

T(n) = T(n/2) + c
     = T(n/4) + 2c
     = T(n/8) + 3c
     …
     = T(n/2ᵏ) + k · c

After k steps the input is n/2^k, which reaches 1 when 2^k = n, that is, k = log₂ n. So T(n) = T(1) + c · log₂ n, which is O(log n).

The logarithm here answers one question: how many halvings take n to 1? 16 → 8 → 4 → 2 → 1 takes 4, and log₂ 16 = 4. For other n, integer division rounds down, giving ⌊log₂ n⌋ halvings.

A thousandfold larger input (1,024 to about a million) adds only about 10 calls: logarithmic growth is that slow. The chain is log n deep, so memory is O(log n). Binary search and fast exponentiation fit here. (A base case of 0 or an empty range adds one call, which is why fastPower makes ⌊log₂ n⌋ + 2.)

4.6.4T(n) = 2T(n − 1) + c

Each call makes two calls of size n − 1, so calls double at each level: 1 at the root, 2 at level 1, 2^k at level k. With base case n = 1, levels run from 0 to n − 1.

1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ − 1 calls → O(2ⁿ)

Consecutive powers of two add up to one less than the next power: 1 + 2 + 4 + 8 = 15 = 16 − 1. In binary it is obvious: 1111 is 15, and adding 1 gives 10000, 16.

Hanoi fits exactly: 2ⁿ − 1 moves, 1,048,575 for n = 20, about 1.8 · 10¹⁹ for n = 64.

For fib, T(n) = T(n − 1) + T(n − 2) + c ≤ 2T(n − 1) + c, since T(n − 2) ≤ T(n − 1); so O(2ⁿ) is an upper bound. The true growth, about 1.6ⁿ (4.4.3), is slower but still exponential — hence 331 million calls for n = 40.

However large the tree, its depth is only n, so the stack holds at most n frames: exponential time, linear memory.

4.6.5Space: the deepest chain of calls

Time comes from all the nodes of the call tree; space depends on something else. A call finishes completely before its sibling starts — in fib(4), fib(2) waits for the whole subtree of fib(3) — so the stack holds only one root-to-node path. Finished calls have no frames left, and unstarted ones none yet.

Memory = deepest chain of calls × frame size

The depth decides, not the call count: fib(4) makes 9 calls but never has more than 4 fib frames (plus main).

Table 4.15 shows a striking contrast. fib(40) makes over 300 million calls, a noticeable wait, yet its stack never exceeds 40 frames. sumTo(1_000_000) makes only a million calls, no problem for time, but its million-frame chain overflows the stack (4.2.3). Time and memory problems in recursion are independent; check each separately.

The subsets time is not just its 2ⁿ⁺¹ − 1 calls: each of the 2ⁿ leaves also prints up to n elements, giving O(n · 2ⁿ).

4.7Tail recursion

Most recursive methods work on the way back — factorial multiplies, sum adds, countUp prints — so their frames must wait for the subcalls. Methods with nothing to do on the way back are special: they convert easily into loops.

4.7.1What is tail recursion?

factorial is not tail recursive:

int factorial(int n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
  // the multiplication happens after the call returns
}

The call looks last, but after it returns, its result must still be multiplied by n; the multiplication is last.

To make it tail recursive, the multiplication must come before the call, by carrying the partial result down in a parameter called an accumulator, conventionally acc.

int factTail(int n, int acc) {
  if (n <= 1) return acc;
  return factTail(n - 1, n * acc);
  // last step: the call (multiplication first)
}

acc holds the product so far: each call multiplies in its n and passes the result on, so at the base case acc is the answer. The first call is factTail(n, 1), since nothing has been multiplied yet and 1 is the multiplicative identity.

The chapter's methods split into two groups:

• Tail recursive: countdown (prints before the call), reverse (swaps before the call), binarySearch (passes the returned value on unchanged), factTail.
• Not tail recursive: factorial and sum (multiply or add after the call), fib (adds the results of two calls), countUp (prints after the call).

4.7.2Code trace: factTail(4, 1)

int factTail(int n, int acc) {
  if (n <= 1) return acc;   // base case
  return factTail(n - 1, n * acc);  // last step
}
// in main:
System.out.println(factTail(4, 1));

Compare Table 4.2. There, factorial(4) multiplied on the way back (2 · 1, 3 · 2, 4 · 6); here the multiplications happen on the way down (4 · 1, 3 · 4, 2 · 12), with the same result since multiplication is commutative. The real difference is the way back: in steps 5–7 every frame just passes 24 on.

With nothing to do on the way back, the waiting frames are useless, and a compiler could reuse the current frame for a tail call: tail call optimization. Java doesn't, so factTail still opens 4 frames here, needed for nothing yet occupying stack space.

4.7.3Turning it into a loop

A tail-recursive method always converts mechanically into a loop: a tail call just gives the parameters new values and goes back to the top, which is what a loop does.

int factLoop(int n) {
  int acc = 1;
  while (n > 1) {   // while not the base case
    acc = n * acc;  // the call's new
    n = n - 1;      //   arguments
  }
  return acc;       // base: return acc
}

The conversion rules are:

• Parameters become variables. acc becomes a local initialized to its first-call value, 1.
• The negated base case is the loop condition. Recursion stops when n <= 1; the loop runs while n > 1.
• The tail call becomes updates. factTail(n - 1, n * acc) becomes acc = n * acc; and n = n - 1;, in that order, since acc needs the old n.
• The base case's return follows the loop: return acc;.

The loop uses two variables and no frames: O(1) memory, O(n) time. binarySearch converts the same way — lo and hi become variables, the loop runs while lo <= hi, each iteration updates one — which yields the familiar iterative binary search.

Neither the Java compiler nor the JVM optimizes tail calls, so deep tail recursion still throws StackOverflowError. Scheme guarantees the optimization, and Scala and Kotlin compilers can turn self-recursive tail calls into loops; in Java, potentially deep tail recursion is converted by hand.

4.7.4Recursion or a loop?

Any loop can be written recursively and vice versa; the choice depends on the problem's structure and the input size. Table 4.18 compares the two.

Recursion is natural for nested data (trees, folders, expressions), backtracking (subsets, permutations), problems halved at each step, and recursively defined problems like Hanoi. In all of these the depth is small: about log n, or n itself is small.

A loop is better for simple counting and summing, for linear recursion of depth n when n may be large (a long list, a big number), and for binary recursion with repeated subproblems (fib).

More generally, any recursive method, tail recursive or not, becomes a loop if an explicit stack does the call stack's job: pending work (unfinished multiplications, unsolved subproblems) is pushed, and the loop runs until the stack is empty. Hanoi, for instance, can be solved with such a “task stack.” The conversion is longer than for tail recursion but removes the overflow risk, since an explicit stack grows in the program's general memory.

4.8Recursion on linked lists

Recursion suits data structures as well as numbers and arrays. Seen recursively, the singly linked list, the simplest linked structure, has very short operations, and the same view pays off for trees.

4.8.1A list is a recursive structure

A linked list stores elements in nodes, each holding a value and a reference to the next node; the last node's reference is null. The reference to the first node is usually head, which is null for an empty list.

Recursively, a list is either empty (null) or a node followed by a shorter list. head → 7 → 3 → 9 → null is a node holding 7 plus the list 3 → 9 → null, which is a node holding 3 plus 9 → null, and so on down to the empty list.

So list operations are naturally recursive, always with one pattern: process the node and pass the rest (d.next) to the same method, with the empty list, d == null, as base case. Length is the simplest example:

class Node { int data; Node next; }

int length(Node d) {
  if (d == null) return 0;        // empty list
  return 1 + length(d.next);      // 1 + the rest
}

An empty list has length 0; otherwise the length is 1 plus the rest's. Base case d == null, reduction to d.next, combination by adding 1. Printing front to back follows the same pattern:

void print(Node d) {
  if (d == null) return;
  System.out.print(d.data + " ");
  print(d.next);
}

4.8.2Code trace: length(head)

int length(Node d) {
  if (d == null) return 0;        // empty list
  return 1 + length(d.next);      // 1 + the rest
}
// in main (head → 7 → 3 → 9 → null):
System.out.println(length(head));

The result is 3, after 4 calls (3 nodes and the final null). A list of n nodes takes n + 1 calls and as many frames: O(n) time and stack.

For lists this memory cost is serious: on a million-node list length tries to open a million frames, which won't fit (4.2.3). A loop needs constant memory: int s = 0; for (Node d = head; d != null; d = d.next) s++;.

4.8.3Printing a list backward

A singly linked list has no references back, so printing it backward is awkward with a loop: you can reach the last node but can't step back. Recursion solves this by itself.

void printReverse(Node d) {
  if (d == null) return;
  printReverse(d.next);   // the rest first
  System.out.print(d.data + " ");
}

This differs from print (4.8.1) only in whether the print precedes or follows the call — just like countdown2 and countUp (4.1.5). print(head) prints 7 3 9, in visiting order; printReverse(head) prints 9 3 7.

The list has no backward links; the call stack provides the way back, each frame holding its node until its turn, at the cost of O(n) stack. For very long lists, a loop with an explicit stack is safer: push each node while walking the list, then pop and print them in reverse.

4.9Common mistakes

Most recursion mistakes fall into a few types. Those noted throughout the chapter are collected here as a checklist for reviewing a recursive method.

All of these come back to two questions. The first is correctness: does the base case catch every input, and does every step approach it? The first two mistakes answer “no.” The third and fourth break the induction assumption: the smaller answer is lost, or the smaller problem starts from the wrong state. The second question is cost: how many nodes does the call tree have, and how deep is it? The last two mistakes ignore it; exponentially many nodes make time the problem, great depth makes memory the problem.

4.10Summary

• Recursion is a method calling itself on a smaller input. Every recursive method has a base case, solved directly, and a recursive step that approaches it. Thinking recursively means trusting the smaller problem's answer and designing only the last step — the logic of induction.
• Work before the recursive call happens as the calls go down; work after it happens as they return, in reverse order (countdown2 → 3 2 1, countUp → 1 2 3).
• Each call pushes a frame (parameters, locals, return address) onto the call stack, in LIFO order; only the top frame runs. The stack is limited, and very deep or infinite recursion throws StackOverflowError, so every input, including 0 and negatives, must reach a base case in finitely many steps.
• In linear recursion each call makes at most one call, forming a chain: factorial, sum, reverse, length. Halving the input gives a chain of length O(log n): fastPower makes ⌊log₂ n⌋ + 2 calls, and binarySearch is O(log n).
• In binary recursion each call makes two, forming a call tree. fib(n) makes 2F(n + 1) − 1 calls, growing like 1.6ⁿ, because subproblems repeat. Memoization or a loop gives O(n), the loop with O(1) memory.
• The Towers of Hanoi take three steps: n − 1 disks to the helper, the largest to the target, n − 1 disks to the target; the 2ⁿ − 1 moves are the minimum.
• Backtracking builds a solution step by step: choose, recurse, and undo the choice on return. subsets produces 2ⁿ subsets in 2ⁿ⁺¹ − 1 calls; perm produces n! permutations.
• A recurrence relation expresses the cost through the cost on smaller inputs and is solved with the call tree: T(n − 1) + c → O(n), T(n/2) + c → O(log n), 2T(n − 1) + c → O(2ⁿ). Time comes from the number of calls, space from the deepest chain of calls.
• In tail recursion the recursive call is the last action, and an accumulator carries the partial result. Such a method converts mechanically into a loop: parameters become variables, the negated base case the loop condition. Java doesn't optimize tail calls, so factTail still uses O(n) stack.
• A linked list is recursive: empty, or a node followed by a shorter list, with base case d == null. printReverse uses the call stack to print a singly linked list backward, at the cost of O(n) stack.

In one sentence: recursion is a base case plus a recursive step that approaches it; its time comes from the number of calls, its space from the deepest chain of calls.

4.11Key terms

Each term links to the course glossary, which gives its Turkish equivalent and its use in other chapters.

• recursion
• base case
• recursive step
• stack frame
• call stack
• LIFO (last-in, first-out)
• linear recursion
• binary recursion
• multiple recursion
• binary search
• Towers of Hanoi
• backtracking
• recurrence relation
• tail recursion
• accumulator
• linked list
• node
• time complexity
• space complexity

4.12Test Yourself

1. Given void printDigits(int n) { if (n == 0) return; printDigits(n / 10); System.out.print(n % 10 + " "); }, what does printDigits(472) print? How many calls are made, and how many frames (counting main) are on the stack at most?

   Answer

   The calls are on 472, 47, 4, 0: 4 calls. printDigits(0) is the base case and prints nothing. The print follows the call, so printing happens on the way back: 4, then 7, then 2. The output is 4 7 2, the digits left to right. At the deepest point there are 4 printDigits frames plus main: 5.

2. How many calls does fastPower(3, 9) make? What does each call return?

   Answer

   The values of n are 9, 4, 2, 1, 0: 5 calls (⌊log₂ 9⌋ + 2 = 3 + 2). On the way back: fastPower(3, 0) = 1; n = 1 odd, 3 · 1 · 1 = 3; n = 2 even, 3 · 3 = 9; n = 4 even, 9 · 9 = 81; n = 9 odd, 3 · 81 · 81 = 19,683. The result is 3⁹ = 19,683.

3. How many calls does the recursive fib(7) make? What is the largest number of fib frames on the stack at once?

   Answer

   Since F(8) = 21, there are 2 · 21 − 1 = 41 calls, and fib(7) = 13. The deepest chain is fib(7) → fib(6) → … → fib(1): 7 frames (8 with main). Time is exponential, memory O(n).

4. For a = {1, 4, 7, 10, 13, 16, 19}, how many calls do binarySearch(a, 19, 0, 6) and binarySearch(a, 5, 0, 6) each make, and what do they return?

   Answer

   For 19: (0, 6) mid = 3, 19 > 10; (4, 6) mid = 5, 19 > 16; (6, 6) mid = 6, found. 3 calls, returns 6. For 5: (0, 6) 5 < 10; (0, 2) mid = 1, 5 > 4; (2, 2) mid = 2, 5 < 7; (2, 1) empty range. 4 calls, returns −1.

5. How many moves does the Towers of Hanoi take with 5 disks? How many times does disk 2 move?

   Answer

   2⁵ − 1 = 31 moves. Disk k moves 2^n−k times, so disk 2 moves 2³ = 8 times. Check: disks 1 through 5 move 16, 8, 4, 2, and 1 times, which add up to 31.

6. What does subsets(new int[]{5, 6}, 0, new ArrayList<>()) print, and how many calls does it make?

   Answer

   The output is [5, 6] [5] [6] []. The decision tree has 1 + 2 + 4 = 7 nodes: 2²⁺¹ − 1 = 7 calls. The stack holds at most 3 subsets frames.

7. A method does constant work and stops when n <= 0; otherwise it does constant work and calls itself once on n − 3. What is its recurrence relation? How many calls are made for n = 12?

   Answer

   T(n) = T(n − 3) + c. The chain is 12, 9, 6, 3, 0: 5 calls. In general there are about n/3 + 1 calls, which is O(n), since the input shrinks by a constant amount at each step.

8. Is int pow2(int n, int acc) { if (n == 0) return acc; return pow2(n - 1, acc * 2); } tail recursive? Through which chain of calls does pow2(5, 1) run, and what does it return? What is the loop equivalent?

   Answer

   Yes: the multiplication happens while computing the argument, before the call, and the returned value is passed on unchanged. The chain is (5, 1) → (4, 2) → (3, 4) → (2, 8) → (1, 16) → (0, 32): 6 calls, returning 32 (2⁵). As a loop: int acc = 1; while (n != 0) { acc = acc * 2; n = n - 1; } return acc;. In Java the recursion uses O(n) memory, the loop O(1).

9. Consider int count(Node d, int x) { if (d == null) return 0; return (d.data == x ? 1 : 0) + count(d.next, x); }. For the list 2 → 7 → 2 → 2 → null, what does count(head, 2) return, and how many calls does it make? Is the method tail recursive?

   Answer

   It returns 3 (three nodes hold 2), after 5 calls: four nodes and null. It is not tail recursive, since 0 or 1 is added after the call returns; a version with an accumulator (count(d.next, x, acc + …)) would be.

10. Given int t(int n) { if (n <= 1) return 1; return t(n - 1) + t(n - 1) + t(n - 1); }, what does t(3) return, and how many calls does it make? How can the method be made linear?

    Answer

    The tree's levels have 1, 3, and 9 nodes: 13 calls. Each of the 9 leaves returns 1, so t(3) = 9 = 32. In general t(n) = 3ⁿ⁻¹, with (3ⁿ − 1)/2 calls: O(3ⁿ). The three calls compute the same value; return 3 * t(n - 1); leaves one call and costs O(n).

4.13Further reading

• M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Data Structures and Algorithms in Java (6th ed., 2014), Chapter 5: presents recursion by dividing it into linear, binary, and multiple recursion, with Java examples close to those in these notes (binary search, reversing an array, computing powers).
• R. Sedgewick and K. Wayne, Computer Science: An Interdisciplinary Approach (2016), Section 2.3: the Towers of Hanoi, repeated computation in Fibonacci, and memoization, through short programs and experiments.
• E. Roberts, Thinking Recursively with Java (2006): a whole book on recursive thinking, explaining the connection with induction and backtracking examples for the beginning reader.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), Chapter 4: solves recurrences more formally, with the recursion-tree and substitution methods.

4.14References

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022.
2. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6th ed., Wiley, 2014.
3. E. Roberts, Thinking Recursively with Java, Wiley, 2006.
4. R. Sedgewick, K. Wayne, Computer Science: An Interdisciplinary Approach, Addison-Wesley, 2016.

Related pages: Chapter 4 slides · Study questions · Towers of Hanoi simulator · Glossary · © Sercan Külcü. All rights reserved.