Advanced CS Recursion: Base Cases, Stack Frames, and Trace Discipline

Recursion becomes much less mysterious when students stop asking, "How do all the calls happen at once?" and start asking, "What is one call responsible for?" A recursive method should have a clear contract, a base case that stops the chain, and a recursive step that makes the input smaller.

A worked example: count target values

Suppose a method should count how many times target appears from index index to the end of an array. The contract is narrow: this call is responsible for the suffix starting at one index.

public static int countTarget(int[] values, int index, int target)
{
    if (index == values.length)
    {
        return 0;
    }

    int rest = countTarget(values, index + 1, target);

    if (values[index] == target)
    {
        return 1 + rest;
    }

    return rest;
}

For {4, 7, 4, 2} and target 4, the calls move forward until index == 4. Only then do returns begin: index 3 contributes 0, index 2 contributes 1, index 1 contributes 0, and index 0 contributes 1. The final answer is 2.

Trace the call stack in two passes

A strong recursion trace has two columns: calls going down and returns coming back up. Students often make mistakes because they try to compute the final answer while the calls are still going down. That is like trying to grade an exam before all answers have been written.

Call	What waits?
countTarget(values, 0, 4)	Needs result from index 1, then may add 1.
countTarget(values, 1, 4)	Needs result from index 2.
countTarget(values, 2, 4)	Needs result from index 3, then may add 1.
countTarget(values, 4, 4)	Base case returns 0.

Harder pattern: recursion with a choice

Advanced CS problems often include recursion where each call chooses between options. For example, count the number of ways to reach exactly target points using moves worth 1, 3, or 5.

public static int countWays(int remaining)
{
    if (remaining == 0)
        return 1;
    if (remaining < 0)
        return 0;

    return countWays(remaining - 1)
         + countWays(remaining - 3)
         + countWays(remaining - 5);
}

The base cases carry the meaning. Reaching exactly 0 is one valid way. Dropping below 0 is not valid. The recursive step tries each possible next move and combines the counts.

Common traps

• No progress: calling the method with the same input causes infinite recursion.
• Wrong base case: stopping at index == values.length - 1 often skips the final element.
• Lost return value: making a recursive call but not returning or using its result.
• Shared state confusion: changing an array or list during recursion without understanding which later calls see the mutation.

Practice prompt

Write a recursive method isStrictlyIncreasing(int[] a, int index) that returns whether every adjacent pair from index onward is increasing. Test it on an empty suffix, a one-element suffix, a passing array, and an array with the failure near the end.