Recursion Concept and Call Stack Visualization in DSA C

Mental Model

Recursion is when a function calls itself to solve smaller parts of a problem until it reaches a simple case it can solve directly.

Analogy: Imagine a set of Russian nesting dolls where each doll contains a smaller doll inside. You open each doll until you reach the smallest one, then close them back in reverse order.

function call stack:
main()
  ↓
func() -> func() -> func() -> base case
  ↑       ↑       ↑       ↑
  top     next    next    bottom

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion (factorial(3))

Goal: Show how recursive calls build up and then return results using the call stack

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

Stack: factorial(3) -> factorial(2)
Return unknown yet

Why: We break the problem into smaller part factorial(2)

Step 2: Call factorial(2), which calls factorial(1)

Stack: factorial(3) -> factorial(2) -> factorial(1)
Return unknown yet

Why: Keep breaking down until base case

Step 3: Call factorial(1), which calls factorial(0)

Stack: factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)
Return unknown yet

Why: Reach base case where factorial(0) = 1

Step 4: factorial(0) returns 1 (base case)

Stack unwinds: factorial(0) returns 1
Stack now: factorial(3) -> factorial(2) -> factorial(1)

Why: Base case solved, start returning values

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

Stack unwinds: factorial(1) returns 1
Stack now: factorial(3) -> factorial(2)

Why: Calculate factorial(1) using returned value

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

Stack unwinds: factorial(2) returns 2
Stack now: factorial(3)

Why: Calculate factorial(2) using returned value

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

Stack unwinds: factorial(3) returns 6
Stack empty

Why: Calculate factorial(3) using returned value, recursion ends

Result:

Final result: factorial(3) = 6

Annotated Code

DSA C

#include <stdio.h>

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

int main() {
    int number = 3;
    int result = factorial(number);
    printf("factorial(%d) = %d\n", number, result);
    return 0;
}

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

Check for base case to stop recursion

return n * factorial(n - 1);

Recursive call reduces problem size by 1

Output

factorial(3) = 6

Complexity Analysis

Time: O(n) because the function calls itself n times until reaching the base case

Space: O(n) because each recursive call adds a new layer to the call stack

vs Alternative: Iterative approach uses O(1) space but recursion is simpler to write and understand for problems like factorial

Edge Cases

Input is 0

Returns 1 immediately as base case

DSA C

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

Input is negative

No guard in code, leads to infinite recursion and stack overflow

DSA C

No explicit guard; user must ensure non-negative input

When to Use This Pattern

When a problem can be broken into smaller versions of itself and has a simple stopping point, use recursion to solve it cleanly.

Common Mistakes

Mistake: Forgetting the base case causing infinite recursion
Fix: Always include a base case that stops recursion

Mistake: Changing the input incorrectly causing wrong results
Fix: Ensure each recursive call moves closer to the base case by reducing input properly

Summary

Recursion solves problems by calling itself with smaller inputs until a simple base case is reached.

Use recursion when a problem naturally breaks down into smaller similar problems.

The key is the base case that stops the recursion and the call stack that remembers each step.