Introduction to Recursion

Lesson Overview

So far, we have used loops to perform repeated work:

for (int number = 5; number >= 1; number--) {
    System.out.println(number);
}

Another technique for expressing repetition is recursion. In recursion, a method calls itself to solve a smaller version of the same problem:

static void countDown(int number) {
    if (number == 0) {
        return;
    }

    System.out.println(number);
    countDown(number - 1);
}

Recursion matters because some problems, such as folders inside folders or the branches of a tree, are naturally made of smaller copies of themselves, and recursion expresses them directly. In this lesson, we will learn how a recursive method stops, how its calls run and return, and when a plain loop is the better choice.

Learning Objectives

After completing this lesson, you will be able to:

• Explain recursion
• Identify a base case and recursive case
• Understand how recursive input moves toward a smaller problem
• Write a simple recursive method
• Trace recursive calls
• Use a returned recursive result
• Process an array recursively
• Identify causes of infinite recursion
• Choose appropriately between loops and recursion

What Is Recursion?

Recursion is a technique where a method calls itself to solve a smaller or simpler version of a problem. Basic structure:

static void recursiveMethod(int value) {
    if (stoppingCondition) {
        return;
    }

    recursiveMethod(smallerValue);
}

A correct recursive solution usually has two important parts: a base case and a recursive case.

Base Case and Recursive Case

The base case defines when recursion should stop:

if (number == 0) {
    return;
}

Without a base case, the method keeps calling itself until the program fails with a StackOverflowError (explained later in this lesson).

The recursive case, countDown(number - 1);, reduces the current problem to a smaller problem. If we start with 5, the calls receive 5, 4, 3, 2, 1 and 0, and 0 reaches the base case.

First Recursive Method

public class Main {

    public static void main(String[] args) {
        countDown(5);
    }

    static void countDown(int number) {
        if (number == 0) {
            return;
        }

        System.out.println(number);
        countDown(number - 1);
    }
}

Output:

5
4
3
2
1

Execution Trace

The flow of the call countDown(3):

countDown(3)
↓
print 3
↓
countDown(2)
↓
print 2
↓
countDown(1)
↓
print 1
↓
countDown(0)
↓
return

A Recursive Call Must Make Progress

Correct:

countDown(number - 1);

Each call moves toward 0. Wrong:

countDown(number);

The input does not change. Therefore:

countDown(5)
→ countDown(5)
→ countDown(5)
→ ...

The base case is never reached.

Recursion and the Call Stack

When a method is called, Java needs to remember:

• Which method invocation is active
• Its parameters
• Its local variables
• Where execution should return when the method finishes

With recursion, multiple invocations of the same method can be active at the same time. Conceptually, countDown(3) looks like this:

countDown(3)
    countDown(2)
        countDown(1)
            countDown(0)

The deepest call finishes first. Then execution returns to the previous calls.

Going Down and Coming Back Up

Consider:

static void show(int number) {
    if (number == 0) {
        return;
    }

    System.out.println("Before: " + number);
    show(number - 1);
    System.out.println("After: " + number);
}

Output of show(3):

Before: 3
Before: 2
Before: 1
After: 1
After: 2
After: 3

Why Does the Output Return in Reverse Order?

Calls go downward:

show(3)
→ show(2)
→ show(1)
→ show(0)

But after show(0) returns, previous calls resume:

show(1)
→ show(2)
→ show(3)

Therefore, code before the recursive call executes during the downward journey, and code after the recursive call executes during the return journey.

So the position of one println decides the order: printing before the recursive call counts down, and printing only after it counts up. Predict the Result Questions 1 and 2 test exactly this.

Difference Between Recursion and Loops

The loop in the overview and countDown() print the same numbers. Both can express repetition. However, their execution models are different: a loop repeats within the same method invocation, while recursion creates a new method invocation for every step.

A Recursive Method Can Return a Value

Recursion is not limited to void methods:

static int sumTo(int number) {
    if (number == 0) {
        return 0;
    }

    return number + sumTo(number - 1);
}

Sum from 1 to n

We want sumTo(5) to calculate 5 + 4 + 3 + 2 + 1, which is 15. Think of it as sumTo(5) = 5 + sumTo(4), then sumTo(4) = 4 + sumTo(3). The general form and the base case are:

sumTo(n) = n + sumTo(n - 1)
sumTo(0) = 0

Trace sumTo(3)

sumTo(3)
= 3 + sumTo(2)

= 3 + 2 + sumTo(1)

= 3 + 2 + 1 + sumTo(0)

= 3 + 2 + 1 + 0

= 6

Factorial

Factorial is a classic recursion example: 5! = 5 × 4 × 3 × 2 × 1 = 120. The recursive relationship is n! = n × (n - 1)!, and the base case is 0! = 1.

static long factorial(int number) {
    if (number == 0) {
        return 1;
    }

    return number * factorial(number - 1);
}

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

= 24

The Base Case Result Is Important

Wrong:

if (number == 0) {
    return 0;
}

Then factorial(1) is 1 × 0 = 0, and every higher result will also become 0. Correct, because 0! = 1:

return 1;

How Does a Recursive Return Value Work?

Consider:

return number * factorial(number - 1);

The current method invocation does not immediately know the final result. It first needs the result of the smaller call:

factorial(3)

needs
factorial(2)

which needs
factorial(1)

which needs
factorial(0)

Once the base result is available, the answers are calculated during the return journey.

Traversing an Array Recursively

Suppose we have int[] numbers = {10, 20, 30};. Instead of using a loop, the index can be advanced recursively:

static void print(int[] numbers, int index) {
    if (index == numbers.length) {
        return;
    }

    System.out.println(numbers[index]);
    print(numbers, index + 1);
}

Output of print(numbers, 0):

10
20
30

Base Case for Array Recursion

The base case index == numbers.length means there are no more valid array elements. Progress comes from index + 1: each recursive call moves to the next position.

Recursive Array Sum

static int sum(int[] numbers, int index) {
    if (index == numbers.length) {
        return 0;
    }

    return numbers[index] + sum(numbers, index + 1);
}

For int[] numbers = {10, 20, 30};, the flow is:

sum(numbers, 0)
=
10 + sum(numbers, 1)

=
10 + 20 + sum(numbers, 2)

=
10 + 20 + 30 + sum(numbers, 3)

=
10 + 20 + 30 + 0

=
60

Hiding the Internal Index

The caller does not need to know that recursion internally uses sum(numbers, 0). A wrapper overload, placed next to the two-parameter sum above, can hide it:

static int sum(int[] numbers) {
    return sum(numbers, 0);
}

Now the caller simply writes int total = sum(numbers);.

Recursive Search

static boolean contains(int[] numbers, int target) {
    return contains(numbers, target, 0);
}

static boolean contains(int[] numbers, int target, int index) {
    if (index == numbers.length) {
        return false;
    }

    if (numbers[index] == target) {
        return true;
    }

    return contains(numbers, target, index + 1);
}

Here, recursion can stop in two ways: it returns true when the target is found, and false when the end of the array is reached.

Infinite Recursion

Wrong:

static void greet() {
    System.out.println("Hello");
    greet();
}

There is no base case. The method keeps calling itself until the program fails with a StackOverflowError.

A base case alone is not enough. countDown(number) without - 1, shown in A Recursive Call Must Make Progress, has a base case that is never reached, and so does a call that moves the wrong way.

Wrong Direction

static void countDown(int number) {
    if (number == 0) {
        return;
    }

    countDown(number + 1);
}

For a positive input, recursion moves farther away from zero. Correct direction:

countDown(number - 1);

StackOverflowError

Each recursive call creates a new method invocation. If too many recursive calls remain active, the available call-stack space can be exhausted. The program then stops with an error like this (followed by a long list of the method calls that were still active):

Exception in thread "main" java.lang.StackOverflowError

Common causes:

• Missing base case
• Wrong recursive direction
• Input not progressing toward the base case
• Extremely deep recursion

Approach to Fixing StackOverflowError

The goal is to correct the recursion design, not to catch the error and keep the recursion running. The three questions in the next section are the checklist.

Three Questions for Recursion

When designing a recursive solution, ask:

1. What Is the Smallest Problem?

The problem that can be solved directly. This becomes the base case.

2. How Does the Current Problem Become Smaller?

This becomes the recursive step.

3. Will Every Recursive Path Reach the Base Case?

If not, the recursion will not terminate.

Recursion vs. Iteration

Compare the recursive sumTo() from earlier with the same problem solved by a loop:

static int sumTo(int number) {
    int total = 0;

    for (int current = 1; current <= number; current++) {
        total += current;
    }

    return total;
}

For this particular problem, the loop is simpler.

When Should You Prefer a Loop?

For straightforward sequential work, loops are generally simpler:

• Print 1–100
• Sum an array
• Count array values
• Linear traversal
• Simple search
• Fixed repetition

These problems can be written recursively, but recursion is not necessary.

When Can Recursion Be Natural?

Recursion is useful when the problem is naturally composed of smaller versions of itself. Future examples:

• Tree traversal
• Nested directory structures
• Divide-and-conquer algorithms
• Backtracking

These will become more meaningful when we study algorithms.

Recursion Does Not Automatically Mean Better

A method such as static int sum(int[] numbers, int index) is useful for learning. However, for a simple array sum in production code, a for (int number : numbers) loop is generally clearer. Choose recursion when it makes the problem structure clearer.

Important Terms

Recursion

A technique where a method calls itself to solve a smaller version of a problem.

Base Case

The condition that stops recursion.

Recursive Case

The part that calls the method again with smaller input.

Recursive Call

A method calling itself.

Call Stack

A runtime structure that tracks the execution state of active method invocations.

Recursion Depth

The number of nested recursive calls active at the same time.

StackOverflowError

An error that can occur when too many nested method calls exhaust available stack space.

Predict the Result

Question 1

static void show(int number) {
    if (number == 0) {
        return;
    }

    System.out.print(number + " ");
    show(number - 1);
}

What does show(3) print?

Answer

3 2 1 

Each call prints its number before making the smaller call, so the numbers appear on the way down.

Question 2

static void show(int number) {
    if (number == 0) {
        return;
    }

    show(number - 1);
    System.out.print(number + " ");
}

What does show(3) print?

Answer

1 2 3 

Each call first waits for the smaller call to finish and prints afterwards. show(1) finishes first, so 1 is printed first, as the calls return.

Question 3

static void echo(int number) {
    if (number == 0) {
        return;
    }

    System.out.print(number + " ");
    echo(number - 1);
    System.out.print(number + " ");
}

What does echo(2) print?

Answer

2 1 1 2 

The first print runs on the way down (2, then 1). The second runs on the way back up, after each smaller call returns (1, then 2).

Question 4

static int product(int number) {
    if (number == 0) {
        return 0;
    }

    return number * product(number - 1);
}

What does product(4) return?

Answer

0. The chain is 4 * 3 * 2 * 1 * product(0), and the base case returns 0, so the whole product becomes 0. For multiplication the base case should return 1, as in factorial.

Common Mistakes

A missing base case, an input that does not change, and a call that moves away from the base case all end in StackOverflowError; Infinite Recursion above shows each one. These mistakes are less obvious.

A Base Case the Input Can Jump Over

countDown() stops at number == 0. Called as countDown(-1), the input goes -1, -2, -3 and never equals 0, so the program ends in StackOverflowError. The same happens when a step is larger than one and skips the exact value. Write the base case so that every input reaches it, here if (number <= 0).

A Base Value That Breaks the Calculation

The base case returns a value that every other call builds on. 0 is right for a sum, but for a product it turns the whole result into 0 (Predict the Result, Question 4). Ask what the answer for the smallest problem really is: sumTo(0) is 0, and factorial(0) is 1.

Making a Simple Loop Problem Unnecessarily Recursive

For simple sequential traversal, recursion adds a new invocation and stack space for every element, and a large array can even cause StackOverflowError. If a clear loop is available, prefer the loop.

Practice Exercise 1: Count Digits

Solutions: lesson 2.11.

Create static int countDigits(int number) without a loop. Assume number is 0 or positive. countDigits(4096) returns 4, and countDigits(7) and countDigits(0) both return 1. Hint: number / 10 drops the last digit.

Practice Exercise 2: Print Upward

Write a recursive method where printUpTo(5) prints:

1
2
3
4
5

Practice Exercise 3: Power

Create static long power(int base, int exponent) using recursion, for an exponent of 0 or more. power(2, 10) returns 1024, power(3, 4) returns 81, and power(5, 0) returns 1.

Practice Exercise 4: Reverse a String

Create static String reverse(String text) using recursion. reverse("Java") returns "avaJ", reverse("Nur") returns "ruN", and reverse("") returns "". Hint: the reverse of a text is the reverse of everything after its first character, followed by that first character.

Practice Exercise 5: Recursive Count

Create static int count(int[] numbers, int target), which returns how many elements equal target, using a recursive helper with an index instead of a loop. For {4, 7, 4, 9, 4} and target 4, it returns 3; for target 5, it returns 0.

Practice Exercise 6: Palindrome Check

Create static boolean isPalindrome(String text) using recursion. A palindrome reads the same forwards and backwards: "level" and "noon" give true, "java" gives false, and an empty or one-character text gives true. Compare the first and last characters, then check what lies between them.

Practice Exercise 7: Find the Bug

static int sumTo(int number) {
    if (number == 0) {
        return 0;
    }

    return number + sumTo(number);
}

Why does the recursion never end?

Practice Exercise 8: Recursion or Loop?

For each case, decide whether recursion or a loop is generally more natural:

1. Print from 1 to 100
2. Sum all values in an array
3. Traverse a nested directory structure
4. Process the child nodes of a tree
5. Print a message exactly 10 times

Knowledge Check

Question 1

What is recursion?

Question 2

What is a base case?

Question 3

What is a recursive case?

Question 4

Why should recursive input become smaller or simpler?

Question 5

What happens to the current method invocation when a recursive call occurs?

Question 6

Why can code before and after a recursive call execute in different orders?

Question 7

What is factorial(0)?

Question 8

What should the base value of sumTo(0) be?

Question 9

When does an array recursion index reach the base case?

Question 10

Is having a base case alone enough to make recursion safe?

Question 11

Why can StackOverflowError occur?

Question 12

Why is a loop often preferable for simple linear array traversal?

Question 13

For what kinds of problems can recursion be natural?

Question 14

What are three important questions to ask when designing a recursive method?

Knowledge Check Answers

Answer 1

A technique where a method calls itself to solve a smaller or simpler version of a problem.

Answer 2

A stopping condition that prevents further recursive calls.

Answer 3

The part that reduces the current problem and calls the method again with smaller input.

Answer 4

So that the calls eventually reach the base case.

Answer 5

The current invocation remains active until the deeper method call finishes, then execution resumes.

Answer 6

The deeper call completes first, and control then returns to previous calls in reverse order.

Answer 7

1

Answer 8

0

Answer 9

When index == numbers.length.

Answer 10

No. The recursive input must also progress toward the base case.

Answer 11

Too many nested method invocations can exhaust the available call-stack space.

Answer 12

A loop provides a simpler execution flow and does not create an unnecessary recursive call stack.

Answer 13

Recursively structured problems such as trees or nested hierarchies.

Answer 14

Ask:

• What is the base case?
• How does the current problem become smaller?
• Will every recursive path reach the base case?

Lesson Summary

In this lesson, we learned:

• In recursion, a method calls itself on a smaller problem: the base case stops the calls, and the recursive case moves toward it
• Each call waits for the deeper call to return, so code before the recursive call runs on the way down and code after it runs on the way back up
• Recursive methods can return values that are combined on the way back, as in sumTo() and factorial(), whose base values must fit the calculation
• Arrays can be processed by recursively advancing an index, with a wrapper overload hiding that index from the caller
• A missing base case, or input that never reaches it, leads to StackOverflowError
• Loops are generally clearer for simple sequential work; recursion is natural for problems made of smaller copies of themselves, such as trees