Introduction

So far, all algorithms have used iteration—loops that repeat operations. Recursion offers an alternative approach: a method that calls itself. Topic 4.16 introduces recursive methods and how to trace their execution.

A recursive method is a method that calls itself. Recursion is another form of repetition—instead of using loops, we break problems into smaller versions of themselves. While recursion can seem abstract at first, it elegantly solves certain problems like traversing tree structures, computing factorials, or processing nested data.

Important: Writing recursive code is outside the scope of the AP Computer Science A course and exam. You only need to trace and understand existing recursive methods.

What is Recursion?

Recursion works by:

Solving a simple version of the problem directly (base case)
Breaking complex versions into simpler ones (recursive case)
Combining results from simpler versions

Recursive methods contain at least one base case, which halts the recursion, and at least one recursive call.

Simple Example: Countdown

public static void countdown(int n) 
{
    if (n == 0) 
    {
        System.out.println("Done!");  // Base case
    } 
    else 
    {
        System.out.println(n);
        countdown(n - 1);      // Recursive call
    }
}

Call countdown(3):

Prints 3, calls countdown(2)
- Prints 2, calls countdown(1)
  - Prints 1, calls countdown(0)
    - Prints Done! (base case reached)

Output:

3
2
1
Done!

Base Case and Recursive Case

Base Case

The base case is the stopping condition—the simplest version of the problem that can be solved directly without recursion.

Without a base case, recursion continues forever (or until stack overflow error).

Example base cases:

Countdown: n == 0
Factorial: n == 0 or n == 1
Binary search: range has 0 or 1 element

Recursive Case

The recursive case calls the method with a simpler version of the problem, moving toward the base case.

Each recursive call must make progress toward the base case or the recursion won't terminate.

Complete Example: Factorial

The factorial of $n$ is: $n! = n \times (n - 1) \times (n - 2) \times \dots \times 2 \times 1$

Recursive definition: $n! = {1 n (n - 1)! if n = 0, if n > 0$

public static int factorial(int n) 
{
    if (n == 0) 
    {
        return 1;              // Base case
    } 
    else 
    {
        return n * factorial(n - 1);  // Recursive case
    }
}

Trace factorial(4):

factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * (1 * factorial(0))))
= 4 * (3 * (2 * (1 * 1)))
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
= 4 * 6
= 24

Local Variables and Parameters

Each recursive call has its own set of local variables, including the parameters. This is crucial—each "level" of recursion maintains separate data.

Parameter values capture the progress of a recursive process, much like loop control variable values capture the progress of a loop.

Example: Sum of Array

public static int sum(int[] arr, int index) 
{
    if (index >= arr.length) 
    {
        return 0;                    // Base case: past end
    } 
    else 
    {
        return arr[index] + sum(arr, index + 1);  // Recursive case
    }
}

Trace sum([2, 3, 5], 0):

Each call has its own index:

Call 1: index = 0, returns 2 + sum(arr, 1)
- Call 2: index = 1, returns 3 + sum(arr,2)
  - Call 3: index = 2, returns 5 + sum(arr,3)
    - Call 4: index = 3, returns 0 (base case)
  - Call 3 returns: 5 + 0 = 5
- Call 2 returns: 3 + 5 = 8
Call 1 returns: 2 + 8 = 10

Final result: 10

The index parameter tracks progress—like a loop counter, but through method parameters instead of a variable.

Tracing Recursive Methods

Method 1: Call Stack Diagram

Draw each method call as a box showing parameters and local variables:

Example: power(2, 3) computes $2^{3}$

public static int power(int base, int exp) 
{
    if (exp == 0) 
    {
        return 1;
    } 
    else 
    {
        return base * power(base, exp - 1);
    }
}

Stack diagram:

power(2, 3) → 2 * power(2, 2)
              |
              └─→ power(2, 2) → 2 * power(2, 1)
                                |
                                └─→ power(2, 1) → 2 * power(2, 0)
                                                  |
                                                  └─→ power(2, 0) → 1
                                                  returns 1
                                    returns 2 * 1 = 2
                      returns 2 * 2 = 4
        returns 2 * 4 = 8

Method 2: Substitution

Replace each recursive call with its eventual value:

power(2, 3)
= 2 * power(2, 2)
= 2 * (2 * power(2, 1))
= 2 * (2 * (2 * power(2, 0)))
= 2 * (2 * (2 * 1))
= 2 * (2 * 2)
= 2 * 4
= 8

Method 3: Table of Calls

Track each call's parameters and return value:

$Call # 1234 Parameters base = 2, exp = 3 base = 2, exp = 2 base = 2, exp = 1 base = 2, exp = 0 Returns 2 \times result_of_call_2 = 8 2 \times result_of_call_3 = 4 2 \times result_of_call_4 = 2 1 (base case)$

Recursion vs Iteration

Any recursive solution can be replicated through the use of an iterative approach and vice versa.

Recursive Factorial

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

Iterative Factorial

public static int factorial(int n) 
{
    int result = 1;
    for (int i = 1; i <= n; i++) 
    {
        result *= i;
    }
    return result;
}

Both produce the same results—recursion is just another way to express repetition.

When to prefer recursion:

Problem naturally divides into smaller versions (tree traversal, divide-and-conquer)
Recursive solution is simpler and clearer

When to prefer iteration:

Performance matters (recursion has overhead)
Deep recursion might cause stack overflow

Complete Examples

Example 1: String Reversal

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

Trace reverse("abc"):

reverse("abc")
= reverse("bc") + 'a'
= (reverse("c") + 'b') + 'a'
= ((reverse("") + 'c') + 'b') + 'a'
= (("" + 'c') + 'b') + 'a'
= ("c" + 'b') + 'a'
= "cb" + 'a'
= "cba"

Example 2: Fibonacci

public static int fibonacci(int n) 
{
    if (n == 0)   // Base case 1
    {
      return 0;         
    }
    if (n == 1)   // Base case 2
    {
      return 1;         
    }
    return fibonacci(n - 1) + fibonacci(n - 2);  // Recursive
}

Trace fibonacci(4):

fibonacci(4)
= fibonacci(3) + fibonacci(2)
= (fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))
= ((fibonacci(1) + fibonacci(0)) + 1) + (1 + 0)
= ((1 + 0) + 1) + 1
= (1 + 1) + 1
= 2 + 1
= 3

Example 3: Array Sum

public static int arraySum(int[] arr, int start) 
{
    if (start >= arr.length) 
    {
        return 0;
    }
    return arr[start] + arraySum(arr, start + 1);
}

Trace arraySum([5, 3, 8], 0):

arraySum([5,3,8], 0)
= 5 + arraySum([5,3,8], 1)
= 5 + (3 + arraySum([5,3,8], 2))
= 5 + (3 + (8 + arraySum([5,3,8], 3)))
= 5 + (3 + (8 + 0))
= 5 + (3 + 8)
= 5 + 11
= 16

Common Mistakes

Mistake 1: Missing base case

// WRONG - infinite recursion
public static int bad(int n) 
{
    return n + bad(n - 1);  // Never stops!
}

Mistake 2: Base case never reaches

// WRONG - if n is odd, never reaches 0
public static int bad(int n) 
{
    if (n == 0)
    {
      return 0;
    }
    return bad(n - 2);  // Skips 0 if n is odd!
}

Mistake 3: Not making progress

// WRONG - always calls with same value
public static int bad(int n) 
{
    if (n == 0)
    {
      return 0;
    }
    return n + bad(n);  // n never changes!
}

FiveHive