Factorial and Fibonacci Recursively

Two classic recursion examples. Factorial is a linear recursion — one call per level. Fibonacci is a tree recursion — it explodes exponentially. One is efficient, the other shows you why memoisation exists.

Factorial: Linear Recursion

n! = n × (n−1) × ... × 1. The recursive definition writes itself: n! = n × (n−1)!, with 0! = 1 as the base.

C++

long long fact(int n) {
    if (n <= 1) return 1;         // base: 0! = 1! = 1
    return n * fact(n - 1);        // recursive
}

Rust

fn fact(n: u64) -> u64 {
    if n <= 1 { return 1; }
    n * fact(n - 1)
}

💡 Linear = efficient

Factorial makes N recursive calls, does N multiplications — O(N) time, O(N) stack space. That's as good as the iterative version.

Fibonacci: Tree Recursion

fib(n) = fib(n−1) + fib(n−2) with fib(0) = 0, fib(1) = 1. The definition is simple, but the recursive call tree is not.

C++ — naive Fibonacci

int fib(int n) {
    if (n <= 1) return n;          // fib(0)=0, fib(1)=1
    return fib(n - 1) + fib(n - 2);
}

Rust — naive Fibonacci

fn fib(n: u64) -> u64 {
    if n <= 1 { return n; }
    fib(n - 1) + fib(n - 2)
}

📐 The explosion

Each call makes two more calls. The tree has depth N and roughly 2ᴺ nodes. fib(45) takes ~14 seconds on a modern CPU. fib(100) would take longer than the age of the universe. That's O(2ᴺ) — and it's why we need memoization (next chapter).

// Compare the growth:
// fib(10)  =    55   (177 calls)
// fib(20)  =  6,765  (21,891 calls)
// fib(30)  =  832,040 (2,692,537 calls)
// fib(45)  =  1,134,903,170 (~3.6 billion calls)

Key Takeaways

→ Factorial: linear recursion — O(N) time, O(N) space. Efficient as-is.
→ Fibonacci: tree recursion — O(2ᴺ) time. Impossibly slow for N > 45.
→ The problem: identical subproblems are recomputed over and over.
→ The fix: memoization — store results the first time, reuse later.