Exploring the Basics of Recursion (Java)

Meet the Author: Marco Ni

Hello readers! Welcome to this tutorial, where we’ll break down recursion, provide simple examples, and demonstrate how this powerful technique can simplify complex problems.

What is Recursion?

Recursion is a technique where a function calls itself to solve smaller instances of the same problem. This self-referential approach can make certain problems easier to solve by breaking them down into simpler, more manageable parts.

How Does Recursion Work?

A recursive function generally has two main components:

1. Base Case: The condition under which the recursion stops. This is crucial to prevent infinite loops and eventually provide a solution.
2. Recursive Case: The part of the function where it calls itself with modified arguments, moving closer to the base case.

Let’s break this down with a classic example.

Example 1: Factorial Function

The factorial of a non-negative integer n (denoted as n!) is the product of all positive integers less than or equal to n. It’s defined as:

• 0! = 1 (Base Case)
• n! = n * (n - 1)! (Recursive Case)

Here’s how you would implement this in Java:

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

    public static void main(String[] args) {
        System.out.println(factorial(5)); // Output: 120
    }
}

When factorial(5) is called, the function calls itself with decreasing values of n until it reaches the base case, ultimately calculating 5 * 4 * 3 * 2 * 1.

Example 2: Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. The sequence looks like this: 0, 1, 1, 2, 3, 5, 8, …

It’s defined as:

• F(0) = 0 (Base Case)
• F(1) = 1 (Base Case)
• F(n) = F(n - 1) + F(n - 2) (Recursive Case)

Here’s a Java implementation:

public class RecursionExamples {
    public static int fibonacci(int n) {
        // Base cases
        if (n <= 1) {
            return n;
        }
        // Recursive case
        else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(5)); // Output: 5
    }
}

The function fibonacci(5) would return 5 by adding the results of fibonacci(4) and fibonacci(3), continuing until it reaches the base cases.

When to Use Recursion

Recursion is particularly useful when:

• The problem can be divided into similar subproblems.
• A problem can be naturally expressed in terms of smaller subproblems (like the factorial or Fibonacci sequence).
• The iterative solution is complex or not straightforward.

However, recursion might not be the best choice for every problem. It can lead to high memory usage and stack overflow if the recursion depth is too large. For these cases, iterative solutions or optimizations like memoization may be preferred.

Works Cited

1. GeeksforGeeks. “Recursion in C/C++.” GeeksforGeeks, 2024, https://www.geeksforgeeks.org/recursion/.
2. Techopedia. “What is Recursion?” Techopedia, 2024, https://www.techopedia.com/definition/6202/recursion.