Recursion: methods that call themselves

Some problems have a smaller copy of themselves inside. The total of a shopping list is the first price plus the total of the rest of the list. The size of a folder is the size of its own files plus the size of every folder inside it. When you spot that shape, you can write a method that solves the problem by calling itself on the smaller copy. In this lesson you write methods like that, and watch, call by call, what Java does when a method calls itself.

A method that calls itself#

Picture a long queue outside a cinema. You want to know your place in it, but all you can see is the back of the person in front of you. So you tap their shoulder and ask, “What number are you?” They do not know either, so they tap the person in front of them and ask the same question. The question travels forward until it reaches the person at the very front, who needs to ask nobody: they are number 1. Then the answers travel back. Each person hears a number, adds one, and passes the result to the person behind.

Nobody in that queue solved the whole problem. Each person did one small step and handed the rest to someone else, who did the same small step. A method can work the same way: it does a little of the work and calls itself to do the rest. A method that calls itself is a recursive method, and solving a problem this way is called recursion.

The smallest useful recursive method is a countdown. Press Run, then step through slowly with the arrow buttons while you watch the call stack panel.

The program prints the numbers 3, 2 and 1, then Liftoff!, each on its own line. Now look at what happened in the call stack. When main calls countdown(3), a box appears for that call, holding n = 3. Then countdown(3) calls countdown(2), and a second box appears with its own n = 2, while the first box stays where it is, waiting. By the time Liftoff! prints there are four countdown boxes at once, with n equal to 3, 2, 1 and 0.

Then the boxes go away in reverse order. countdown(0) prints and returns, so its box disappears and Java is back inside countdown(1), just after the line that made the call. That call has nothing left to do, so it returns as well, and so on back to main.

Key idea

Every call gets its own box on the call stack, with its own copy of the parameters. Four calls to countdown means four separate variables named n, all alive at the same time.

The base case and the recursive case#

Look at countdown again. It has two parts, and every recursive method you write will have the same two.

• The base case is an input so small that the method can answer without calling itself. For countdown it is n == 0: print Liftoff! and stop. In the cinema queue, it is the person at the front.
• The recursive case covers every other input. The method does one small piece of the work and calls itself on a smaller input. For countdown, that means printing n and calling countdown(n - 1).

One more rule is hidden in there, and it is the one people forget: every recursive call has to move closer to the base case. countdown subtracts 1 each time, so from any positive start it must reach 0. If it subtracted nothing, or added 1, it would never get there.

Factorial: building the answer on the way back

countdown does its work on the way down, before each call. Most recursive methods do their work on the way back, by using the answer the smaller call returns. The classic example is the factorial. 4 factorial, written 4!, means 4 × 3 × 2 × 1, which is 24.

The smaller copy hides inside: 4! is 4 × 3!, because 3! is 3 × 2 × 1. In the same way 3! is 3 × 2!, and 2! is 2 × 1!. And 1! is just 1. Those sentences are already the whole method. The base case is n == 1, and the recursive case returns n times the factorial of n - 1.

Step through it and watch the stack grow to four factorial boxes, from n = 4 down to n = 1. None of the first three can finish yet. factorial(4) cannot multiply until it knows factorial(3), which needs factorial(2), which needs factorial(1). Only factorial(1) can answer straight away. Then the answers come back, one multiplication per box, and the program prints 4! = 24.

Key idea

A recursive method needs a base case that answers without recursing, and a recursive case that calls the method on a smaller input. Every call must move closer to the base case.

What the call stack is doing#

You have been watching boxes appear and disappear. Each time a method is called, Java sets aside a small block of memory for that one call, called a stack frame, and each box in the panel is one frame. The frame holds the call's parameters and local variables, and it remembers where in the caller to carry on once the call returns. The frames of all the calls that have started but not yet finished are kept in order on the call stack.

It is a stack in the same sense as in stacks and queues: last in, first out. A call pushes a new frame on top. When the call returns, its frame is popped off, and the frame underneath, the caller's, carries on from where it paused. The method running right now is always the one on top. (The visualizer lists the frames oldest first, so the top of the stack is the last box, the one marked Running.)

None of this is special to recursion. When main calls a method that calls another method, three frames are stacked up in the same way. In recursion, several of the frames belong to the same method, each with different values inside.

The order of pushing and popping decides the order of everything a recursive method does. This method prints a line before its recursive call and another line after it.

The down lines print while the frames are being pushed: 3, then 2, then 1. Each up line has to wait until every call above its frame has returned, so the up lines come out as the frames are popped, in reverse: 1, then 2, then 3. echo(3) was the first frame in and is the last one out.

Trusting the recursion#

Tracing every frame is the best way to see how recursion works, and a slow way to write a recursive method. When programmers write one, they use a habit sometimes called the leap of faith: while writing the recursive case, assume the call on the smaller input already works and returns the right answer. Your only job is to turn that answer into the answer for the input you were given.

Back in the cinema queue, if the person in front of you tells you their correct place, yours is their number plus one. You never need to know how they worked theirs out.

1. 1Find the smallest input and its answer. That is the base case.
2. 2Pretend the method already works for any smaller input.
3. 3Write the recursive case: call the method on a smaller input, and use its answer to build the answer for this input.
4. 4Check that every call gets smaller, so the calls must reach the base case.

Numbers: counting digits and raising to a power

How many digits does 2026 have? Dividing an int by 10 drops its last digit, because integer division throws the remainder away: 2026 / 10 is 202. That means 2026 has one more digit than 202. The smallest case is a number below 10, which has one digit.

Powers work the same way. 2 to the power 5 means 2 × 2 × 2 × 2 × 2, which is 2 times (2 to the power 4). Any number to the power 0 is 1, and that gives the base case.

Read countDigits with the leap of faith: if countDigits(202) correctly returns 3, then 1 + countDigits(202) is 4. You can check that by stepping through, and after a few methods like this you will find you no longer need to. The program prints 4 and then 32.

Arrays: carry an index

An array does not get smaller when you pass it to a method, so you need another way to shrink the problem: pass a position along with it. The call sum(prices, 0)means “the total from index 0 to the end”, which is prices[0] plus the total from index 1 to the end. The smallest case is an index that has walked off the end of the array. Nothing is left to add, so that total is 0.

Step through and watch the arrow labelled i in the memory view: each new frame starts one index further along the array. There is only ever one array. Every frame holds a reference to it and its own i, so nothing is copied. On the way back the frames add 5 + 0, then 2 + 5, then 7 + 7, then 4 + 14, and the program prints Total: 18.

Strings: peel off a character

Strings shrink with substring. To reverse a word, take off its first letter, reverse the rest, and stick that first letter on the end. To reverse stop, reverse top to get pot, then add the s. A word with one letter, or none, is its own reverse, so that is the base case.

In the call stack, each frame's word is one letter shorter than the one before: stop, top, op, p. The last frame returns p, and each frame on the way back adds its own first letter: po, then pot, then pots.

1public class Main {
2    public static void main(String[] args) {
3        System.out.println(countChar("banana", 'a'));
4        System.out.println(countChar("recursion", 'z'));
5        System.out.println(countChar("", 'a'));
6    }
7 
8    static int countChar(String word, char letter) {
9        // TODO: an empty word contains no letters at all.
10        // TODO: otherwise count the letters in word.substring(1),
11        //       and add 1 if word.charAt(0) is the letter.
12        return 0;
13    }
14}

A palindrome check peels off two letters at once. A word reads the same backwards when its first and last letters match and the part in between is a palindrome too. You solved this with a loop in string practice. The recursive version follows that definition line by line.

racecar shrinks to aceca, then cec, then e. That is one letter, so the answer is true. rocket stops at the first comparison, because r and t differ, and the method returns false without recursing at all. A method can have more than one base case, and this one has two: a short word, and a mismatch.

Halving: binary search

A recursive call does not have to shrink the problem by just one. Binary search finds a value in a sorted array by looking at the middle element and throwing half of the array away each time. If the target is smaller than the middle element, it can only be in the left half, so search there. If it is bigger, search the right half. The part still worth searching runs from index lo to index hi, and once lo passes hi nothing is left, so the target is not in the array. The middle index is lo + (hi - lo) / 2, which gives the same number as (lo + hi) / 2 but avoids an int overflow on a huge array. You will study binary search properly, including that midpoint, in searching and sorting.

In the memory view, the arrows labelled lo and hi close in as each new frame starts. Finding 42 among eight numbers takes two calls, and the program prints 5, the index where 42 sits. Looking for 10, which is missing, takes four calls. The last one gets an empty range, with lo at 2 and hi at 1, so it prints -1. Each call halves the range, so even a million sorted numbers need only about 20 calls, and the call stack never gets deep.

Linked lists: a node, then a smaller list

A linked list has a recursive definition: it is either empty, or a node followed by a smaller linked list. That is why recursion fits linked lists so well. The length of an empty list (a null reference) is 0, and the length of any other list is 1 plus the length of the list that starts at next.

1public class Main {
2    public static void main(String[] args) {
3        Node list = new Node("milk", new Node("eggs", new Node("bread", null)));
4        System.out.println(length(list));
5        System.out.println(length(list.next));
6        System.out.println(length(null));
7    }
8 
9    static int length(Node node) {
10        // TODO: an empty list (null) has length 0.
11        // TODO: otherwise the length is 1 plus the length of the rest.
12        return 0;
13    }
14}
15 
16class Node {
17    String item;
18    Node next;
19 
20    Node(String item, Node next) {
21        this.item = item;
22        this.next = next;
23    }
24}

When recursion never stops: StackOverflowError#

Go back to the factorial method and ask it for the factorial of 0. Its base case is n == 1, but 0 is already below 1. So factorial(0) calls factorial(-1), which calls factorial(-2), and n runs away from the base case forever. Each call pushes a frame that cannot be popped until the call above it returns, and none of them ever returns.

The program prints Working out 0! and then stops with a StackOverflowError: the call stack ran out of room. The second println never runs. Drag the progress bar back to the step where Java throws the error and look at the call stack: a tower of factorial frames, each with its own n, deep into the negative numbers. The steps after it show Java leaving those frames one at a time, looking for a catch that never comes.

The visualizer gives up after a few hundred frames, to keep your browser responsive. Real Java has far more room. On the computer used to test this page, this program got more than 25,000 calls deep before the stack ran out, and the exact number changes with the computer, the method and the -Xss setting. The ending is the same either way. Here is the start of what Java prints in a terminal:

Java printed about a thousand of those at Main.factorial lines and then stopped listing them, so the report never even gets down to main. When a stack trace shows one method on the same line over and over, read it as a recursion that never reached its base case. Reading stack traces in general is covered in reading errors and debugging.

Two ways to miss the base case

• There is no base case at all, so nothing ever stops the calls.
• There is a base case, but the recursive case can jump over it or move away from it. That is what happened to factorial(0): subtracting 1 from 0 moves away from 1.

The fix here is a base case that catches every small input: if (n <= 1). It covers 1, and it covers 0, whose factorial is defined to be 1 as well. With it, factorial(0) returns 1 at once. Negative numbers have no factorial, yet with this fix the method quietly returns 1 for them too. A stricter method would refuse negative input by throwing an exception, which you will learn to do in exception handling.

Fibonacci: recursion that repeats itself#

The Fibonacci numbers start with 0 and 1, and each number after that is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21, and on forever. Count the positions from 0, so fib(0) is 0, fib(1) is 1, fib(2) is 1, and fib(6) is 8.

That definition is already recursive: fib(n) is fib(n - 1) + fib(n - 2). It needs two base cases, because the recursive case reaches back two places: fib(0) is 0 and fib(1) is 1. One check covers both, since in both cases the answer is n itself.

This method is different from every one so far, because a single call can make two recursive calls. Step through and keep an eye on the call stack. fib(5) calls fib(4), and that call goes all the way down to fib(1) and fib(0) and back before fib(5) gets to make its second call, fib(3). The stack grows and shrinks many times over.

Drawn out, the calls make a tree. Each call sits above the two calls it makes, and Java visits the tree in a fixed order: a call starts, its whole fib(n - 1) side runs to the end, then its fib(n - 2) side, and only then does it return. Choose n = 5 below and press Play.

While it plays, look at the calls marked as on the call stack. At every moment they form a path from the top of the tree down to the call that is running: the call stack is that path. Then look at how often the same call turns up. Inside fib(6), fib(2) is worked out from scratch 5 times, and fib(1) is called 8 times. Choose n = 6 and use the buttons under the tree to light up every copy of one call.

Counting the calls

To measure how bad the repeating gets, count the calls. The counter has to be a static field outside the method. A local variable lives inside one frame, so every call would get a fresh one that starts at 0.

Doubling n from 5 to 10 multiplied the calls by more than ten. The visualizer cannot follow much bigger runs, because it records several steps for every call. Real Java has no such limit, and with larger values of n the same counter prints this:

fib(10) = 55 after 177 calls
fib(20) = 6765 after 21891 calls
fib(30) = 832040 after 2692537 calls
fib(40) = 102334155 after 331160281 calls

Every time n grows by 10, the number of calls is multiplied by more than 120. fib(40) makes over 331 million calls to produce one number, and almost all of them redo work that was already done somewhere else in the tree. fib(50) would need over 40 billion.

Memoization: remember what you already worked out#

The tree shows the fix. The first time you work out fib(3), write the answer down. Every later time something asks for fib(3), read the answer back instead of working it out again. Storing answers like this is called memoization, from memo, a note you write so you remember something, and the place you keep the answers is often called the memo.

An array makes a good memo here, because the inputs are small whole numbers that can be used as indexes: memo[n] holds fib(n) once it is known. A new long array is full of zeros, and fib(n) is never 0 when n is 2 or more, so a 0 in memo[n]means “not worked out yet”. The answers are long because Fibonacci numbers grow fast: fib(47) is already too big for an int.

Watch the memory view as you step. The arrow labelled n shows which slot the running call is looking at, and memo fills from the left as calls return: memo[2] first, then memo[3], and so on up to memo[6]. When fib(4) makes its second call, fib(2), the answer is already in memo[2], so that call returns at once without calling anything. The program prints fib(6) = 8 after 11 calls, down from 25 without the memo.

Now go back up to the call tree and switch the memo on. The repeated calls fade out, because with the memo they never happen. Each fib(k) is worked out once, and every later request for it is answered from the memo straight away. For n = 7 the tree shrinks from 41 calls to 13. The same counter as before shows how far the saving goes:

With the memo, going from fib(20) to fib(40) roughly doubles the work. Without it, the same step multiplies the work by about fifteen thousand.

Key idea

Memoization trades a little memory for a lot of time: store each answer the first time you work it out, and look it up every time after that.

A HashMap as the memo

An array only works when the inputs can be used as indexes. When they cannot, because they are huge numbers, or strings, or pairs of values, keep the answers in a map from HashMap and HashSet, with the input as the key and the answer as the value. Step through it and watch the map in the memory view fill up as each answer is stored.

containsKey asks whether the answer for n is stored, and get hands it back. The map ends up holding 49 answers, one for each n from 2 to 50.

Recursion or a loop?#

Anything you can write with recursion you can also write with a loop, and the other way round. This program works out a factorial both ways. Step through it and compare the call stack during the two calls.

Both print 120. While factorialRecursive(5) runs, the stack grows to five frames of it. While factorialLoop(5) runs there is only one frame, and result and i change inside it.

That gives a sensible rule. When a problem splits into smaller copies of itself, especially two or more of them, recursion usually gives the clearer code. When you are walking through items one at a time, a loop is clearer and has no depth limit.

Depth is the trap to watch. A recursive sum of the numbers from 1 to 10,000 works on real Java, but the same method for 1 to 100,000 overflows the stack with Java's default settings, while a loop adds up a hundred million numbers without trouble. Walking a long linked list recursively has the same problem, because every node costs a frame.

Key idea

Use recursion when a problem contains smaller copies of itself, and a loop when you walk straight through a sequence. Every recursive call holds a stack frame until it returns, so watch how deep it can go.

Three problems made for recursion#

Some problems are awkward with loops and take only a few lines with recursion, because they split into smaller copies of themselves. These three are optional, and each one follows the same recipe as before.

The Tower of Hanoi

You have three pegs, A, B and C, and a pile of disks on peg A, the biggest at the bottom. The goal is to move the whole pile to peg C. You may move only one disk at a time, and you may never put a disk on top of a smaller one.

Planning the moves for even four disks by hand gets confusing. The leap of faith makes it short. To move 3 disks from A to C, first move the top 2 disks out of the way onto B, which is a smaller Hanoi problem. Then move the biggest disk from A to C. Then move the 2 disks from B onto C, another smaller Hanoi problem. Moving 0 disks takes no moves at all, so that is the base case.

It prints seven moves and then Moves: 7. Each extra disk doubles the moves and adds one more, so n disks take 2 to the power n, minus 1, moves.

Every order of some letters

In how many orders can you arrange the letters of abc? To list them all, try each letter in the first place, and after each choice list every order of the letters that are left. That inner job is the same problem with one letter fewer. Below, chosen holds the letters placed so far and rest holds the ones still to place. When rest is empty, chosen is one complete arrangement.

The six lines are all the permutations of abc, its possible orders. This method has a loop inside it, so each call makes as many recursive calls as there are letters left: 3, then 2, then 1. The count grows fast. 4 letters give 24 orders, and 10 letters give 3,628,800, which is 10!.

Flood fill: the paint bucket

The paint bucket in a drawing program fills the area you click, spreading to every touching pixel of the same color and stopping at edges. On a grid stored in a 2D array, that is a short recursion: to fill a cell, paint it, then fill the four cells next to it, below, above, right and left. The base cases are the cells to skip: anything outside the grid, and anything that is not blank.