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

Main Ideas / Lessons Conveyed

• Goal of the lesson: Understand how multiple recursion calls work inside a single recursive function (e.g., a function that calls itself 2 times per invocation, and in general problems may call it 3 times, 4 times, etc.).
• Why Fibonacci is used: Fibonacci naturally demonstrates recursion where each value depends on two previous values.

Core Recursion Relation (Fibonacci)

[ F(0)=0,\quad F(1)=1,\quad \text{for } n>1:\; F(n)=F(n-1)+F(n-2) ]

How Multiple Recursive Calls Execute

• The recursive calls do not run simultaneously.

• They behave like a depth-first process using the call stack:

  1. One call is made.
  2. The program waits for that call to finish and returns.
  3. Only then the second call is made.
  4. Then the results are added and returned upward.

Recursion Call Stack / Execution Order (Example: F(4))

• F(4) calls F(3) and F(2) (the “last” and “second last”).
• F(3) further calls F(2) and F(1).
• F(2) calls F(1) and F(0).
• Base cases stop recursion when n <= 1.

• The function returns from the deepest base cases upward:

  • F(1)=1, F(0)=0
  • 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

Recursion Tree Interpretation

• The recursion tree is drawn vertically (levels deepen downward).
• Each node splits into two children because each F(n) makes two recursive calls.
• The execution order corresponds to which child call happens first in the function (the “first” call gets evaluated first).

Time Complexity Insight

• Since each call makes two further calls, the growth is exponential.
• Intuition: it’s “near” (2^n), commonly described as exponential time (often not exactly (2^n) in small examples due to structural overlap).

Optimization Mention (Brief)

• Dynamic Programming (DP) can trim down repeated work, but the video notes DP is coming later.

---

Detailed Instruction / Methodology (Recursion Pattern for Multiple Calls)

Fibonacci as the Template for “Multiple Recursion Calls”

• Define a recursive function f(n):

  • Base case:
    • If n <= 1, return n
      • returns 0 for n=0
      • returns 1 for n=1
  • Recursive step (two calls):
    • Compute:
      • last = f(n - 1)
      • secondLast = f(n - 2)
    • Return:
      • last + secondLast

Execution Behavior to Remember

When f(n) performs multiple recursive calls:

• It finishes the first recursive call completely (reach base case, then unwind)
• Then it performs the second recursive call
• Finally it combines both results

Example Walkthrough Rule (Used for f(4))

• Conceptually expand:
  • f(4) = f(3) + f(2)
• Then follow call stack depth-first:
  • fully evaluate f(3) (which evaluates f(2) and f(1))
  • fully evaluate f(2) (which evaluates f(1) and f(0))
• Combine returned values:
  • f(1)=1, f(0)=0
  • f(2)=1+0=1
  • f(3)=f(2)+f(1)=1+1=2
  • f(4)=f(3)+f(2)=2+1=3

---

Speakers / Sources Featured

• Single speaker: The YouTube channel host/instructor (no specific name provided in the subtitles)
• Content/source: “Strivers A2Z DSA Course” (as stated in the video title)