Factorial Using Recursion in DSA C

Mental Model

A function calls itself with a smaller number until it reaches 1, then multiplies all those numbers back up.

Analogy: Imagine stacking blocks from 1 up to n by first asking how many blocks are below, then adding the current one on top.

factorial(n)
  ↓
factorial(n-1)
  ↓
factorial(n-2)
  ↓
...
  ↓
factorial(1) = 1
  ↑
return multiply back up

Dry Run Walkthrough

Input: Calculate factorial of 4 using recursion

Goal: Find 4! = 4 x 3 x 2 x 1 = 24 by recursive calls

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

factorial(4) -> factorial(3) -> ?

Why: We reduce the problem to a smaller number to reach the base case

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

factorial(4) -> factorial(3) -> factorial(2) -> ?

Why: Keep breaking down until we reach factorial(1)

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

factorial(4) -> factorial(3) -> factorial(2) -> factorial(1)

Why: Base case factorial(1) returns 1

Step 4: factorial(1) returns 1

factorial(1) = 1

Why: Base case reached, start returning values

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

factorial(2) = 2

Why: Multiply current number by result of smaller factorial

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

factorial(3) = 6

Why: Continue multiplying back up

Step 7: factorial(4) returns 4 x factorial(3) = 4 x 6 = 24

factorial(4) = 24

Why: Final result is the factorial of 4

Result:

factorial(4) = 24

Annotated Code

DSA C

#include <stdio.h>

// Recursive function to calculate factorial
int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1; // base case: factorial of 0 or 1 is 1
    }
    return n * factorial(n - 1); // recursive call multiplying current n
}

int main() {
    int num = 4;
    int result = factorial(num);
    printf("Factorial of %d is %d\n", num, result);
    return 0;
}

if (n == 0 || n == 1) {

check for base case to stop recursion

return 1; // base case: factorial of 0 or 1 is 1

return 1 when base case reached

return n * factorial(n - 1);

recursive call multiplying current number by factorial of smaller number

Output

Factorial of 4 is 24

Complexity Analysis

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

Space: O(n) due to the call stack holding n recursive calls

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

Edge Cases

Input is 1

Returns 1 immediately as base case

DSA C

if (n == 0 || n == 1) {

Input is 0

Returns 1 immediately as base case

DSA C

if (n == 0 || n == 1) {

When to Use This Pattern

When you see a problem asking for repeated multiplication down to 1, use recursion to break it into smaller factorial calls.

Common Mistakes

Mistake: Missing base case causes infinite recursion
Fix: Add if (n == 0 || n == 1) return 1; to stop recursion

Summary

Calculates factorial by calling itself with smaller numbers until reaching 1.

Use recursion when a problem can be broken down into smaller identical problems.

The key is the base case that stops the recursion and starts returning results.