Recursion — Data Structure & Algrorithm

Sometimes a problem can be solved by breaking it into smaller versions of the same problem.

This is where recursion becomes useful.

Recursion is a technique where a function calls itself to solve a smaller part of the problem.

It might sound confusing at first, but the basic idea is actually quite simple.

Imagine you are standing in front of a staircase and want to reach the top. You could think:

"First, reach the next step. Then from there, reach the next step, and keep doing the same thing."

The same idea can be applied to many programming problems.

A Simple Recursive Function

Let's start with a very simple example:

static void countDown(int n) {

    if (n == 0) {
        return;
    }

    System.out.println(n);

    countDown(n - 1);
}

We can call it:

countDown(5);

The execution looks like:

countDown(5)
     ↓
countDown(4)
     ↓
countDown(3)
     ↓
countDown(2)
     ↓
countDown(1)
     ↓
countDown(0)

The output is:

Notice what happened. The countDown() method kept calling itself with a smaller value.

That's recursion.

The Two Important Parts of Recursion

Every recursive solution needs two important things:

Base case

The condition that tells the function when to stop.

Recursive case

The part where the function calls itself with a smaller or simpler version of the problem.

In our example:

if (n == 0) {
    return;
}

is the base case.

And:

countDown(n - 1);

is the recursive case.

Without a base case, the function could keep calling itself forever.

Why Do We Need a Base Case?

Consider this:

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

There's no condition telling the function to stop.

So it keeps calling itself:

hello()
 ↓
hello()
 ↓
hello()
 ↓
hello()
 ↓
...

Eventually, Java will run out of space in the call stack and throw a StackOverflowError.

That's why the base case is extremely important in recursion.

Factorial Using Recursion

One of the most common examples of recursion is calculating a factorial.

The factorial of 5 is:

5 × 4 × 3 × 2 × 1 = 120

We can write:

static int factorial(int n) {

    if (n == 0 || n == 1) {
        return 1;
    }

    return n * factorial(n - 1);
}

Then:

System.out.println(factorial(5));

Output:

Let's see what happens internally:

factorial(5)
→ 5 × factorial(4)
→ 5 × 4 × factorial(3)
→ 5 × 4 × 3 × factorial(2)
→ 5 × 4 × 3 × 2 × factorial(1)

At factorial(1), the base case returns 1.

Then the results start coming back:

1
↓
2 × 1 = 2
↓
3 × 2 = 6
↓
4 × 6 = 24
↓
5 × 24 = 120

This is one of the key ideas behind recursion: the function keeps going deeper and then the results return back up.

Recursion and the Call Stack

To understand recursion properly, you should know about the call stack.

Whenever a method is called, Java creates a stack frame to keep track of that method's execution.

With recursion, every recursive call creates another stack frame.

For:

factorial(5)

the stack roughly looks like:

factorial(1)
factorial(2)
factorial(3)
factorial(4)
factorial(5)
main()

Once the base case is reached, the calls start returning and their stack frames are removed.

This is why recursion uses additional memory.

For the factorial example, the recursion depth is n, so the space complexity is:

O(n)

Recursion with Arrays

Recursion can also be used to process arrays.

For example, let's print all elements of an array:

static void printArray(int[] numbers, int index) {

    if (index == numbers.length) {
        return;
    }

    System.out.println(numbers[index]);

    printArray(numbers, index + 1);
}

We can call:

int[] numbers = {10, 20, 30, 40, 50};

printArray(numbers, 0);

Output:

The function processes one element and then recursively moves to the next index.

Sum of Array Elements

We can also calculate the sum of an array recursively.

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, 40};

calling:

System.out.println(sum(numbers, 0));

gives:

The recursion can be understood as:

10 + sum(index 1)
        ↓
20 + sum(index 2)
        ↓
30 + sum(index 3)
        ↓
40 + sum(index 4)
        ↓
0

Then the results are added while the calls return.

Recursion vs Loop

Many recursive problems can also be solved using loops.

For example, counting from 1 to 5 using a loop:

for (int i = 1; i <= 5; i++) {
    System.out.println(i);
}

Using recursion:

static void count(int n) {

    if (n > 5) {
        return;
    }

    System.out.println(n);

    count(n + 1);
}

Both can produce:

So you might ask:

"Why use recursion if a loop can do the same thing?"

The answer is that recursion can make certain problems much easier to express, especially when the problem naturally has a recursive structure.

When is Recursion Useful?

Recursion is particularly useful for problems involving:

Trees
Graphs
Divide and conquer
Backtracking
Searching through nested structures
Mathematical problems
Problems that can be broken into smaller versions of themselves

For example, traversing a tree naturally involves visiting smaller subtrees, so recursion often makes the solution much cleaner.

Multiple Recursive Calls

A function doesn't necessarily have to call itself only once.

For example, the Fibonacci sequence can be defined recursively:

0, 1, 1, 2, 3, 5, 8, 13...

A recursive implementation could be:

static int fibonacci(int n) {

    if (n <= 1) {
        return n;
    }

    return fibonacci(n - 1) + fibonacci(n - 2);
}

For example:

System.out.println(fibonacci(6));

Output:

Here, each call creates two more recursive calls, which creates a branching structure.

This simple implementation is quite inefficient for larger values because many calculations are repeated. Later, when we study dynamic programming, you'll see how this problem can be optimized.

Recursion Doesn't Always Mean Faster

This is another important point.

Recursion is a technique for solving problems. It doesn't automatically make a program faster.

Sometimes a recursive solution is easier to understand but uses more memory or performs more operations than an iterative solution.

For example, the simple recursive Fibonacci solution has exponential time complexity:

O(2ⁿ)

because it repeatedly calculates the same values.

So when using recursion, we should still think about time and space complexity.

A Real-Life Example

Imagine you have a folder on your computer that contains files and other folders.

Inside one folder, there might be another folder, which contains another folder, and so on.

You want to find a particular file.

You can:

Open folder
   ↓
Check files
   ↓
Open each subfolder
   ↓
Repeat the same process

The process of checking a folder is basically the same whether you're looking at the first folder or a folder several levels deep.

That's exactly the kind of situation where recursion can be useful.

A Complete Example

Let's write a program that reverses a string using recursion:

static void reverse(String text, int index) {

    if (index < 0) {
        return;
    }

    System.out.print(text.charAt(index));

    reverse(text, index - 1);
}

We can call:

String text = "John";

reverse(text, text.length() - 1);

Output:

nhoJ

The function starts from the last character and recursively moves toward the first character.

The Most Important Thing to Remember

When you're solving a recursive problem, ask yourself three questions:

1. What is the smallest version of this problem?
2. What is the base case?
3. How can I reduce the problem and call the function again?

For example, with factorial:

factorial(n)
     ↓
n × factorial(n - 1)

and eventually:

factorial(1)

which is our base case.

The main idea is:

Recursion is a technique where a function solves a problem by calling itself on a smaller version of that problem.

The two most important parts are the base case, which stops the recursion, and the recursive case, which reduces the problem and calls the function again.

Once you understand these two ideas, recursion becomes much less mysterious. The real challenge is learning to recognize when a problem can naturally be broken down into smaller versions of itself.