Recursion: Factorial, Fibonacci, and Overlapping Subproblems

Functional vs. Parameterized Recursion

Before diving into the problems, it's useful to understand two common ways to structure a recursive function, a distinction that Striver explains well.

1. Parameterized Recursion: The function doesn't return a value. Instead, it carries the answer down through the recursive calls as a parameter, and a final action (like printing) is performed in the base case.
2. Functional Recursion: The function returns a value. Each recursive call returns a partial result, which is then combined with other values to compute the final answer that is returned up the call stack.

For interview preparation, functional recursion is generally more versatile, as it allows you to use the result of one function as an input to another. We'll focus on this style.

Implementing Factorial Recursively

As you saw in the video, calculating the factorial of a number n (denoted as $n!$) is a classic example of functional recursion. The problem is defined by a simple recurrence relation:

with the base case being $0!=1$.

The recursive function mirrors this definition almost perfectly:

1. Base Case: If n is 0 (or 1), return 1.
2. Recursive Step: Otherwise, return n multiplied by the result of calling the function with n-1.

Here is the Java implementation:

public class Factorial {
    public static int factorial(int n) {
        // Base case
        if (n <= 1) {
            return 1;
        }
        // Recursive step
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        int number = 5;
        System.out.println("Factorial of " + number + " is: " + factorial(number)); // Output: 120
    }
}

The call stack for factorial(5) would look like a straight line, as each function call makes only one subsequent recursive call. This results in a time complexity of $O(n)$ and a space complexity of $O(n)$ due to the depth of the recursion stack.

Multiple Recursion Calls: The Fibonacci Series

Now, let's turn to a problem that introduces a new level of complexity: the Fibonacci series. This sequence starts with 0 and 1, and each subsequent number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, ...

The recurrence relation is:

with base cases $\text{fib}(0)=0$ and $\text{fib}(1)=1$.

Unlike factorial, the recursive step here involves two recursive calls. This is a fundamental pattern known as multiple recursion.

Identifying Overlapping Subproblems

As you saw in the video, the recursion tree for Fibonacci is not a straight line; it's a branching tree. Let's look at the tree for fib(5).

This tree reveals a massive inefficiency. To calculate fib(5), we calculate fib(3) twice. To calculate fib(4), we need fib(3) and fib(2). But the call to fib(3) will also recalculate fib(2). This redundant computation is what we call overlapping subproblems.

The naive recursive implementation in Java looks like this:

public class Fibonacci {
    public static int fib(int n) {
        // Base cases
        if (n <= 1) {
            return n;
        }
        // Recursive step with multiple calls
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        int number = 5;
        System.out.println("Fibonacci of " + number + " is: " + fib(number)); // Output: 5
    }
}

Because the number of calls roughly doubles at each level of the tree, the time complexity is exponential, approximately $O(2^n)$. This is extremely slow. Calculating fib(40) would already take billions of operations.

A First Look at Optimization: Memoization

So, how do we fix the problem of overlapping subproblems? The answer is simple in concept: if you've already computed the result for a subproblem (like fib(3)), store it somewhere. The next time you need it, just look it up instead of re-computing it. This technique is called memoization.

It's a way of trading a little bit of space (to store the results) for a massive gain in time.

By using memoization, we ensure that fib(k) for any k is calculated only once. The recursion tree is effectively "pruned." All the repeated branches are cut off.

The improved complexities are:

• Time Complexity: $O(n)$, because each fib(i) from 0 to n is computed exactly once.
• Space Complexity: $O(n)$, for the recursion stack depth and the memoization array.

This dramatic improvement from $O(2^n)$ to $O(n)$ shows the power of identifying and solving the issue of overlapping subproblems. This exact idea—solving recursive problems while caching results—is the core principle behind memoization-based dynamic programming, a topic we will explore in depth in a later module.

Key Takeaways

• Functional Recursion is a powerful pattern where functions return results that are combined up the call stack. It's highly applicable to many algorithmic problems.
• Simple recursive problems like Factorial have a linear call structure, leading to $O(n)$ time complexity.
• Problems like Fibonacci that use multiple recursive calls can have a branching call structure.
• A recursion tree is an essential tool for visualizing the execution of a recursive function and identifying its performance characteristics.
• When a recursion tree shows the same subproblem being solved multiple times, you have identified overlapping subproblems. This is a major source of inefficiency, often leading to exponential time complexity.
• Memoization is the technique of storing the results of expensive function calls and returning the cached result when the same inputs occur again. It transforms exponential-time recursive solutions into linear-time solutions for problems with overlapping subproblems.

Conclusion

You have now completed the foundational module of this course. You've mastered complexity analysis, call stack tracing, bit manipulation, and now, the crucial patterns of recursion. You've seen how a seemingly simple problem like Fibonacci can expose deep algorithmic principles.

In our next lesson, we will begin Module 2: "Arrays & Hashing." We will start with a practical deep dive into ArrayList, Java's implementation of a dynamic array, understanding its operations and their associated time complexities. This will be our first step into studying concrete data structures.