DSA Tracker

Visualize

Fibonacci Number

time O(n)space O(1)

The key insight: the Fibonacci sequence is defined recursively, but the recursive definition can be expensive due to repeated computation. A bottom-up iterative approach builds the sequence from the base cases F(0) = 0 and F(1) = 1, computing each subsequent value F(i) = F(i-1) + F(i-2) exactly once. After n steps, F(n) is available as the last computed value. This avoids the exponential blowup of the naive recursive approach while remaining conceptually simple.

Details

Animated on: Compute F(6) where F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n >= 2. Answer: 8.

Problem:Fibonacci NumberEasy

Recursion

step 1 / 11

0
[0]
1
[1]

Seed the iterative build with the base cases: a = F(0) = 0, b = F(1) = 1. These are the first two Fibonacci numbers.

  • a=0· arr[0] = 0
  • b=1· arr[1] = 1
Pseudocode
1FUNCTION fibonacci(n):
2  IF n == 0: RETURN 0
3  IF n == 1: RETURN 1
4  a = 0, b = 1
5  FOR i from 2 to n:
6    c = a + b
7    a = b
8    b = c
9  RETURN b

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. Seed the iterative build with the base cases: a = F(0) = 0, b = F(1) = 1. These are the first two Fibonacci numbers.
  2. i = 2: compute c = a + b = F(2) = F(0) + F(1) = 0 + 1 = 1. This is the next Fibonacci number.
  3. a = b = 1: shift the window forward; the new a becomes the old b (1), and b will soon hold F(2).
  4. c = a + b = 1 + 1 = 2. Compute F(3) = F(2) + F(1) = 1 + 1 = 2. Now b = 2.
  5. a = b = 2: shift the window forward; a becomes the old b (1 → now updated to 2), preparing for the next iteration.
  6. c = a + b = 1 + 2 = 3. Compute F(4) = F(3) + F(2) = 2 + 1 = 3. Now b = 3.
  7. a = b = 3: shift the window forward; a becomes the old b (2), preparing for F(5).
  8. c = a + b = 2 + 3 = 5. Compute F(5) = F(4) + F(3) = 3 + 2 = 5. Now b = 5.
  9. a = b = 5: shift the window forward; a becomes the old b (3), preparing for F(6).
  10. c = a + b = 3 + 5 = 8. Compute F(6) = F(5) + F(4) = 5 + 3 = 8. Now b = 8, which is the answer.
  11. Return b = 8. F(6) = 8, the answer for n = 6.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Fibonacci Number in the editorAll Recursion problemsBack to roadmap