← Back to All Algorithms

🌀 Fibonacci: Recursion vs DP

The Classic Example

F(n) = F(n-1) + F(n-2), with F(0)=0, F(1)=1

Naive Recursion: O(2ⁿ) — exponential due to repeated work

DP (Tabulation): O(n) — each subproblem solved once

Compute F()

Click "Start" to compare approaches

DP Tabulation

Operations: 0

Naive Recursion

?

Function calls: 0