The base case and the call stack

A recursive method is 2 cases. One of them answers the job outright, and the other makes the job smaller and calls the method again. What follows is the first one: what a base case has to be, how to find it, what the machine is actually doing while the calls pile up, and what happens when the base case is missing or unreachable.

What a base case has to be

The base case is the version of the job that has an answer you can write down without asking anything else. It is not a safety check bolted onto the front. It is the answer for the smallest input.

The job	The smallest version	Its answer, with no further calls
add up an array from index `i` onward	`i` is past the last index	0, because there is nothing left to add
count the nodes from here to the end	here is `null`	0, because there is no node
reverse the span from `left` to `right`	`left` is not before `right`	nothing to do, the span is done
multiply the whole numbers from 1 to `n`	`n` is 0	1, which is what an empty product is

Two of those 4 answer with the value that changes nothing, 0 for adding and 1 for multiplying. That is not a coincidence, it is what "nothing left to do" means for each operation, and it is usually the right guess for a base case value.

Three rules come with it.

Write the base case first. Before you write the recursive call, write the test and the value it returns. That decides what the recursive case has to hand back.

Every path has to reach it. Not most inputs. Every input the method will be called with, including the smallest and the empty one.

The recursive call has to be strictly smaller. Smaller by the same measure the base case is written in. If the base case tests the index, the call moves the index. If the base case tests the node, the call moves to the next node.

The call stack, drawn

When any method is called, Java sets aside a block of memory for that call, and the usual name for it is a frame. The frame holds that call's parameters, its local variables, and where to go back to when it finishes. Frames stack: newest on top, main at the bottom. When a call returns, its frame is discarded and the frame under it resumes at the line after the call.

Recursion adds nothing to that. It just means several frames on the stack happen to belong to the same method, each with its own separate copies.

public static int sumTo(int n)
{
    if (n == 0)
    {
        return 0;
    }
    return n + sumTo(n - 1);
}

Call sumTo(3) and watch the stack grow, then shrink. Each line is a frame, and the value beside it is that frame's own n.

growing
  sumTo(3)  n=3  waits
  sumTo(2)  n=2  waits
  sumTo(1)  n=1  waits
  sumTo(0)  n=0  returns 0

shrinking
  sumTo(1)  1 + 0  returns 1
  sumTo(2)  2 + 1  returns 3
  sumTo(3)  3 + 3  returns 6

Read the first block top to bottom and the second one after it. Nothing is added up on the way down. Every frame is parked on the line return n + sumTo(n - 1), having evaluated nothing but the call. The adding happens on the way back, once the base case has given the innermost frame something to add to.

Two shapes: carry it down, or combine on the way back

There are 2 ways to get an answer out of a recursion, and knowing which one you are writing removes most of the confusion about where the work goes.

Combine on return. The call goes down empty handed, the base case returns a starting value, and each frame combines its own piece with what came back. sumTo above is this shape. So is anything written as return something + recursiveCall(...).

Carry down. The answer so far travels in a parameter. Each call updates it and passes it on, so by the time the base case is reached, the answer is already complete, and the base case just returns the parameter it was handed. Nothing happens on the way back up at all.

// carry down: the running total is a parameter
public static int sumTo(int n, int total)
{
    if (n == 0)
    {
        return total;
    }
    return sumTo(n - 1, total + n);
}

The same call, sumTo(3, 0), with the frames written out:

growing
  sumTo(3, 0)  n=3  total=0
  sumTo(2, 3)  n=2  total=3
  sumTo(1, 5)  n=1  total=5
  sumTo(0, 6)  n=0  total=6, returns 6

shrinking
  every frame returns the same 6

Compare the 2 shrinking blocks. The combine version computes a different number in every frame on the way back. The carry-down version computes the answer on the way down, and every frame on the way back does nothing but pass the same 6 along. That difference is the whole distinction.

Which one you use is usually not your choice, because the public method is already written and its call tells you. A public method that calls a helper with extra parameters holding starting values is handing you a carry-down problem, and the extra parameters are the things being carried.

public static int countNegatives(int[] array)
{
    if (array == null)
    {
        throw new IllegalArgumentException("array was null");
    }
    return countNegatives(array, 0, 0);
}

Read that last line and the helper is described for you. It takes an index and a count so far. Both start at 0, so no element has been counted yet. The base case therefore has to be the index reaching the end, and it has to return the carried count.

When nothing stops it

Frames take memory, and the region they live in has a fixed size that is decided before your program starts. A recursion that never reaches its base case keeps making frames until that region is full, and then Java throws a StackOverflowError.

Three things about that are worth holding on to.

It is a run-time death after a clean compile. Nothing about a missing base case is a syntax error. The code compiles, the build succeeds, and the program dies the first time the method runs. A compiler that accepted your code has told you nothing about whether the recursion terminates.

It is an Error, not an Exception. It sits on the branch of the family tree Java's own documentation says a reasonable application should not try to catch. Catching it does not fix anything, because the bug is the recursion, and the stack is already full at the moment you would catch it.

What it prints is the same line over and over. The chain of calls is thousands of frames deep and they are all the same method, so a wall of identical lines is what this bug looks like. The method name on those lines is the one to go look at.

There are 3 ways to earn it, and only the first is the one people expect.

// 1. no base case at all
public static int bad(int n)
{
    return n + bad(n - 1);
}

// 2. a base case that this input can never reach
public static int bad(int n)
{
    if (n == 0) { return 0; }
    return n + bad(n - 1);      // called with -3, n never lands on 0
}

// 3. a base case that can be reached, and a call that does not shrink
public static int bad(int n)
{
    if (n == 0) { return 0; }
    return n + bad(n);          // same value forever
}

Number 3 is the one that hides, because the method has a base case sitting right there in plain sight and the test is correct. The bug is in the argument. When you are checking your own recursion, read the argument at the call site and say out loud what changed about it.

The rule about loops

A recursion problem asks for a recursion. The department's own preview of the upcoming exam format states the consequence directly:

If you use loops in the recursion problems, you will get 0 points for recursion.

Upcoming APE General Instructions Preview, posted on the official site's Practice Exams page.

This is not a knowledge gap for anybody who gets caught by it. You have spent 2 terms learning to reach for for the moment you see an array, and that reflex is what fires under time pressure. The fix is practice rather than reading: write the recursive version of a few small methods from a blank file, with no loop keyword allowed anywhere in the body, until reaching for the call feels as automatic as reaching for the loop.

It helps to know what the loop was doing, so you can see what replaces it. A loop keeps its state in variables it reassigns: the index, the running total. A recursion never reassigns anything, so that same state travels in the parameters instead, and the stack of frames remembers where each call was. An index that was i++ becomes an argument of i + 1. A total that was total += x becomes an argument of total + x.

RecursionFindLargest.java says No loops of any form are allowed, and the preview above says loops without defining the word. Once the helper is written, search its body for for, while and do. Then read every call in it and ask whether that call visits every element. Neither document defines a loop, so the safe reading counts a library call that walks the array for you as a loop too. A stream, the Java library feature that runs a step over every element, is the usual example: a helper that hands the array to a stream and asks for its largest value is doing its repeating there. If the only thing doing the walking is your own recursive call, the rule is kept.

The infinite recursion and the infinite loop are the same finding

The same preview says that code which compiles but runs forever earns nothing for that problem, and it names a missing base case as an example of how that happens. So a recursion with no base case is not partially right. Check the smallest inputs by hand before you check anything else: the empty case, the one-element case, and the case the public method seeds. If the base case is right for those, the rest of the recursion is usually already right.

In the practice APE

Both recursion problems in the Practice APE Exam Instructions hand you the public method and ask for the private helper, so in both of them the base case is the first thing you have to work out, and both give you enough to work it out from.

Readiness check

Work each one on paper and write the answer down before you open it.

TraceThe frames, both shapes

Use the 2 versions of sumTo above.

sumTo(4), the combine-on-return version. How many frames at the deepest point, and what does each frame add?
sumTo(4, 0), the carry-down version. What does total hold in each frame, deepest frame last?
Both return the same number. What is it?
In which version does a frame still have work to do after the call it made returns?

Answers

1. Five frames, with n holding 4, 3, 2, 1 and 0. They add 4, 3, 2, 1 and nothing, in that order on the way back up.

2. 0, then 4, then 7, then 9, then 10. The last one is the base case and it returns 10 straight out.

3. 10.

4. The combine version. Every frame is parked mid-expression waiting to add its own n. In the carry-down version each frame's last act is the call itself, so when the call returns there is nothing left to do but pass the value along.

TraceWhich ones terminate

For each, say whether the call terminates. If it does not, name which of the 3 ways to earn a stack overflow it is.

countUp(0) where the body is if (n == 10) { return; } countUp(n + 1);
countUp(20) on that same method.
half(7) where the body is if (n == 0) { return 0; } return 1 + half(n / 2);
walk(node) where the body is if (node == null) { return 0; } return 1 + walk(node);

Answers

1. It terminates. n climbs by 1 and lands exactly on 10.

2. It does not. The base case exists and is correct for some inputs, and 20 is already past it and moving away, which is the second failure: a base case this input cannot reach. Changing the test to n >= 10 fixes it.

3. It terminates. Integer division drops the remainder, so 7 becomes 3, then 1, then 0, and it returns 3.

4. It does not. This is the third failure. The base case is right, the test is right, and the argument never changed, so the same node is passed forever. It has to be node.next.

TraceRead the seeded call

A public method you may not change ends with this line, and you are writing the helper.

return countMatches(array, 0, 0, target);

The helper header is private static int countMatches(int[] array, int i, int found, int target).

Which parameter is the one that shrinks the problem, and which is carrying an answer?
Which shape is this, carry down or combine on return?
Write the base case test and what it returns.
Write the recursive call, assuming array[i] matches target.

Answers

1. i shrinks the problem, because it is the position in the array. found is carrying the answer, and it is seeded at 0 because nothing has been found yet.

2. Carry down. The seed of 0 for found is the tell: a combine-on-return version would have no such parameter, because the count would be built on the way back.

3. if (i == array.length) { return found; }. One past the last index, returning what was carried.

4. return countMatches(array, i + 1, found + 1, target);. The index moves on and the count goes up. The non-matching branch is the same call with found unchanged.

The one thing to keep

The base case is the answer for the smallest input, written before anything else, and the recursive call has to move toward it by the same measure the base case tests. Each call gets its own frame with its own copies, so the state lives in the parameters and the stack does the remembering. Carry the answer down in a parameter, or combine it on the way back up, and let the public method's own call tell you which. A missing or unreachable base case compiles cleanly and dies at run time with a StackOverflowError, so check the smallest inputs by hand, and read the argument at the call site to make sure something actually got smaller.