# AP® Computer Science A 4.16 Recursion

Source: https://lockincs.com/ap-csa/unit-4/4-16-recursion/  
Last reviewed against the College Board Course and Exam Description (CED): 2026-11-12  
CED codes: 4.16.A, 4.16.A.1, 4.16.A.2, 4.16.A.3

A recursive method is a method that calls itself. It has at least one base case, which halts the recursion, and at least one recursive call, and it is another form of repetition. Each call has its own local variables and parameters, so on the AP® exam you trace recursive calls one by one to determine the result.

## What you will learn

- 4.16.A Determine the result of calling recursive methods.

## 1\. What makes a method recursive

A **recursive method** is a method that calls itself 4.16.A.1. Every recursive method contains at least one **base case**, which halts the recursion, and at least one **recursive call** 4.16.A.1. Recursion is another form of repetition, like a loop 4.16.A.1.

```
public static void countdown(int n)
{
    if (n == 0)                  // base case: stop
    {
        System.out.println("Liftoff!");
    }
    else
    {
        System.out.println(n);
        countdown(n - 1);        // recursive call
    }
}

countdown(3);
```

Output:

```
3
2
1
Liftoff!
```

Each call moves `n` one step closer to the base case. Scope note: writing recursive code is outside the scope of the AP® Computer Science A exam. You must be able to read recursive methods and determine the result of calling them 4.16.A.1.

## 2\. Tracing a method that returns a value

Each recursive call has its own set of local variables, including its parameters 4.16.A.2. A call that is waiting for a deeper call to return stays “paused” with its own values. Java keeps these paused calls on the **call stack**.

```
public static int sumDigits(int n)
{
    if (n < 10)
    {
        return n;
    }
    return n % 10 + sumDigits(n / 10);
}

System.out.println(sumDigits(4071));
```

Output:

```
12
```

Trace it in two directions. Going down, write each call. Coming back up, fill in each return value.

| Call | n | Base case? | Returns |
| --- | --- | --- | --- |
| `sumDigits(4071)` | 4071 | no | 1 + sumDigits(407) = 1 + 11 = **12** |
| `sumDigits(407)` | 407 | no | 7 + sumDigits(40) = 7 + 4 = **11** |
| `sumDigits(40)` | 40 | no | 0 + sumDigits(4) = 0 + 4 = **4** |
| `sumDigits(4)` | 4 | yes | **4** |

There are four calls and four different values of `n` alive at the same time. When `sumDigits(4)` returns, `sumDigits(40)` continues with its own `n`, which is still 40.

## 3\. Before or after the recursive call

Where a statement sits relative to the recursive call decides when it runs. A statement **before** the call runs on the way down. A statement **after** the call waits until every deeper call has returned, so it runs on the way back up, in reverse order 4.16.A.2.

```
public static void echo(String word)
{
    if (word.length() > 0)
    {
        System.out.print(word.substring(0, 1));       // before the call
        echo(word.substring(1));
        System.out.print(word.substring(0, 1));       // after the call
    }
}

echo("abc");
System.out.println();
```

Output:

```
abccba
```

| Step | What happens | Printed so far |
| --- | --- | --- |
| 1 | `echo("abc")` prints a, calls `echo("bc")` | a |
| 2 | `echo("bc")` prints b, calls `echo("c")` | ab |
| 3 | `echo("c")` prints c, calls `echo("")` | abc |
| 4 | `echo("")` is the base case: does nothing, returns | abc |
| 5 | back in `echo("c")`: prints c | abcc |
| 6 | back in `echo("bc")`: prints b | abccb |
| 7 | back in `echo("abc")`: prints a | abccba |

## 4\. Parameters track progress, like a loop control variable

Parameter values capture the progress of a recursive process, much like the values of a loop control variable capture the progress of a loop 4.16.A.2. Some methods make more than one recursive call; draw a tree of calls and add the results from the bottom up.

```
public static int paths(int steps)
{
    if (steps <= 1)
    {
        return 1;
    }
    return paths(steps - 1) + paths(steps - 2);
}

System.out.println(paths(4));
```

Output:

```
5
```

Call tree for `paths(4)`:

| Call | Makes the calls | Returns |
| --- | --- | --- |
| `paths(4)` | `paths(3)` and `paths(2)` | 3 + 2 = **5** |
| `paths(3)` | `paths(2)` and `paths(1)` | 2 + 1 = **3** |
| `paths(2)` | `paths(1)` and `paths(0)` | 1 + 1 = **2** |
| `paths(1)`, `paths(0)` | base cases | **1** each |

In total `paths(4)` causes 9 calls, because `paths(2)` is computed twice and `paths(1)` three times.

## 5\. Recursion and iteration are interchangeable

Any recursive solution can be replicated with an iterative approach (a loop), and any iterative solution can be written recursively 4.16.A.3. The parameter plays the role of the loop control variable, and the base case plays the role of the loop condition becoming false.

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

public static int powerLoop(int base, int exp)
{
    int result = 1;
    for (int i = exp; i > 0; i--)
    {
        result *= base;
    }
    return result;
}

System.out.println(powerRec(3, 4) + " " + powerLoop(3, 4));
```

Output:

```
81 81
```

| Recursive version | Iterative version |
| --- | --- |
| parameter `exp` | loop control variable `i` |
| `exp - 1` in the recursive call | `i--` |
| base case `exp == 0` | loop stops when `i > 0` is false |

## 6\. No base case reached: StackOverflowError

If the recursive calls never reach a base case, every call waits on the call stack until Java runs out of room 4.16.A.1. The program stops with an error.

```
public static int halve(int n)
{
    if (n == 1)
    {
        return 0;
    }
    return 1 + halve(n / 2);
}

System.out.println(halve(8));
System.out.println(halve(0));
```

Output:

```
3
Exception in thread "main" java.lang.StackOverflowError
```

`halve(8)` reaches the base case after three recursive calls (n is 8, then 4, 2 and 1). But `halve(0)` calls `halve(0)` again and again, because `0 / 2` is 0 and the base case `n == 1` is never true.

## Common mix-ups

- Not true: All the recursive calls share one copy of the parameters, so a later call overwrites an earlier value. Each call gets its own set of local variables, including its parameters. When a call returns, the caller continues with its own values, unchanged.
- Not true: A method that prints after its recursive call prints in the same order as one that prints before it. Code after the recursive call runs only when the deeper calls have returned, so it runs in reverse order: deepest call first.
- Not true: Recursion can solve problems that loops cannot. Any recursive solution can be written with iteration, and any iterative solution can be written with recursion. Recursion is just another form of repetition.
- Not true: You must write recursive methods on the AP® exam. Writing recursive code is outside the scope of the AP® Computer Science A exam. You must be able to trace recursive methods and determine their results.

## In 30 seconds

- A recursive method calls itself; it needs at least one base case and at least one recursive call.
- Recursion is a form of repetition: the parameter moves toward the base case like a loop control variable moves toward the end.
- Each call has its own parameters and local variables; calls wait on the call stack until the deeper call returns.
- Trace by writing every call, then resolve the returns from the base case back up.
- Every recursive solution has an iterative version and every iterative solution has a recursive version.

## Checkpoint: 5 practice questions

### Question 1

Consider the following method. What value is returned by the call `mystery(10)`?

```java
public static int mystery(int n)
{
    if (n <= 0)
    {
        return 0;
    }
    return n + mystery(n - 3);
}
```

- A. 12
- B. 18
- C. 21
- D. 22

**Answer: D.** The calls are `mystery(10)`, `mystery(7)`, `mystery(4)`, `mystery(1)` and `mystery(-2)`, which is the base case and returns 0. Adding on the way back: 1 + 0, then 4 + 1, then 7 + 5, then 10 + 12 = 22. 21 and 18 drop one of the terms, and 12 is the value of `mystery(7)`.

### Question 2

Consider the following method. What is printed as a result of the call `show(3)`?

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

- A. 3 2 1
- B. 1 2 3
- C. 0 1 2 3
- D. 3 2 1 0

**Answer: B.** The print statement comes after the recursive call, so each call waits until the deeper calls finish. `show(0)` prints nothing; then `show(1)` prints 1, `show(2)` prints 2 and `show(3)` prints 3. 3 2 1 is the order for a print before the call, and the options with 0 forget that the base case prints nothing.

### Question 3

Consider the following method. How many times is `halves` called as a result of the call `halves(20)`, including the original call?

```java
public static int halves(int n)
{
    if (n < 1)
    {
        return 0;
    }
    return 1 + halves(n / 2);
}
```

- A. 6
- B. 5
- C. 4
- D. 20

**Answer: A.** The parameter takes the values 20, 10, 5, 2, 1 and 0. The call with 0 is the base case, so there are 6 calls in total (and the method returns 5). 5 is the return value, not the number of calls, 4 forgets the first or the last call, and 20 assumes the parameter goes down by 1.

### Question 4

Consider the following method. Which of the following code segments stores in `r` the same value that `total(n)` returns, for every `n` greater than or equal to 1?

```java
public static int total(int n)
{
    if (n == 0)
    {
        return 0;
    }
    return n * n + total(n - 1);
}
```

- A. `int r = 0; for (int i = 1; i < n; i++) { r += i * i; }`
- B. `int r = 1; for (int i = 1; i <= n; i++) { r *= i; }`
- C. `int r = 0; for (int i = 1; i <= n; i++) { r += i * i; }`
- D. `int r = 0; for (int i = 0; i <= n; i++) { r += i; }`

**Answer: C.** `total(n)` adds n * n, then (n - 1) * (n - 1), down to the base case at 0, so it returns the sum of the squares from 1 to n. The loop from 1 to n that adds `i * i` is the iterative version. The loop with `i < n` misses the last square, the loop with `r *= i` computes a factorial, and the last loop adds the numbers instead of their squares.

### Question 5

Consider the following method. What value is returned by the call `twist(5)`?

```java
public static int twist(int x)
{
    if (x <= 2)
    {
        return x;
    }
    int y = x - 1;
    int z = twist(y) * 2;
    return z - y;
}
```

- A. -2
- B. 2
- C. 1
- D. 4

**Answer: A.** Each call has its own `x`, `y` and `z`. `twist(2)` is a base case and returns 2. In `twist(3)`, y is 2 and z is 4, so it returns 2. In `twist(4)`, y is 3 and z is 4, so it returns 1. In `twist(5)`, y is 4 and z is 2, so it returns -2. 2 and 1 are the values of `twist(3)` and `twist(4)`, and 4 is the value of `z` inside `twist(3)`.

## Questions students ask

**What is a base case in recursion?**

A base case is a condition where a recursive method returns without calling itself again. It halts the recursion. Without a reachable base case, the method calls itself until the program runs out of stack memory.

**How do you trace a recursive method on the AP® exam?**

Write each call on its own line with its parameter values until you reach the base case. Then work back up, replacing each call with the value it returns, until you reach the original call.

**Do you have to write recursive code on the AP® Computer Science A exam?**

No. Writing recursive code is outside the scope of the exam. You need to determine the result of calling recursive methods, including recursive searching and sorting algorithms.

**What happens if a recursive method has no base case?**

The calls never stop. Each call takes space on the call stack until Java runs out and throws a StackOverflowError.

---

© LockInCS, licensed CC BY-NC-ND 4.0. AP® is a trademark registered by the College Board, which is not affiliated with, and does not endorse, this website.