Reference Guide

Key Topics

Term Definition Example
Recursion A method solving a problem by calling itself on a smaller problem. factorial(number - 1)
Base case Condition that stops further calls. if (number <= 1)
Recursive case Part that calls the method again. return number * factorial(number - 1);
Call stack Stack of paused method calls waiting for a result. factorial(3) waits for factorial(2)
Frame One call’s parameters and paused work on the call stack. The number value in factorial(2)
Unwinding Returning results from the base case back upward. 1, then 2, then 6
StackOverflowError Runtime error caused by recursion that does not stop. A call that keeps the same argument

Recursion Patterns

Pattern What happens Short code example
Base case Stops making recursive calls and returns a result. if (number <= 1) { return 1; }
Recursive case Calls the method again with an argument closer to the base case. return number * factorial(number - 1);
Call stack behavior Calls wait while the stack grows; pending work resumes in reverse order after the base case returns. factorial(3) waits for factorial(2), then multiplies the returned value by 3.

Recursion Checklist

  • What is the base case?
  • What does it return or print?
  • What is the recursive call?
  • Does its argument move toward the base case?
  • What happens while the calls unwind?

Recursion Compared with Loops

  • A loop repeats through a condition and update.
  • Recursion repeats through method calls and smaller arguments.
  • Both need progress and a stopping condition.

Choosing Recursion

  • Need a stopping point? Define the base case first.
  • Can the problem become a smaller version of itself? Use a recursive case that moves toward the base case.
  • Need to track pending work and return order? Trace the call stack and its unwinding.

College Board Requirements

AP CSA Unit 4, Topic 4.16: Recursion. The official 2025 Course and Exam Description is listed in References (College Board, 2025).

  • TODO (College Board, 2025, p. TODO): Add the exact Topic 4.16 learning objective ID and quoted wording.
  • TODO (College Board, 2025, p. TODO): Add each applicable Topic 4.16 essential knowledge ID and its exact quoted wording.

Lesson Plan

Learning Objective: Identify the base case and recursive case, trace a recursive call stack, and write recursive methods that move toward a base case.

Success Criteria: You can identify where recursion stops, identify the recursive call and its progress, trace power(2, 3) by hand, compare print-before and print-after output, and repair a broken recursive method.

Tech Talk

Recursion means a method solves a problem by calling itself on a smaller version of the problem. The base case is the condition where the method stops making calls. The recursive case is the part that calls the method again. The argument must move toward the base case, such as changing number to number - 1. Recursion is sometimes used instead of a loop when a problem naturally breaks into smaller versions of itself, such as walking through nested data.

Our running scenario is a launch mission: a countdown starts the launch, factorial calculates fuel units, and a digit sum checks the launch code.

Call Stack Trace: factorial(3)

Follow how factorial(3) unwinds through this call stack:

A call stack is the stack of method calls that are currently waiting for results. Each call creates a frame containing that call’s parameter values and paused work.

  1. factorial(3) starts and waits for 3 * factorial(2).
  2. factorial(2) starts and waits for 2 * factorial(1).
  3. factorial(1) reaches the base case and returns 1.
  4. factorial(2) resumes: 2 * 1 = 2, then returns 2.
  5. factorial(3) resumes: 3 * 2 = 6, then returns 6.

Unwinding is the process of returning from the base case back through the paused frames in reverse order: 1, then 2, then 6. The stack grows while calls move toward the base case and unwinds after the base case returns.

Code Runner Challenge

Run the complete Java examples in Section 5. Predict the output first, then trace the base case, recursive calls, and call-stack unwinding against the output.


Code Examples

A. Countdown: Print Before the Recursive Call

Code Runner Challenge

Change the starting number and predict the mission output

View IPYNB Source
// CODE_RUNNER: Change the starting number and predict the mission output
public class MissionCountdown {
    public static void countdown(int number) {
        if (number == 0) {
            System.out.println("Liftoff!");
        } else {
            System.out.println("T-minus " + number);
            countdown(number - 1);
        }
    }

    public static void main(String[] args) {
        countdown(3);
    }
}

MissionCountdown.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

B. Unwinding: Print After the Recursive Call

Code Runner Challenge

Predict the completion order, then run the mission

View IPYNB Source
// CODE_RUNNER: Predict the completion order, then run the mission
public class MissionUnwinding {
    public static void completeStage(int number) {
        if (number == 0) {
            System.out.println("Launch sequence ready");
        } else {
            completeStage(number - 1);
            System.out.println("Stage " + number + " complete");
        }
    }

    public static void main(String[] args) {
        completeStage(3);
    }
}

MissionUnwinding.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

When a message is printed before the recursive call, it appears while the stack is growing; when it is printed after the call, it appears while the stack is unwinding, so the order reverses.

C. Factorial Fuel

Code Runner Challenge

Predict factorial(4), then run the fuel calculation

View IPYNB Source
// CODE_RUNNER: Predict factorial(4), then run the fuel calculation
public class MissionFuel {
    public static int factorial(int number) {
        if (number <= 1) {
            return 1;
        }
        return number * factorial(number - 1);
    }

    public static void main(String[] args) {
        System.out.println("Fuel units for mission 4: " + factorial(4));
    }
}

MissionFuel.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

D. Digit-Sum Checksum

Code Runner Challenge

Trace the launch code, then change it and predict the checksum

View IPYNB Source
// CODE_RUNNER: Trace the launch code, then change it and predict the checksum
public class LaunchCodeChecksum {
    public static int sumDigits(int number) {
        if (number < 10) {
            return number;
        }
        return (number % 10) + sumDigits(number / 10);
    }

    public static void main(String[] args) {
        int launchCode = 2026;
        System.out.println("Checksum for " + launchCode + ": " + sumDigits(launchCode));
    }
}

LaunchCodeChecksum.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

For sumDigits(2026), the trace is 6 + sumDigits(202) → 6 + 2 + sumDigits(20) → 6 + 2 + 0 + sumDigits(2) → 6 + 2 + 0 + 2 = 10. number % 10 gives the last digit, while integer division number / 10 removes that digit. Factorial is the mission’s fuel because its multiplication grows a resource total; digit sum is the launch-code checksum because it reduces the code to a quick value for checking.

E. Broken Runner

Code Runner Challenge

Run it to see why recursive progress toward the base case matters

View IPYNB Source
// CODE_RUNNER: Run it to see why recursive progress toward the base case matters
public class BrokenMissionCountdown {
    public static void countdown(int number) {
        if (number == 0) {
            return;
        }
        countdown(number);
    }

    public static void main(String[] args) {
        try {
            countdown(3);
        } catch (StackOverflowError error) {
            System.out.println("Stack overflow: the recursive call never moved toward zero.");
        }
    }
}

BrokenMissionCountdown.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Hacks & Practice Tasks

Popcorn Hack

Write a recursive count-up method that starts at 1 and prints through 5. Identify its base case and explain how the argument moves toward it before you run the cell.

Code Runner Challenge

Predict the count-up order, then run it

View IPYNB Source
// CODE_RUNNER: Predict the count-up order, then run it
public class MissionCountUp {
    public static void countUp(int number) {
        if (number > 5) {
            System.out.println("Count-up complete");
        } else {
            System.out.println(number);
            countUp(number + 1);
        }
    }

    public static void main(String[] args) {
        countUp(1);
    }
}

MissionCountUp.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Homework Hack

Complete both TODOs in the recursive power method. The base case must handle an exponent of zero, and the recursive case must use a smaller power problem.

Stretch task: What happens if the exponent is negative? Explain why the current base case does not stop that input and what a robust method would need to do.

Code Runner Challenge

Complete both TODOs, then run the power tests

View IPYNB Source
// CODE_RUNNER: Complete both TODOs, then run the power tests
public class MissionPowerHomework {
    public static int power(int base, int exponent) {
        if (exponent == 0) {
            // TODO: What should power return when the exponent is 0?
            return 0;
        }

        // TODO: Multiply base by the answer to a smaller power problem.
        return 0;
    }

    public static void main(String[] args) {
        System.out.println("2^3 = " + power(2, 3));
        System.out.println("3^2 = " + power(3, 2));
    }
}

MissionPowerHomework.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

References

College Board. (2025). AP Computer Science A course and exam description [Effective fall 2025].

All Java lessons