Fibonacci, naive
Naive Fibonacci computes the nth Fibonacci number by adding the two before it, each found the same recursive way, with 0 and 1 as base cases. Every call above the base cases makes two further calls, so the recursion forms a tree rather than the single chain factorial does.
When it is the right choice
There is no honest case for using this version: it recomputes fib(k) for every smaller k as many times as it is needed on the way to fib(n), which grows exponentially with n. It exists on this page to make that waste visible and countable — see it raced against the memoised version below, which keeps the identical logic but remembers what it has already worked out.
How it works
- Call fib with the given n.
- If n is 0 or 1, the base case is reached: hand back n itself.
- Otherwise, call fib on n − 1, then call fib on n − 2.
- Add the two answers together and hand the sum back.
Worth noticing
- fib(5) calls fib(4) and fib(3); fib(4) itself calls fib(3) and fib(2) — fib(3) is computed twice, and that duplication compounds at every level below it.
- The calls counter grows exponentially with n: fib(10) makes 177 calls, fib(16) makes 3,193. Watch it against memoised Fibonacci's counter on the same n to see the size of the waste directly.
- Its call tree is wide as well as deep, unlike factorial's single chain — the tree view earns its place on this page in a way the stack view alone could not show.
Cost
- Best
- O(2ⁿ)
- Average
- O(2ⁿ)
- Worst
- O(2ⁿ)
- Extra space
- O(n)
- Largest input
- n = 16
The largest input is a pedagogical ceiling rather than a technical one. This algorithm makes 2·F(n+1) calls, and past n = 16 the run stops being something a person can sit and watch — long before it reaches the step limit the tool enforces.