AlgoViz
HomeRecursion

Fibonacci Number

Easy

Two branches, and why they explode

Problem

Return the Nth Fibonacci number, where F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2).

In simple words

Each number is the sum of the previous two; recursion just asks for those two smaller answers.

The idea

F(n) is F(n-1) + F(n-2) with F(0)=0 and F(1)=1. Written naively it recomputes the same values exponentially often, which makes it the standard illustration of why memoisation exists.

The trick

  • Plain recursion is O(2^n); memoising drops it to O(n).
  • Two base cases are needed because two branches are combined.
  • Iterating with two rolling variables is O(n) time and O(1) space.
fib(5)
calls1

Step 1 of 7. Brute force: fib(5) calls fib(4) and fib(3) — and each of those splits again. calls 1.

1/7
Brute force
timeO(2ⁿ)spaceO(n)

Exponential tree.

1function fib(n) {2  if (n <= 1) return n;3  return fib(n - 1) + fib(n - 2);   // recomputes everything4}

Input

nodes
1, 0 edges

Memory

calls
1
fib(1) redone
—
brute calls
—

Call stack

  1. 0visit(fib(5))

Output

with memo
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
n = 2
Output:
1
Explanation:
F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2

Input:
n = 5
Output:
5
Explanation:
0,1,1,2,3,5 → F(5) = 5.

Example 3

Input:
n = 9
Output:
34
Explanation:
The 9th Fibonacci number is 34.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.