Reference

Fibonacci Number Recursively

The classic recursive Fibonacci definition, and why it's inefficient for large n without memoization.

The Fibonacci sequence is defined as fib(0) = 0, fib(1) = 1, and fib(n) = fib(n-1) + fib(n-2) for n > 1. Each term is the sum of the previous two.

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

Although this illustrates recursion clearly, it is inefficient for large n because it recomputes values (this can later be improved with memoization).