Fibonacci Series

Why it shows up everywhere in practice: It’s the classic teaching vehicle for a few foundational concepts, which is why it appears so often in coursework and interviews.

A deceptively simple sequence that’s really a lesson in how you compute, not what you compute.

1. Iterative

#include <iostream>
#include <cstdint>

// Prints the first n Fibonacci numbers
void fibSeries(int n) {
    uint64_t a = 0, b = 1;
    for (int i = 0; i < n; ++i) {
        std::cout << a << " ";
        uint64_t next = a + b;
        a = b;
        b = next;
    }
    std::cout << "\n";
}

int main() {
    fibSeries(10);   // 0 1 1 2 3 5 8 13 21 34
    return 0;
}

O(n) time, O(1) space. This is what you'd want in an interview unless asked otherwise.

O(n) time, O(1) space. This is what you’d want in an interview unless asked otherwise.

2. Recursive

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

Clean to read, but O(2ⁿ) time because it recomputes the same subproblems over and over. Good for explaining recursion; bad for anything past n ≈ 40.

3. Memoized recursion

#include <vector>

uint64_t fib(int n, std::vector<uint64_t>& memo) {
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];  // already computed
    return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
}

Brings the recursive version down to O(n) time, O(n) space. This is the bridge between naive recursion and the iterative dynamic programming version — worth being able to write from memory since it’s the pattern for most dynamic programming problems.