Re 3. Parameterised and Functional Recursion | Strivers A2Z DSA Course

Main ideas / lessons

• The video teaches two recursive approaches to compute the sum of the first (n) numbers, i.e., (1+2+\dots+n):
  1. Parameterized recursion (use parameters to carry progress / accumulated state)
  2. Functional recursion (the function returns the computed result)
• It also uses factorial as an example to emphasize that the base case is crucial and must match the operation (addition vs. multiplication).
• It concludes with time and space complexity for the recursive patterns.

---

Methodology 1: Parameterized recursion (accumulate via parameters)

Concepts

• Instead of relying on the function call to build the answer, you carry partial progress through parameters.
• Typical parameters in this example:
  • i = current number being added
  • sum = accumulated sum so far

Instruction / structure (detailed)

• Define a helper recursive function, conceptually like:

  • f(i, sum)

• Base case:

  • If i < 1 (meaning i has moved past the beginning), then:
    • output sum
    • return to stop recursion

• Recursive step:

  • Call:
    • f(i - 1, sum + i)

• Main:

  • Read n
  • Initialize:
    • i = n
    • sum = 0
  • Call:
    • f(n, 0)

Example walk-through ((n = 3))

• Start: f(3, 0)
• Next: f(2, 0 + 3) → f(2, 3)
• Next: f(1, 3 + 2) → f(1, 5)
• Next: f(0, 5 + 1) → f(0, 6)
• Base case triggers when i < 1, so 6 is printed.

Key takeaway

• Design recursion that uses parameters to carry state and ends by outputting the final accumulated result.

---

Methodology 2: Functional recursion (return the answer)

Concepts

• The recursive function is designed to return the result (instead of printing).
• This pattern matches common DP/recursion thinking: “return computed value of the subproblem.”

Instruction / structure (detailed)

• Define f(n) as:

  • f(n) = sum of first n numbers

• Base case:

  • If n == 0, return 0

• Recursive step:

  • Return:
    • n + f(n - 1)

• Main:

  • Compute and print f(n)

Example walk-through ((n = 3))

• f(3) = 3 + f(2)
• f(2) = 2 + f(1)
• f(1) = 1 + f(0)
• f(0) = 0

Combine returns upward:

• f(1) = 1
• f(2) = 3
• f(3) = 6

Output is 6.

Key takeaway

• The answer is constructed via return values from smaller subproblems.

---

Important concept: Base case correctness (factorial example)

What the factorial illustrates

• Factorial uses multiplication: [ n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n ]

• Example values:

  • factorial(3) = 6
  • factorial(4) = 24

Base case error explained

• A common mistake shown:
  • Using return 0 for the base case in a multiplication recursion makes the entire product become 0.
• Contrast:
  • In a sum recursion, base case 0 works because 0 is the addition identity.
  • In a multiplication recursion, the correct base case is:
    • return 1, because 1 is the multiplicative identity.

Correct idea stated

• For factorial recursion, when n == 0, you must return 1 so products don’t collapse to 0.

---

Complexity discussion

• For the summation recursion, calls grow linearly:
  • Time complexity: (O(n))
  • Space complexity: (O(n)) due to the recursion stack (stack frames waiting for returns)

---

Speakers / sources featured

• Primary speaker: The host/instructor of “Strivers A2Z DSA Course” (who teaches the recursion patterns in the video).
• Source mentioned (sponsor): Code Studio (for interview preparation resources).