Recursion Basics

1. Introduction: The Mirror in the Mirror

Have you ever held two mirrors facing each other? You look into one and see an infinite tunnel of reflections, each slightly smaller than the last.

In computer science, Recursion is a function that calls itself. Instead of using a for or while loop, a recursive function solves a massive problem by breaking it into a slightly smaller piece, and handing that smaller piece to a clone of itself.

Recursion is the cornerstone of advanced algorithms. Trees, Graphs, Dynamic Programming, and Divide & Conquer all rely on recursive logic. If you do not understand the recursive call stack, you cannot pass a technical interview.

2. Core Concept: The Two Pillars of Recursion

Every valid recursive function must have two absolutely critical components:

1. The Base Case: The condition where the function stops calling itself and returns a concrete answer. Without a base case, the mirrors reflect forever, resulting in a StackOverflowError.
2. The Recursive Step: The function calls itself with a modified input that is strictly closer to the base case.

The Call Stack: When Function A calls Function B, Function A pauses. The operating system places Function A on the "Call Stack" and runs Function B. If Function B calls Function C, both A and B are paused. When Function C hits a base case and returns, it is popped off the stack, and Function B resumes exactly where it left off!

3. Beginner Code Example: Factorial

Problem Statement: Calculate the factorial of $N$ ($N!$). $5! = 5 \times 4 \times 3 \times 2 \times 1$.

The Insight: $5! = 5 \times 4!$. We can define the mathematical operation in terms of itself!

public class Factorial {
    public static int calcFactorial(int n) {
        // 1. The Base Case: We know that 1! is 1. We stop here.
        if (n <= 1) {
            return 1;
        }
        
        // 2. The Recursive Step: Multiply current number by the factorial of (n-1)
        // We PAUSE execution here and wait for calcFactorial(n-1) to finish!
        int subAnswer = calcFactorial(n - 1);
        
        // 3. Return the combined result
        return n * subAnswer;
    }
}

Trace for calcFactorial(3):

1. calcFactorial(3) sees 3 > 1. Calls calcFactorial(2). (Pauses).
2. calcFactorial(2) sees 2 > 1. Calls calcFactorial(1). (Pauses).
3. calcFactorial(1) hits base case. Returns 1.
4. calcFactorial(2) resumes. 2 * 1 = 2. Returns 2.
5. calcFactorial(3) resumes. 3 * 2 = 6. Returns 6.

4. Intermediate Code Example: Fibonacci Sequence

Problem Statement: (LeetCode 509) The Fibonacci numbers are defined as F(n) = F(n-1) + F(n-2), with F(0) = 0 and F(1) = 1. Return F(n).

The Insight: This requires Multiple Branching Recursion. One function call spawns TWO new function calls.

public class Fibonacci {
    public static int fib(int n) {
        // Base Cases
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        // The "Leap of Faith"
        // We assume fib(n-1) and fib(n-2) will magically return the correct answers.
        int leftBranch = fib(n - 1);
        int rightBranch = fib(n - 2);
        
        return leftBranch + rightBranch;
    }
}

The Danger: Branching recursion creates an exponentially growing tree of function calls. fib(5) calls fib(4) and fib(3). But fib(4) ALSO calls fib(3)! The exact same calculation is executed multiple times.

• Time Complexity: $O(2^N)$. This will freeze your computer for $N=50$.
• Space Complexity: $O(N)$ for the call stack height. (Note: To fix this, we use Dynamic Programming / Memoization).

5. Advanced Code Example: Reversing a String

Problem Statement: (LeetCode 344) Reverse a string array in-place. You cannot use loops.

The Insight: A recursive function doesn't just pass return values up the stack; it can mutate state as it drills down the stack. We use Two Pointers, but instead of a while loop, we pass the pointers as parameters to the recursive function.

public class ReverseString {
    public void reverseString(char[] s) {
        // Kick off the recursion with the initial boundaries
        helper(s, 0, s.length - 1);
    }
    
    private void helper(char[] s, int left, int right) {
        // Base Case: Pointers met or crossed. 
        if (left >= right) {
            return;
        }
        
        // Action: Swap the current characters
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        
        // Recursive Step: Shrink the window and pass it to the next function
        helper(s, left + 1, right - 1);
    }
}

6. Common Mistakes Beginners Make

1. Forgetting the Base Case (Infinite Loop)

   • The Mistake: Writing return n * factorial(n-1); without an if statement.
   • Why it's wrong: The function will call factorial(-1), then factorial(-2), plunging into negative infinity until Java throws a StackOverflowError and crashes.

2. Not modifying the parameter

   • The Mistake: return factorial(n);
   • Why it's wrong: The input must get strictly closer to the base case. If you pass the exact same input, you create an infinite loop.

3. Not returning the recursive call

   • The Mistake:

   if (n == 0) return 0;
   fib(n-1); 
   // Missing return statement!
   

   • Why it's wrong: The sub-function computed the answer, but the parent function threw it away because it didn't capture or return the value.

7. Interview Q&A

Q1: What is Tail Recursion? Answer: Tail recursion occurs when the recursive call is the absolute final action in the function (e.g., return recurse(n-1);). There is no math done after the function returns. Some languages (like C++ or Scala) optimize this by reusing the exact same stack frame, converting the recursion into a while loop under the hood to achieve $O(1)$ space. (Note: Java does NOT support tail-call optimization!).

Q2: How do you choose between Recursion and Iteration (Loops)? Answer: Any recursive algorithm can be written iteratively using a custom Stack. Iteration is physically faster and safer (no StackOverflow risk). However, recursion is significantly easier to read and write for non-linear structures like Trees, Graphs, and Backtracking permutations. Use iteration for Arrays/Strings; use recursion for Trees/Graphs.

Q3: What is the "Recursive Leap of Faith"? Answer: It is a mental model. When writing the recursive step, do not try to trace the code all the way down to the base case in your head. Your brain will crash. Just assume the recursive call recurse(n-1) perfectly works and returns the correct answer. Focus only on what the current function should do with that answer.

8. Practice Problems

1. Fibonacci Number (LeetCode 509)
   • Goal: Master branching recursion.
2. Reverse String (LeetCode 344)
   • Goal: Master passing state via parameters.
3. Power of Two (LeetCode 231)
   • Hint: Base cases: n==1 return true. n==0 or n%2!=0 return false. Return isPowerOfTwo(n/2).

9. Summary

• The Blueprint: Every recursive function starts with a Base Case if statement, followed by the Recursive Call.
• The Call Stack: Pauses the current function, saves local variables, and executes the child function.
• Leap of Faith: Trust that the child function will return the correct answer. Only worry about how the parent should combine the child's answer.
• Danger: Branching recursion often yields $O(2^N)$ time limits.