Understand the idea

A recursive method calls itself with a smaller or simpler input. Define the base case first, then explain why each call moves toward it. Recursion consumes stack space; a mathematically elegant solution is not always the best production implementation.

Explore the details

Java Recursion

Recursion is the technique of making a function call itself. This technique provides a way to break complicated problems down into simpler problems which are easier to solve.

Recursion may be a bit difficult to understand. The best way to figure out how it works is to experiment with it.

Recursion Example

Adding two numbers together is easy to do, but adding a range of numbers is more complicated. In the following example, recursion is used to add a range of numbers together by breaking it down into the simple task of adding two numbers:

Example Explained

When the sum() method is called, it adds parameter k to the sum of all numbers smaller than k and returns the result. When k becomes 0, the method just returns 0. When running, the program follows these steps:

Since the method does not call itself when k is 0, the program stops there and returns the result.

Halting Condition

Just as loops can run into the problem of infinite looping, recursive methods can run into the problem of infinite recursion. Infinite recursion is when the method never stops calling itself. Every recursive method should have a halting condition, which is the condition where the method stops calling itself. In the previous example, the halting condition is when the parameter k becomes 0.

It is helpful to see a variety of different examples to better understand the concept. In this example, the method adds a range of numbers between a start and an end. The halting condition for this recursive method is when end is not greater than start:

Countdown with Recursion

This example demonstrates how to use recursion to create a countdown function:

The method calls itself with n - 1 until n becomes 0.

Fibonacci Sequence with Recursion

The Fibonacci sequence is a classic recursion example. Each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13 …

static int fibonacci(int n) {
    if (n <= 1) return n;           // base cases: fib(0)=0, fib(1)=1
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// Print first 8 Fibonacci numbers
for (int i = 0; i < 8; i++) {
    System.out.print(fibonacci(i) + " ");
}
// Output: 0 1 1 2 3 5 8 13

Golden Rules of Recursion

1. Always have a base case — the condition that stops recursion (e.g., if (n <= 0) return)
2. Move toward the base case — every recursive call must bring you closer to stopping
3. Trust the recursion — assume the recursive call correctly solves the smaller sub-problem
4. Watch for stack overflow — deeply nested calls consume memory; consider iteration for large inputs

Calculate Factorial with Recursion

This example uses a recursive method to calculate the factorial of 5:

A complete runnable example

This complete Main.java program focuses on the lesson idea. Reference fragments above may demonstrate individual statements; this example includes the imports, entry point, and supporting types it needs.

public class Main {
    public static void main(String[] args) throws Exception {
        System.out.println(Sums.upTo(4));
    }
}
class Sums {
    static int upTo(int n) {
        if (n <= 0) return 0;
        return n + upTo(n - 1);
    }
}

10

Change it. Run it. Understand it.

Load this lesson example into the editor. Change one value or statement, predict the result, then press RUN to execute Java.

Make it your own

Your learning checkpoint

• Explain the example without reading the output first.
• Make the change requested in the practice task.
• Describe why the result changed—or why compilation failed.

Ready to move on? Follow the next lesson in course order, or return to the curriculum to review a prerequisite.