Re 5. Multiple Recursion Calls | Problems | Strivers A2Z DSA Course

Understanding multiple recursion calls marks a foundational transition from linear single-branch recursion to branching decision trees. This chapter breaks down how multiple function calls execute sequentially on the call stack, how to visualize them using vertical recursion trees, and how to analyze their exponential time complexity.

1. Why Do We Need Multiple Recursion Calls?

• Limitation of Single Recursion: Up to this point, functions invoked only a single recursive instance per frame (unidirectional execution). Many computational problems, however, require evaluating multiple independent sub-problems simultaneously to construct a solution.
• Branching Logic: Problems such as finding Fibonacci numbers, generating permutations, solving the N-Queens puzzle, or exploring grid paths require a function to branch out and invoke itself two or more times within a single execution frame.
• The Core Pattern: Instead of a single return path, a function initiates multiple sub-tasks, waits for their respective resolutions, and then combines their outputs.

2. Core Mental Model: The Fibonacci Sequence

• Definition: The Fibonacci sequence is a classic mathematical series where each number is the sum of the two preceding ones:
  CODE

  Copy

  F(0) = 0
  F(1) = 1
  F(2) = F(1) + F(0) = 1 + 0 = 1
  F(3) = F(2) + F(1) = 1 + 1 = 2
  F(4) = F(3) + F(2) = 2 + 1 = 3
  F(5) = F(4) + F(3) = 3 + 2 = 5
  

• Recursive Relation: To compute the $N$-th Fibonacci number $F(N)$, we must know both $F(N-1)$ and $F(N-2)$:
  CODE

  Copy

  F(N) = F(N - 1) + F(N - 2)
  

• Base Cases: When $N \le 1$, the recursion terminates directly:
  • If $N = 0$, return 0.
  • If $N = 1$, return 1.

3. Naive Iterative Approach vs. Multiple Recursion

• Iterative Approach: Can be solved easily using a for loop by storing previous values in an array or variables.
  C++

  Copy

  int f(int n) {
      if (n <= 1) return n;
      int a = 0, b = 1, c;
      for (int i = 2; i <= n; i++) {
          c = a + b;
          a = b;
          b = c;
      }
      return b;
  }
  

• Recursive Approach: Rather than maintaining iterative state variables, we delegate the computation of previous terms to recursive function calls.
  C++

  Copy

  int fibonacci(int n) {
      if (n <= 1) {
          return n;
      }
      int last = fibonacci(n - 1);
      int secondLast = fibonacci(n - 2);
      return last + secondLast;
  }
  

4. Execution Order: Sequential Nature of Multiple Calls

• Crucial Rule: Multiple recursive calls do not execute simultaneously. They execute strictly sequentially (line by line).
• Call Stack Behavior:
  1. The first recursive call (fibonacci(n - 1)) is invoked. The current function pauses execution, and its state is pushed onto the call stack.
  2. The entire sub-tree for fibonacci(n - 1) runs to completion and returns its result.
  3. Only after the first call returns does the second recursive call (fibonacci(n - 2)) execute.
  4. Once both values are returned, they are added together and the final sum is returned.

5. Step-by-Step Execution Walkthrough for $N = 4$

Let's trace fibonacci(4) step by step:

6. Translating Horizontal Code to Vertical Recursion Trees

While code executes horizontally line-by-line, visualizing recursion as a vertical tree makes complex branching understandable.

                     f(4)
                    /    \
                 f(3)    f(2)
                /    \   /    \
             f(2)   f(1) f(1) f(0)
            /    \
         f(1)    f(0)

• Traversal Order: The left branch (f(3)) is fully evaluated down to its base cases before the right branch (f(2)) is touched.
• Redundant Computations: Notice how f(2) is computed multiple times in the tree above. This redundancy is the hallmark of naive multiple recursion.

7. Time Complexity Analysis

• Total Function Calls: For $N = 4$, the total number of calls is 9. For larger $N$, the number of calls grows rapidly.
• Exponential Growth ($O(2^N)$):
  • Each level of the recursion tree roughly doubles the number of calls compared to the previous level ($2 \times 2 \times 2 \dots$).
  • While it is not strictly $2^N$ due to uneven branch depths (e.g., $N-1$ vs $N-2$), the time complexity is exponential in nature ($O(2^N)$).
• Optimization Preview: This massive redundancy can be eliminated using Dynamic Programming (Memoization or Tabulation), which will be explored in upcoming chapters.

8. Summary and Key Takeaways

• Multiple Recursion: Occurs when a single function frame invokes itself two or more times, creating a branching execution model.
• Sequential Execution: Multiple calls within a function never run concurrently; the first call runs and returns completely before the second call initiates.
• Call Stack Pausing: The parent function pauses at the line of the first call, waiting in the stack frame until a return value is produced.
• Fibonacci Paradigm: Computing $F(N)$ requires splitting into $F(N-1)$ and $F(N-2)$, serving as the quintessential introductory problem for multiple recursion.
• Recursion Trees: Essential for visualizing execution flow, branch ordering, and function dependencies.
• Exponential Complexity: Naive multiple recursion often leads to $O(2^N)$ time complexity due to overlapping sub-problems.
• Future Optimization: Overlapping recursive calls pave the way for Dynamic Programming to cache results and drastically improve efficiency.