C++ Fibonacci Series Program: Loop, Recursion and Memoization

The Fibonacci series starts with 0, 1 and every next number is the sum of the two numbers before it: 0, 1, 1, 2, 3, 5, 8, 13...

1. Using a loop (the best way)

#include <iostream>

int main() {
    int count = 12;
    unsigned long long a = 0, b = 1;
    for (int i = 0; i < count; i++) {
        std::cout << a << ' ';
        unsigned long long next = a + b;
        a = b;
        b = next;
    }
    std::cout << '\n';
}

2. Using recursion

#include <iostream>

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

int main() {
    for (int i = 0; i < 12; i++) std::cout << fib(i) << ' ';
    std::cout << '\n';
}

Simple, but it repeats the same work again and again, so it is very slow for numbers like fib(45).

3. Recursion with memoization

#include <iostream>
#include <unordered_map>

unsigned long long fib(int n, std::unordered_map<int, unsigned long long>& cache) {
    if (n <= 1) return n;
    if (auto it = cache.find(n); it != cache.end()) return it->second;
    return cache[n] = fib(n - 1, cache) + fib(n - 2, cache);
}

int main() {
    std::unordered_map<int, unsigned long long> cache;
    std::cout << fib(10, cache) << '\n';
    std::cout << fib(50, cache) << '\n';
    std::cout << fib(90, cache) << '\n';
}

4. At compile time with constexpr

#include <array>
#include <iostream>

constexpr unsigned long long fib(int n) {
    unsigned long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        unsigned long long next = a + b;
        a = b;
        b = next;
    }
    return a;
}

int main() {
    constexpr auto table = [] {
        std::array<unsigned long long, 10> t{};
        for (int i = 0; i < 10; i++) t[i] = fib(i);
        return t;
    }();                                        // the table is built while compiling
    for (auto v : table) std::cout << v << ' ';
    std::cout << '\n';
}

Way	Speed	Note
Loop	Very fast	Simple, no extra memory
Plain recursion	Very slow for big n	Good only to learn recursion
Memoization	Fast	Uses memory for the cache
constexpr	No cost at run time	Values are known at compile time

Related: C++ Recursion.

• Next Code

---

Tutorials
No Content Found.

Exercises & Assignments
No Content Found.

Interview Questions & Answers
No Content Found.