Re 3. Parameterized and Functional Recursion | Striver's A2Z DSA Course

This chapter explores two foundational recursion patterns—Parameterized Recursion and Functional Recursion—by solving the classic problem of calculating the summation of the first $n$ numbers. Mastering these two patterns establishes the mental models required for advanced algorithmic paradigms, including dynamic programming, backtracking, and divide-and-conquer strategies.

1. Why Do We Need Different Recursion Patterns?

While simple iterative loops (like for or while loops) can easily compute mathematical sequences, mastering recursion is crucial because many complex problems (trees, graphs, and dynamic programming) cannot be solved with a simple linear loop.

When designing recursive functions, developers typically choose between two main structural patterns based on what the function needs to do:

• Parameterized Recursion: The function carries an ongoing state (like a running accumulator) as parameters through each recursive call and eventually prints or outputs the result when a base case is hit.
• Functional Recursion: The function relies on the return value of sub-problems, breaking a large problem into smaller sub-problems, combining their results, and passing the final computed value back up the call stack.

2. Problem Statement: Sum of First $N$ Numbers

Given an integer $n$, compute the sum of all integers from $1$ up to $n$.

• Example: If $n = 3$, the summation is $1 + 2 + 3 = 6$.
• Goal: Implement this using recursion rather than an iterative loop to build a robust mental model for base cases and recursive state transitions.

3. Pattern 1: The Parameterized Approach

In a parameterized recursion pattern, the recursive function accepts extra parameters (such as a running sum) to carry state forward as it traverses deeper into the recursion tree.

Conceptual Walkthrough

Assume we write a function f(i, sum) where:

• i represents the current number being processed (counting down from $n$ to $1$).
• sum accumulates the running total.

As we make recursive calls, we decrement i by 1 and add the current value of i to sum. When i drops below $1$, our base case is reached, and we print the accumulated result.

Code Implementation (Parameterized)

#include <iostream>
using namespace std::;

void solve(int i, int sum) {
    // Base Case: When i drops below 1, print the final accumulated sum and return
    if (i < 1) {
        cout << "Sum is: " << sum << endl;
        return;
    }
    
    // Recursive Step: Decrease i, and add i to the running sum parameter
    solve(i - 1, sum + i);
}

int main() {
    int n = 3;
    solve(n, 0); // Initial call with n = 3 and initial sum = 0
    return 0;
}

4. Execution Flow & Recursion Tree (Parameterized)

Let's trace what happens when n = 3 is passed into solve(3, 0):

As each function hits the base case, it terminates and unwinds back up the call stack without performing any additional arithmetic operations because the work was already done on the way down.

5. Pattern 2: The Functional Approach

Unlike parameterized recursion, a functional recursive function does not carry an accumulator. Instead, it expects the function itself to return a value computed from sub-problems.

Real-Life Analogy: The Restaurant Tab

Analogy: Imagine asking three people in a line to calculate a running total. Person 3 says: "I don't know the whole total, but give me Person 2's total and I will add my number ($3$) to it." Person 2 says the exact same thing to Person 1: "Give me Person 1's total and I'll add $2$." Finally, Person 0 (the base case) replies with $0$. The values then cascade back up, each person adding their own share to build the final bill.

Mathematical Breakdown

We break $f(n)$ down into smaller sub-problems:

• $f(3) = 3 + f(2)$
• $f(2) = 2 + f(1)$
• $f(1) = 1 + f(0)$
• $f(0) = 0$ (Base Case)

Code Implementation (Functional)

#include <iostream>
using namespace std;

int functionalSum(int n) {
    // Base Case: Sum of first 0 numbers is 0
    if (n == 0) {
        return 0;
    }
    
    // Recursive Step: Return n plus the result of the sub-problem for n - 1
    return n + functionalSum(n - 1);
}

int main() {
    int n = 3;
    int result = functionalSum(n);
    cout << "Sum is: " << result << endl; // Output: 6
    return 0;
}

6. Step-by-Step Call Stack Walkthrough (Functional)

When executing functionalSum(3), the system execution pauses each function call while it waits for the result of the subsequent recursive call:

Final output printed to screen: 6. Functional recursion is essential when learning advanced patterns like Dynamic Progression, where sub-problem results must be returned, stored, and reused.

7. Extending the Functional Pattern: Factorial of $N$

To solidify the functional pattern, let's solve a slightly different problem: calculating the Factorial of $N$ ($n!$).

• Definition: $n! = 1 \times 2 \times 3 \times \dots \times n$.
• Example: If $n = 3$, $3! = 1 \times 2 \times 3 = 6$. If $n = 4$, $4! = 24$.

The Pitfall: Choosing the Wrong Base Case

A common bug when shifting from summation to multiplication is keeping return 0 as the base case:

// INCORRECT BASE CASE FOR FACTORIAL
int factorial(int n) {
    if (n == 0) return 0; // BUG! 
    return n * factorial(n - 1);
}

If n == 0 returns 0, the entire product collapses:

• $1 \times 0 = 0$
• $2 \times 0 = 0$
• $3 \times 0 = 0$

Correct Implementation (Factorial)

For multiplication, the base case for $0!$ (or $1!$) must return 1 so that it acts as a neutral multiplicative identity:

#include <iostream>
using namespace std;

int factorial(int n) {
    // Base Case: 0! is 1 (multiplicative identity)
    if (n == 0) {
        return 1;
    }
    
    // Recursive Step: n multiplied by factorial of n - 1
    return n * factorial(n - 1);
}

int main() {
    int n = 3;
    cout << "Factorial is: " << factorial(n) << endl; // Output: 6
    return 0;
}

8. Complexity Analysis

9. Summary and Key Takeaways

• Parameterized vs. Functional: Parameterized recursion passes state down via parameters and outputs at the base case; functional recursion returns values up through the call stack to combine sub-problems.
• Role of Functional Recursion: Functional patterns are the stepping stone to Dynamic Programming, where returned values are cached and reused.
• Base Case Vigilance: Always verify base cases based on the mathematical operation. Summation base cases often return 0 (additive identity), whereas multiplication base cases must return 1 (multiplicative identity).
• Stack Memory Awareness: Every recursive call occupies memory on the call stack until a base case terminates it, resulting in $O(n)$ auxiliary space complexity for linear recursion.
• Pattern Recognition: Mastering structural patterns allows you to reliably translate mathematical definitions directly into clean recursive code without getting lost in execution flow.