Re 2. Problems on Recursion | Striver's A2Z DSA Course

This chapter dives into fundamental recursion problems, taking you step-by-step from writing basic parameter-based recursive functions to understanding the mechanics of Backtracking. By exploring how to print values linearly, in reverse, and through deferred execution, we build a solid mental model of the computer's internal call stack and execution flow.

1. Why Do We Need Parameter-Based Recursion?

When transitioning from iterative loops to recursive functions, managing state without global variables is crucial for writing clean, re-entrant, and thread-safe code.

• The Status Quo: Beginners often rely on global counters or static variables to keep track of state across recursive steps, which leads to bugs in concurrent environments and makes functions harder to test.
• The Solution: Passing state explicitly as parameters (i, n) through the function signature. This encapsulates the state within each stack frame, ensuring that every function call operates on its own isolated set of variables.

2. Core Mental Model: The Function Call Stack

To understand recursion, you must visualize how programming languages manage memory using the Call Stack. When a function calls another function, the execution of the current function pauses, and a new "stack frame" is pushed onto the stack.

Note: The stack operates on a Last-In, First-Out (LIFO) basis. The deepest recursive call reaches the base case first, returns, and then unwinds the stack frame by frame.

3. Problem 1: Print Name $N$ Times Using Recursion

Our first objective is to print a given name (e.g., "raj") $N$ times using recursion rather than a standard for loop.

Code Implementation (Java-style pseudo-code)

public class Solution {
    public static void printName(int i, int n) {
        // Base Case: Stop when i exceeds n
        if (i > n) {
            return;
        }
        
        System.out.println("raj");
        
        // Recursive Call with incremented parameter
        printName(i + 1, n);
    }

    public static void main(String[] args) {
        int n = 3;
        printName(1, n); // Start from i = 1
    }
}

Step-by-Step Flow Walkthrough ($N = 3$)

1. main calls printName(1, 3).
   • 1 > 3 is false. Prints "raj".
   • Calls printName(2, 3).
2. printName(2, 3) executes.
   • 2 > 3 is false. Prints "raj".
   • Calls printName(3, 3).
3. printName(3, 3) executes.
   • 3 > 3 is false. Prints "raj".
   • Calls printName(4, 3).
4. printName(4, 3) executes.
   • 4 > 3 is true. Hits base case and executes return.
5. Control unwinds back through the stack frames, terminating the program. Total printed: 3 times.

4. Problem 2: Print Linearly from 1 to $N$

Building directly on the previous example, instead of printing a static name, we print the current value of the incrementing parameter i.

Code Implementation

public class Solution {
    public static void print1ToN(int i, int n) {
        if (i > n) {
            return;
        }
        
        System.out.println(i); // Print current value of i
        print1ToN(i + 1, n);   // Move forward
    }

    public static void main(String[] args) {
        int n = 4;
        print1ToN(1, n); // Output: 1, 2, 3, 4
    }
}

5. Problem 3: Print Linearly from $N$ to 1 (Descending Order)

To print numbers in decreasing order from $N$ down to 1, we change our trajectory: we start at $N$ and decrement towards 1.

Code Implementation

public class Solution {
    public static void printNTo1(int i, int n) {
        // Base Case: Stop when i drops below 1
        if (i < 1) {
            return;
        }
        
        System.out.println(i);
        printNTo1(i - 1, n); // Decrement towards 1
    }

    public static void main(String[] args) {
        int n = 4;
        printNTo1(n, n); // Start from i = 4, output: 4, 3, 2, 1
    }
}

6. What is Backtracking? (Printing 1 to $N$ Without i + 1)

What if we are given a strict constraint: Print from 1 to $N$, but you are NOT allowed to use i + 1 in your recursive call?

This constraint forces us to start our recursion from $N$ and decrement down to 1 (i - 1), while still managing to output the numbers in increasing order (1, 2, 3... $N$). This technique is known as Backtracking.

Real-Life Analogy: The Unwinding Stack and Post-Order Actions

Think of recursion like sending a group of people down a tunnel ($N$ down to 1) where nobody is allowed to speak on the way in. They must reach the deepest point, turn around, and deliver their message on their way back out. The last person to enter the tunnel reaches the end first, but the first person to speak is the one who emerges last—or conversely, by placing our print statement after the recursive call, the deepest call finishes first and prints the smallest number when unwinding.

Code Implementation (Using Backtracking)

public class Solution {
    public static void print1ToNBacktrack(int i, int n) {
        // Base Case
        if (i < 1) {
            return;
        }
        
        // 1. Recursive call FIRST (dive deep before doing work)
        print1ToNBacktrack(i - 1, n);
        
        // 2. Print AFTER the recursive call returns (on the way back up)
        System.out.println(i);
    }

    public static void main(String[] args) {
        int n = 3;
        print1ToNBacktrack(n, n); // Starts at f(3, 3)
    }
}

Complete Flow Walkthrough ($N = 3$)

1. main calls print1ToNBacktrack(3, 3).
2. f(3, 3) calls f(2, 3) (print statement is paused/suspended).
3. f(2, 3) calls f(1, 3) (print statement is paused).
4. f(1, 3) calls f(0, 3) (print statement is paused).
5. f(0, 3) hits base case (i < 1) and immediately returns without printing.
6. Control returns to f(1, 3):
   • Executes System.out.println(1). (Output: 1)
   • Returns to caller.
7. Control returns to f(2, 3):
   • Executes System.out.println(2). (Output: 2)
   • Returns to caller.
8. Control returns to f(3, 3):
   • Executes System.out.println(3). (Output: 3)
   • Returns to main. Program terminates.

Final Output: 1, 2, 3 (printed in ascending order despite starting our parameters at $N$).

7. Complexity Analysis

Note on Space Complexity: The auxiliary space complexity of $O(N)$ refers to the internal Call Stack memory allocated by the runtime environment to keep track of active function frames. No explicit arrays or data structures are used.

8. Summary and Key Takeaways

• Parameter-Based State: Always prefer passing state variables (like i and n) through function parameters rather than using global variables to ensure clean, maintainable code.
• Base Case Necessity: Every recursive function must have a clearly defined termination condition (if (i > n) or if (i < 1)) to prevent infinite recursion and stack overflow errors.
• Pre-Order vs. Post-Order Execution:
  • Placing logic before the recursive call executes actions on the way down into the stack.
  • Placing logic after the recursive call executes actions on the way up (unwinding) the stack.
• Backtracking Power: Backtracking allows us to reverse or manipulate output order by deferring execution until the deepest recursive branch has resolved.
• Linear Complexity: Standard linear recursion on a single variable $N$ yields both a Time Complexity and a Stack Space Complexity of $O(N)$.