Recursion vs Iteration When Each Wins in DSA C - Trade-offs & Analysis

Mental Model

Recursion solves problems by breaking them into smaller copies of itself, while iteration repeats steps using loops. Each works best depending on problem size and clarity.

Analogy: Imagine climbing stairs: recursion is like asking a friend to climb one step and then call another friend to climb the next, passing the task down until the top; iteration is like climbing step by step yourself in a loop.

Recursion stack:
main -> func(3) -> func(2) -> func(1) -> base case

Iteration loop:
start -> step 1 -> step 2 -> step 3 -> end

Dry Run Walkthrough

Input: Calculate factorial of 4 using recursion and iteration

Goal: Show how recursion and iteration compute factorial and when each is clearer or efficient

Step 1: Recursion calls factorial(4), which calls factorial(3)

Stack: factorial(4) -> factorial(3) ↑

Why: Break problem into smaller factorial(3)

Step 2: Recursion calls factorial(3), which calls factorial(2)

Stack: factorial(4) -> factorial(3) -> factorial(2) ↑

Why: Keep breaking down until base case

Step 3: Recursion calls factorial(2), which calls factorial(1)

Stack: factorial(4) -> factorial(3) -> factorial(2) -> factorial(1) ↑

Why: Reach smallest problem

Step 4: Recursion hits base case factorial(1) = 1, returns 1

Stack unwinding: factorial(1) returns 1

Why: Base case stops recursion

Step 5: factorial(2) returns 2 * 1 = 2

Stack unwinding: factorial(2) returns 2

Why: Combine results going back up

Step 6: factorial(3) returns 3 * 2 = 6

Stack unwinding: factorial(3) returns 6

Why: Combine results going back up

Step 7: factorial(4) returns 4 * 6 = 24

Stack unwinding: factorial(4) returns 24

Why: Final result computed

Step 8: Iteration starts with result=1, i=1

result=1, i=1

Why: Initialize iteration

Step 9: Multiply result by i=1 -> result=1, increment i=2

result=1, i=2

Why: First step of loop

Step 10: Multiply result by i=2 -> result=2, increment i=3

result=2, i=3

Why: Second step of loop

Step 11: Multiply result by i=3 -> result=6, increment i=4

result=6, i=4

Why: Third step of loop

Step 12: Multiply result by i=4 -> result=24, increment i=5

result=24, i=5

Why: Final multiplication

Step 13: Loop ends as i > 4, return result=24

result=24

Why: Iteration complete

Result:

Recursion stack unwound: factorial(4) = 24
Iteration result: 24

Annotated Code

DSA C

#include <stdio.h>

// Recursive factorial function
int factorial_recursive(int n) {
    if (n <= 1) {
        return 1; // base case
    }
    return n * factorial_recursive(n - 1); // recursive call
}

// Iterative factorial function
int factorial_iterative(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i; // multiply result by current i
    }
    return result;
}

int main() {
    int num = 4;
    int rec_result = factorial_recursive(num);
    int iter_result = factorial_iterative(num);
    printf("Recursion factorial(%d) = %d\n", num, rec_result);
    printf("Iteration factorial(%d) = %d\n", num, iter_result);
    return 0;
}

if (n <= 1) { return 1; }

stop recursion at base case to avoid infinite calls

return n * factorial_recursive(n - 1);

recursive call reduces problem size by 1

for (int i = 1; i <= n; i++) { result *= i; }

loop multiplies result by each number from 1 to n

Output

Recursion factorial(4) = 24

Iteration factorial(4) = 24

Complexity Analysis

Time: O(n) because both recursion and iteration multiply n numbers once

Space: O(n) for recursion due to call stack, O(1) for iteration using fixed variables

vs Alternative: Iteration uses less memory and is faster for large n; recursion is clearer for problems naturally defined by self-calls

Edge Cases

n = 0

Both return 1 as factorial of 0 is 1

DSA C

if (n <= 1) { return 1; }

n = 1

Both return 1 immediately

DSA C

if (n <= 1) { return 1; }

large n (e.g., 10000)

Recursion may cause stack overflow; iteration handles it safely

DSA C

for (int i = 1; i <= n; i++) { result *= i; }

When to Use This Pattern

When a problem naturally breaks into smaller subproblems, recursion is a good fit; when performance and memory are critical, iteration is preferred.

Common Mistakes

Mistake: Missing base case in recursion causing infinite calls
Fix: Add a clear base case like if (n <= 1) return 1;

Mistake: Using recursion for very large inputs causing stack overflow
Fix: Use iteration or tail recursion optimization if supported

Summary

Recursion solves problems by calling itself with smaller inputs; iteration uses loops to repeat steps.

Use recursion when problem is naturally recursive and input size is small; use iteration for large inputs or when memory is limited.

The key insight is recursion uses the call stack to remember work, while iteration uses fixed memory and loops.