Recursion: base case, the call stack, and the classic examples

Nesting dolls#

A set of nesting dolls: open the big doll and there is a slightly smaller doll inside, the same shape. Open that, and there is another. You keep going until you reach the tiny doll at the centre, which is solid and does not open. Then you are done.

Recursion is that. A recursive method is a method that calls itself, each time on a smaller version of the problem, until it reaches a version so small that the answer is obvious. That smallest, solid doll is the base case: the case the method answers directly, without calling itself again. Every other case is a recursive case, or general case.

The typical structure#

Almost every recursive method in this course has the same two-part shape:

returnType solve(problem) {
    if (problem is small enough) {        // base case
        return the simple answer;
    } else {                               // recursive case
        return combine(something, solve(a smaller problem));
    }
}

The base case is checked first. Without it, or if the problem never actually gets smaller, the method calls itself forever. Each call takes up memory on the call stack, the pile of method calls that are waiting to finish, and Java soon runs out:

public class Forever {
    public static int countDown(int n) {
        return countDown(n - 1);
    }

    public static void main(String[] args) {
        try {
            countDown(10);
        } catch (StackOverflowError e) {
            System.out.println("Stopped by " + e.getClass().getSimpleName());
        }
    }
}

Stopped by StackOverflowError

StackOverflowError is an Error, not an Exception: the Java machine itself has run out of room. Real programs do not catch it; the listing does so only to show its name instead of a thousand-line stack trace. The fix is always the same: a correct base case, and a recursive call that moves toward it.

Four questions for building a recursive solution#

A widely taught checklist, from Prichard and Carrano’s textbook Data Abstraction and Problem Solving with Java: Walls and Mirrors, turns writing a recursive method into four questions. In our words, ask them in this order:

1. Can I describe the problem using a smaller copy of exactly the same problem? For factorial: 5! is 5 × 4!.
2. How does each recursive call make the problem smaller? The number goes down by 1 each time.
3. Which version of the problem is small enough to answer directly, as the base case? 0! is 1, known without any work.
4. As the problem shrinks, will it definitely reach the base case? Starting from any n ≥ 0 and subtracting 1 always reaches 0. (A negative n would not, which is why the method should reject one.)

If you can answer all four, the method nearly writes itself. If you cannot answer the fourth, you have found your infinite recursion before running it.

Factorial, and watching the stack#

Factorial: n! is n × (n − 1) × … × 1, and 0! is 1. That turns straight into the two-part shape. The version below adds print statements so you can watch each call wait for the one inside it:

public class Factorial {
    public static long factorial(int n, String indent) {
        System.out.println(indent + "factorial(" + n + ") called");
        long result;
        if (n == 0) {
            result = 1;
        } else {
            result = n * factorial(n - 1, indent + "  ");
        }
        System.out.println(indent + "factorial(" + n + ") returns " + result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println("4! = " + factorial(4, ""));
    }
}

factorial(4) called
  factorial(3) called
    factorial(2) called
      factorial(1) called
        factorial(0) called
        factorial(0) returns 1
      factorial(1) returns 1
    factorial(2) returns 2
  factorial(3) returns 6
factorial(4) returns 24
4! = 24

Read the output in two halves. Going down, each call is paused, waiting for the answer to a smaller one: factorial(4) cannot multiply until it knows factorial(3). That is the stack winding. At the base case, answers start coming back up, each call finishing its multiplication and handing the result to the call that was waiting for it. That is the stack unwinding. The last call to start is the first to finish, like a stack of plates.

GCD: Euclid’s algorithm#

The greatest common divisor of two numbers is the largest number that divides both: the GCD of 48 and 18 is 6. Euclid found a shortcut over two thousand years ago: the GCD of a and b is the same as the GCD of b and the remainder of a ÷ b. Keep going until the remainder is 0; the other number is the answer.

public class Gcd {
    public static int gcd(int a, int b) {
        System.out.println("gcd(" + a + ", " + b + ")");
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        System.out.println("Answer: " + gcd(48, 18));
    }
}

gcd(48, 18)
gcd(18, 12)
gcd(12, 6)
gcd(6, 0)
Answer: 6

Four calls to answer the question. The base case is b == 0, and the problem shrinks because a remainder is always smaller than the number you divided by. This is the course’s GCD example; tracing it on paper, one line per call, is a likely exam question.

Fibonacci, and the cost of calling twice#

The Fibonacci numbers start 0, 1, and each one after is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13… The definition is already recursive, with two base cases:

public class Fib {
    static long calls = 0;

    public static long fib(int n) {
        calls++;
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

    public static long fibLoop(int n) {
        long prev = 0, curr = 1;
        for (int i = 1; i < n; i++) {
            long next = prev + curr;
            prev = curr;
            curr = next;
        }
        return n == 0 ? 0 : curr;
    }

    public static void main(String[] args) {
        for (int n = 0; n <= 7; n++) {
            System.out.print(fib(n) + " ");
        }
        System.out.println();
        for (int n : new int[] {10, 20, 25}) {
            calls = 0;
            long value = fib(n);
            System.out.println("fib(" + n + ") = " + value + " took " + calls + " calls");
        }
        System.out.println("Loop version: fib(20) = " + fibLoop(20));
    }
}

0 1 1 2 3 5 8 13 
fib(10) = 55 took 177 calls
fib(20) = 6765 took 21891 calls
fib(25) = 75025 took 242785 calls
Loop version: fib(20) = 6765

It is correct, and it is shockingly slow. Each call makes two more calls, and they repeat each other’s work: fib(20) needs fib(19) and fib(18), but fib(19) computes fib(18) all over again. The call counts above show the result: 21,891 calls to find the 20th number, and each step up multiplies the work by about 1.6. The loop at the end computes the same number in 19 passes. Recursion is elegant here and the wrong tool.

Binary search#

To find a word in a printed dictionary, you do not start at page one. You open the middle, see whether your word comes before or after, and throw away the half it cannot be in. Then you repeat on the half that is left. That is binary search, and it only works on a sorted array.

public class BinSearch {
    public static int search(int[] arr, int target, int low, int high) {
        if (low > high) {
            return -1;
        }
        int mid = (low + high) / 2;
        System.out.println("  looking at index " + mid + " (value " + arr[mid] + ") in " + low + ".." + high);
        if (arr[mid] == target) {
            return mid;
        } else if (target < arr[mid]) {
            return search(arr, target, low, mid - 1);
        } else {
            return search(arr, target, mid + 1, high);
        }
    }

    public static void main(String[] args) {
        int[] sorted = {3, 8, 15, 21, 34, 42, 57, 68, 79, 91};
        System.out.println("Searching for 57:");
        System.out.println("Found at " + search(sorted, 57, 0, sorted.length - 1));
        System.out.println("Searching for 10:");
        System.out.println("Found at " + search(sorted, 10, 0, sorted.length - 1));
    }
}

Searching for 57:
  looking at index 4 (value 34) in 0..9
  looking at index 7 (value 68) in 5..9
  looking at index 5 (value 42) in 5..6
  looking at index 6 (value 57) in 6..6
Found at 6
Searching for 10:
  looking at index 4 (value 34) in 0..9
  looking at index 1 (value 8) in 0..3
  looking at index 2 (value 15) in 2..3
Found at -1

Two base cases: the middle element is the target (return its index), or the range is empty, low > high (return −1, not found). Each recursive call keeps only half of the range, so a sorted array of a million elements takes at most about 20 looks. Compare that with linear search from the arrays guide, which may check all million.

The Towers of Hanoi#

Three pegs, and a stack of discs on the first, largest at the bottom. Move the whole stack to the third peg. Rules: move one disc at a time, and never put a larger disc on a smaller one.

The recursive insight: to move n discs from A to C, first move the top n − 1 discs out of the way to B, then move the biggest disc from A to C, then move the n − 1 discs from B onto it. The “move n − 1 discs” steps are the same problem, one disc smaller. The base case is one disc: just move it.

public class Hanoi {
    static int moves = 0;

    public static void solve(int n, char from, char spare, char to) {
        if (n == 1) {
            moves++;
            System.out.println(moves + ". disc 1 from " + from + " to " + to);
            return;
        }
        solve(n - 1, from, to, spare);
        moves++;
        System.out.println(moves + ". disc " + n + " from " + from + " to " + to);
        solve(n - 1, spare, from, to);
    }

    public static void main(String[] args) {
        solve(3, 'A', 'B', 'C');
        System.out.println(moves + " moves");
    }
}

1. disc 1 from A to C
2. disc 2 from A to B
3. disc 1 from C to B
4. disc 3 from A to C
5. disc 1 from B to A
6. disc 2 from B to C
7. disc 1 from A to C
7 moves

Three discs take 7 moves. In general, n discs take 2ⁿ − 1 moves, which is why the puzzle’s legend about 64 golden discs needs more than 580 billion years at one move a second. A loop solution exists, but it is far harder to write and to understand: this is the problem where recursion clearly wins.

Recursion versus iteration#

Iteration means repeating with a loop. Anything a recursive method can do, a loop can also do, sometimes with the help of your own stack. So the choice is about clarity and cost:

Factorial and GCD are clean either way. Fibonacci shows recursion done naively can be disastrously slow. Hanoi shows recursion can turn a hard problem into three lines. Choose recursion when it makes the solution clearer and the depth of calls stays modest.

Where these go wrong#

• No base case, or one that is never reached. The result is a StackOverflowError, recursion’s version of an infinite loop.
• A recursive call that does not shrink the problem. factorial(n) calling factorial(n) goes forever. It must be n - 1.
• Forgetting return on the recursive call. Writing gcd(b, a % b); without return throws the answer away (and a non-void method will not compile).
• Checking the base case after the recursive call. The call happens first and never stops. Base case goes at the top.
• Binary search on an unsorted array. Throwing away half only works when the order tells you which half.
• Using plain recursive Fibonacci for large n. The repeated calls grow exponentially. Use a loop.
• Tracing the output of a recursive method in call order only. Anything printed after the recursive call appears in reverse, as the stack unwinds.

Practice#

Answer each one on paper before you look at the solutions. Every answer that involves running code was checked by compiling and running it.

1. Define recursion, base case and recursive case in one sentence each.
2. Write a recursive method sumTo(n) that returns 1 + 2 + … + n, with sumTo(0) returning 0. Answer the four questions for it.
3. What does mystery("stack") return?

   public static String mystery(String s) {
       if (s.length() <= 1) {
           return s;
       }
       return mystery(s.substring(1)) + s.charAt(0);
   }

4. Trace gcd(84, 36) using gcd(a, b) = gcd(b, a % b) with base case b == 0.
5. Binary search for 15 in {3, 8, 15, 21, 34, 42, 57, 68, 79, 91}. Which indexes are examined, and what is returned?
6. Write a recursive power(base, exp) for a whole-number exponent of 0 or more. How many moves does the Towers of Hanoi take for 5 discs?

Solutions#

1. Recursion is a method solving a problem by calling itself on a smaller version of the same problem. The base case is the version small enough to answer directly, without another call. The recursive case is every other version, which calls the method again on something closer to the base case.
2. Smaller problem: sumTo(n) is n + sumTo(n - 1). Each call shrinks n by 1. Base case: sumTo(0) is 0. Starting from any n ≥ 0, subtracting 1 always reaches 0.

   public class QSum {
       public static int sumTo(int n) {
           if (n == 0) {
               return 0;
           }
           return n + sumTo(n - 1);
       }
   
       public static void main(String[] args) {
           System.out.println(sumTo(5));
           System.out.println(sumTo(100));
       }
   }

   15
   5050

3. Each call puts its first character after the result for the rest of the String, so the characters come back in reverse order:

   public class QMystery {
       public static String mystery(String s) {
           if (s.length() <= 1) {
               return s;
           }
           return mystery(s.substring(1)) + s.charAt(0);
       }
   
       public static void main(String[] args) {
           System.out.println(mystery("stack"));
       }
   }

   kcats

4. gcd(84, 36) → gcd(36, 12), because 84 % 36 is 12 → gcd(12, 0), because 36 % 12 is 0 → base case, the answer is 12.
5. low 0, high 9: mid 4 (34). 15 is smaller, so search 0..3: mid 1 (8). 15 is larger, so search 2..3: mid 2 (15). Found: it returns 2. Three elements examined.
6. Base case: anything to the power 0 is 1. Recursive case: base * power(base, exp - 1).

   public class QPower {
       public static long power(int base, int exp) {
           if (exp == 0) {
               return 1;
           }
           return base * power(base, exp - 1);
       }
   
       public static void main(String[] args) {
           System.out.println(power(2, 10));
           System.out.println(power(3, 4));
           System.out.println(power(7, 0));
       }
   }

   1024
   81
   1

   For Hanoi, n discs take 2ⁿ − 1 moves, so 5 discs take 2⁵ − 1 = 31.

Test-readiness checklist#

These are the items from the course’s Exam 2 topic list that this guide covers. Tick each one only when you can do it without looking.

• ☐  I can give the definition of recursion and identify the base case.
• ☐  I can write a recursive method in the typical structure: base case first, then a smaller recursive call.
• ☐  I can use the four questions for constructing recursive solutions.
• ☐  I can compare iteration vs. recursion and say when each is the better choice.
• ☐  I can write and trace the examples: factorial, GCD, Fibonacci numbers, binary search and the Towers of Hanoi.

Frequently asked questions#

Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written — several of these exist because somebody asked.