Three Ways to Compute Fibonacci

Compare recursive, iterative, and tail-recursive C++ implementations. Move the slider, switch methods, and animate the execution.

Choose n

n 6

F(n) 8

Recursive execution tree

The same Fibonacci values are recomputed many times.

Same recurrence, different execution

Recursive

fib(n)
↙ fib(n−1)
↘ fib(n−2)

Each call creates two smaller subproblems.

Iterative

(a,b)
→ (b,a+b)
→ (b,a+b)

Only the previous two Fibonacci values are needed.

Tail Recursive

helper(n,a,b)
→ helper(n−1,b,a+b)

The recursive call carries exactly the state used by the loop.

C++ implementations

// 1. Recursive
int fib_recursive(int n) {
    if (n <= 1) return n;
    return fib_recursive(n - 1) + fib_recursive(n - 2);
}

// 2. Iterative
int fib_iterative(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

// 3. Tail Recursive
int fib_tail_helper(int n, int a, int b) {
    if (n == 0) return a;
    return fib_tail_helper(n - 1, b, a + b);
}

int fib_tail_recursive(int n) {
    return fib_tail_helper(n, 0, 1);
}