Recursion Basics (Factorial, Fibonacci)

Recursion solves a problem by breaking it down into smaller instances of the same problem. A recursive function calls itself until it reaches a base case, at which point the recursion stops and results begin to return.

Factorial and Fibonacci are classic examples that clearly illustrate how recursion works and how the call stack behaves.

Anatomy of a Recursive Function

Every recursive function has two essential parts:

1. Base case - stops recursion
2. Recursive case - reduces the problem size

Without a base case, recursion leads to infinite calls and stack overflow.

Example 1: Factorial

Problem Definition

n! = n × (n − 1) × (n − 2) × ... × 1
0! = 1

Recursive Definition

factorial(n) = n × factorial(n - 1)
factorial(0) = 1

Rust Implementation

pub fn factorial(n: u64) -> u64 {
    if n == 0 {
        1
    } else {
        n * factorial(n - 1)
    }
}

Call Stack Visualization

Calling factorial(4):

factorial(4)
 └─ 4 * factorial(3)
     └─ 3 * factorial(2)
         └─ 2 * factorial(1)
             └─ 1 * factorial(0)
                 └─ 1

Stack unwinds bottom-up:

1 → 1 → 2 → 6 → 24

Time and Space Complexity

Example 2: Fibonacci

Problem Definition

fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)

Recursive Implementation (Naive)

pub fn fibonacci(n: u64) -> u64 {
    match n {
        0 => 0,
        1 => 1,
        _ => fibonacci(n - 1) + fibonacci(n - 2),
    }
}

Call Tree Visualization

Calling fibonacci(5):

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  │  ├─ fib(2)
│  │  │  ├─ fib(1)
│  │  │  └─ fib(0)
│  │  └─ fib(1)
│  └─ fib(2)
│     ├─ fib(1)
│     └─ fib(0)
└─ fib(3)
   ├─ fib(2)
   │  ├─ fib(1)
   │  └─ fib(0)
   └─ fib(1)

Why This Is Inefficient

The same subproblems are solved repeatedly:

fib(3), fib(2), fib(1) ...

This leads to exponential growth.

Time and Space Complexity

Iterative Comparison (Conceptual)

Fibonacci can also be computed iteratively in O(n) time and O(1) space, showing that recursion is not always the best choice.

This naturally leads to dynamic programming, which optimizes recursive solutions.

Common Recursion Pitfalls

• Missing base case
• Base case never reached
• Excessive recomputation
• Stack overflow for large inputs

Understanding these pitfalls is crucial before moving to backtracking and DP.

Summary

• Recursion reduces problems into smaller subproblems
• Base cases are mandatory
• Factorial shows linear recursion
• Fibonacci shows exponential recursion
• Naive recursion can be inefficient