Recursion
A Method That Calls Itself

Master the art of recursive thinking: learn how methods call themselves to solve complex problems by breaking them into smaller, identical subproblems.

AP Computer Science A

What Is Recursion?

Recursion is a programming technique where a method calls itself to solve a problem. Instead of using loops, a recursive method breaks a problem into smaller instances of the same problem until it reaches a case simple enough to solve directly.

The Two Essential Parts

Base Case

The stopping condition that prevents infinite recursion. It returns a known value directly without making another recursive call.

Recursive Case

The method calls itself with a modified argument that moves closer to the base case. This is where the problem gets broken down.

The Call Stack in Action

Tracing an array sum

This separate worked question comes from the related lesson.

A student writes the following recursive method intended to compute the sum of an int array: public static int sumArray(int[] arr, int index) { if (index == arr.length) return 0; return arr[index] + sumArray(arr, index + 1); } (a) Trace the execution of sumArray(new int[]{5, 3, 8}, 0), showing every recursive call and its return value. (b) The student's friend claims the method would work just as well if the base case were changed to if (index == arr.length - 1) return arr[index];. Is the friend correct? Explain whether the modified version produces the same results for all valid inputs, including edge cases. (c) Rewrite the method so that it processes the array from the last element toward the first (i.e., the initial call is sumArray(arr, arr.length - 1) and the base case occurs at index 0). (d) Explain the time and space complexity of this recursive approach and compare it to an iterative for-loop summing the same array.

Show answer and explanation

(a) Trace: sumArray({5,3,8}, 0): index 0 ≠ 3 → returns 5 + sumArray({5,3,8}, 1) sumArray({5,3,8}, 1): index 1 ≠ 3 → returns 3 + sumArray({5,3,8}, 2) sumArray({5,3,8}, 2): index 2 ≠ 3 → returns 8 + sumArray({5,3,8}, 3) sumArray({5,3,8}, 3): index 3 == 3 → returns 0 (base case) Unwinding: 8+0=8, 3+8=11, 5+11=16. Final result: 16. (b) The friend is partially correct. For any non-empty array, the modified base case returns arr[arr.length-1] directly instead of recursing one more level and adding arr[arr.length-1]+0. The arithmetic result is identical. However, for an empty array (length 0) called with index 0, the condition 0 == -1 is false. The next expression first accesses arr[0], throwing an ArrayIndexOutOfBoundsException before recursion, while the original correctly returns 0. So the friend's version is not equivalent for all valid inputs. (c) Reverse implementation: public static int sumArray(int[] arr, int index) { if (index < 0) return 0; if (index == 0) return arr[0]; return arr[index] + sumArray(arr, index - 1); } For a nonnull array, use the initial call sumArray(arr, arr.length - 1). An empty array starts at index -1 and returns 0. For a nonempty array, the base case at index 0 returns arr[0]; each recursive call decrements the index. (d) Complexity: Both the recursive and iterative versions run in O(n) time because each element is visited exactly once. However, the recursive version requires O(n) space on the call stack (one frame per element), while a for-loop uses only O(1) extra space for the accumulator variable. For very large arrays, the iterative version is preferable to avoid stack overflow.

For sumArray([5,3,8],0), calls reach index 3 and return 0, then unwind through 8, 11 and 16.

The Recursive Pattern

public static returnType methodName(parameters) {
    if (/* base case condition */) {
        return /* base case value */;
    }
    return /* combine with */ methodName(/* smaller argument */);
}

1

Check the base case first. If the input is simple enough, return the answer immediately.

2

Make the recursive call. Pass a smaller or simpler version of the input.

3

Combine the result. Use the value returned by the recursive call to build the final answer.

Classic Example: Factorial

The factorial of \( n \) is defined as \( n! = n \times (n-1) \times \cdots \times 1 \), with the base case \( 0! = 1 \). This maps perfectly to recursion:

public static int factorial(int n) {
    if (n == 0) {          // base case
        return 1;
    }
    return n * factorial(n - 1);  // recursive case
}

Recursion vs. Iteration

	Recursion	Iteration
Mechanism	Method calls itself	Loops (for, while)
Termination	Base case	Loop condition
Memory	Uses call stack	Uses loop variables
Readability	Elegant for trees, math	Simpler for linear tasks
Risk	StackOverflowError	Infinite loop

How to Write a Recursive Method

1

Identify the base case. What is the simplest input? What should it return?

2

Define the recursive relationship. How does the answer for \( n \) relate to the answer for a smaller input?

3

Ensure progress toward the base case. Every recursive call must move the argument closer to the base case.

4

Trust the recursion. Assume the recursive call returns the correct answer for the smaller problem. Just handle the current step.

5

Trace with a small example. Walk through the calls by hand to verify correctness.

Example 1: Sum of Digits

Write a method that returns the sum of the digits of a non-negative integer. For example, sumDigits(1234) should return \( 1 + 2 + 3 + 4 = 10 \).

public static int sumDigits(int n) {
    if (n < 10) {           // base case: single digit
        return n;
    }
    return n % 10 + sumDigits(n / 10);
}

Example 2: Computing \( b^n \)

Compute \( b^n \) recursively using the fact that \( b^n = b \times b^{n-1} \) with base case \( b^0 = 1 \).

public static int power(int b, int n) {
    if (n == 0) {           // base case
        return 1;
    }
    return b * power(b, n - 1);  // recursive case
}

Example 3: Fibonacci Sequence

The Fibonacci sequence is defined as \( F(0) = 0 \), \( F(1) = 1 \), and \( F(n) = F(n-1) + F(n-2) \). Note: this has two recursive calls and two base cases.

public static int fib(int n) {
    if (n == 0) return 0;  // base case 1
    if (n == 1) return 1;  // base case 2
    return fib(n - 1) + fib(n - 2);
}

Example 4: String Reversal

Recursion works on Strings too. Reverse a String by peeling off the first character and appending it at the end of the reversed remainder.

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

Example 5: Recursive Binary Search

public static int binarySearch(int[] arr, int target, int lo, int hi) {
    if (lo > hi) {
        return -1;              // base case: not found
    }
    int mid = (lo + hi) / 2;
    if (arr[mid] == target) {
        return mid;              // base case: found
    } else if (arr[mid] < target) {
        return binarySearch(arr, target, mid + 1, hi);
    } else {
        return binarySearch(arr, target, lo, mid - 1);
    }
}

Common Mistakes

✕ Missing Base Case

Without a base case, the method calls itself infinitely, resulting in a StackOverflowError.

✕ No Progress Toward Base Case

If the argument doesn't change (or changes in the wrong direction), the recursion never terminates.

✕ Wrong Return Value

Forgetting to return the result of the recursive call. The method runs but the value is lost.

Recursion Summary

Concept	Key Idea	Example
Base Case	Simplest input, returns directly	n == 0 → return 1
Recursive Case	Calls itself with smaller input	n * factorial(n-1)
Call Stack	Each call waits for the next	LIFO order
Termination	Must reach base case	Else StackOverflow
Best Use	Naturally recursive structures	Trees, divide-and-conquer

Question 1 of 5

What is the output of the following code?

public static int mystery(int n) {
    if (n == 0) return 0;
    return n + mystery(n - 1);
}
// Call: mystery(5)

This method computes \( 5 + 4 + 3 + 2 + 1 + 0 = 15 \). It sums all integers from \( n \) down to \( 0 \).

Question 2 of 5

Which of the following will cause a StackOverflowError?

If the parameter never changes, the base case is never reached and the method calls itself infinitely, filling the call stack until it overflows.

Question 3 of 5

What does the following method return when called as foo("hello")?

public static int foo(String s) {
    if (s.length() == 0) return 0;
    return 1 + foo(s.substring(1));
}

The method counts the length of the string recursively. Each call adds 1 and removes the first character. "hello" has 5 characters, so it returns 5.

Question 4 of 5

How many times is fib() called in total (including the original call) when computing fib(5)?

Drawing the recursion tree: fib(5) calls fib(4) and fib(3). Each of those branches further, resulting in 15 total calls. This exponential growth is why naive Fibonacci recursion is inefficient.

Question 5 of 5

What is the output of the following recursive method call mystery(4)?

public static void mystery(int n) {
    if (n > 0) {
        mystery(n - 1);
        System.out.print(n + " ");
    }
}

The print happens after the recursive call, so the deepest call (n=1) prints first. This is a key insight: code before the recursive call executes top-down, code after executes bottom-up.

RecursionA Method That Calls Itself

What Is Recursion?

The Two Essential Parts

The Call Stack in Action

Tracing an array sum

The Recursive Pattern

Classic Example: Factorial

Recursion vs. Iteration

How to Write a Recursive Method

Example 1: Sum of Digits

Example 2: Computing \( b^n \)

Example 3: Fibonacci Sequence

Example 4: String Reversal

Example 5: Recursive Binary Search

Common Mistakes

Recursion Summary

Question 1 of 5

Question 2 of 5

Question 3 of 5

Question 4 of 5

Question 5 of 5

Recursion
A Method That Calls Itself