Factorial & Fibonacci

Factorial and Fibonacci are the classic examples for learning recursion. They demonstrate both the elegance and the pitfalls of recursive thinking.

Factorial

The factorial of n (written n!) is the product of all positive integers from 1 to n:

5! = 5 × 4 × 3 × 2 × 1 = 120
4! = 4 × 3 × 2 × 1 = 24
1! = 1
0! = 1 (by definition)

Recursive Definition

n! = n × (n-1)!     for n > 0
0! = 1              base case

Implementation

fn factorial(n: u64) -> u64 {
    // Base case
    if n == 0 {
        return 1;
    }

    // Recursive case
    n * factorial(n - 1)
}

fn main() {
    println!("{}", factorial(5)); // 120
}

Execution Trace

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1 * factorial(0)
= 5 * 4 * 3 * 2 * 1 * 1
= 120

Iterative Version

fn factorial_iterative(n: u64) -> u64 {
    let mut result = 1;
    for i in 2..=n {
        result *= i;
    }
    result
}

fn main() {
    println!("{}", factorial_iterative(5)); // 120
}

Complexity:

• Time: O(n) for both versions
• Space: O(n) recursive (call stack), O(1) iterative

Fibonacci Sequence

The Fibonacci sequence starts with 0 and 1, and each subsequent number is the sum of the two preceding ones:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n > 1

Naive Recursive Implementation

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

fn main() {
    println!("{}", fibonacci(10)); // 55
}

The Problem: Exponential Time

This simple solution is terribly inefficient:

                    fib(5)
                   /      \
               fib(4)      fib(3)
              /     \       /    \
          fib(3)  fib(2)  fib(2) fib(1)
          /   \    /   \   /   \
       fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
       /   \
    fib(1) fib(0)

We're calculating the same values repeatedly. fib(3) is calculated twice, fib(2) three times, and so on.

Time Complexity: O(2^n) - exponential! Space Complexity: O(n) - call stack depth

Memoization: Fixing the Inefficiency

Memoization stores results of previous calculations to avoid recomputation:

use std::collections::HashMap;

fn fibonacci_memo(n: u64, memo: &mut HashMap<u64, u64>) -> u64 {
    if let Some(&result) = memo.get(&n) {
        return result;
    }

    if n <= 1 {
        return n;
    }

    let result = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo);
    memo.insert(n, result);
    result
}

fn fibonacci_with_memo(n: u64) -> u64 {
    let mut memo = HashMap::new();
    fibonacci_memo(n, &mut memo)
}

fn main() {
    println!("{}", fibonacci_with_memo(50)); // 12586269025
}

With memoization:

• Time: O(n)
• Space: O(n)

With memo, each fib(k) is computed only once:

fib(5) → fib(4) → fib(3) → fib(2) → fib(1) → fib(0)
                      ↓         ↓
                  fib(2)*    fib(1)*
              (*already in memo)

Iterative (Tabulation) Approach

Build up from the base cases:

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

    let (mut prev2, mut prev1) = (0, 1);

    for _ in 2..=n {
        let current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    prev1
}

fn main() {
    println!("{}", fibonacci_iterative(50)); // 12586269025
}

Complexity:

• Time: O(n)
• Space: O(1) - just two variables!

This is often the best approach for Fibonacci.

Matrix Exponentiation: O(log n)

For very large n, use matrix exponentiation:

| F(n)   |   | 1 1 |^n   | 1 |
|        | = |     |   × |   |
| F(n-1) |   | 1 0 |     | 0 |

type Matrix = [[u64; 2]; 2];

fn matrix_mult(a: Matrix, b: Matrix) -> Matrix {
    [
        [
            a[0][0] * b[0][0] + a[0][1] * b[1][0],
            a[0][0] * b[0][1] + a[0][1] * b[1][1],
        ],
        [
            a[1][0] * b[0][0] + a[1][1] * b[1][0],
            a[1][0] * b[0][1] + a[1][1] * b[1][1],
        ],
    ]
}

fn matrix_power(m: Matrix, n: u64) -> Matrix {
    if n == 1 {
        return m;
    }

    if n % 2 == 0 {
        let half = matrix_power(m, n / 2);
        matrix_mult(half, half)
    } else {
        matrix_mult(m, matrix_power(m, n - 1))
    }
}

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

    let m = [[1, 1], [1, 0]];
    let result = matrix_power(m, n);
    result[0][1]
}

fn main() {
    println!("{}", fibonacci_matrix(50)); // 12586269025
}

Complexity:

• Time: O(log n)
• Space: O(log n) for recursion stack

Comparison of Approaches

| Approach | Time | Space | Notes | |----------|------|-------|-------| | Naive recursion | O(2^n) | O(n) | Too slow for n > 40 | | Memoization | O(n) | O(n) | Easy to implement | | Iterative | O(n) | O(1) | Best for most cases | | Matrix | O(log n) | O(log n) | For very large n |

Applications

Factorial Applications

• Counting permutations and combinations
• Probability calculations
• Taylor series expansions

Fibonacci Applications

• Growth patterns in nature (spirals, branching)
• Algorithm analysis (worst case for certain algorithms)
• Trading algorithms (Fibonacci retracements)
• Dynamic programming introduction

Practice: Variations

Sum of Factorials

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

fn sum_factorials(n: u64) -> u64 {
    // Calculate 1! + 2! + 3! + ... + n!
    if n == 0 {
        return 1;
    }
    factorial(n) + sum_factorials(n - 1)
}

fn main() {
    println!("{}", sum_factorials(5)); // 1 + 2 + 6 + 24 + 120 = 153
}

Tribonacci

Like Fibonacci, but summing three previous numbers:

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

    let (mut a, mut b, mut c) = (0, 1, 1);
    for _ in 3..=n {
        let next = a + b + c;
        a = b;
        b = c;
        c = next;
    }
    c
}

fn main() {
    println!("{}", tribonacci(10)); // 149
}

Generalized Fibonacci

fn fibonacci_mod(n: u64, modulo: u64) -> u64 {
    // Fibonacci with modular arithmetic
    if n <= 1 {
        return n;
    }

    let (mut prev2, mut prev1) = (0, 1);
    for _ in 2..=n {
        let current = (prev1 + prev2) % modulo;
        prev2 = prev1;
        prev1 = current;
    }
    prev1
}

fn main() {
    println!("{}", fibonacci_mod(100, 1000000007)); // Result modulo 1000000007
}

Key Takeaways

1. Factorial and Fibonacci are foundation problems for recursion
2. Naive Fibonacci has exponential time complexity—avoid it!
3. Memoization transforms exponential to linear time
4. Iterative solutions often use less space than recursive ones
5. The pattern of "overlapping subproblems" leads to dynamic programming
6. Choose the approach based on constraints (time, space, n size)

These classic problems teach patterns you'll use repeatedly: recognizing redundant computation, caching results, and converting recursive solutions to iterative ones. These skills are essential for dynamic programming.