Fibonacciho číslo $F_n$ je určeno rekurencí následovně: $F_0=0$, $F_1=1$ a $F_n=F_{n-1}+F_{n-2}$ pro $n\geq 2$. Fibonacciho čísla jsou $0$, $1$, $1$, $2$, $3$, $5$, $8$, $\dots$ Pokud bychom naprogramovali funkci vracející $n$-té Fibonacciho číslo pomocí rekurze1, tak přepsáním do for-cyklu dosáhneme podstatného zrychlení, které je způsobeno odstraněním opakujících se výpočtů.

Fib($n$):
	 if $n > 1$ then
	 	 return(Fib$(n-1) + $     Fib$(n-2)$)
	 else
	 	 return $n$

Fib($n$):
	 $\ARRAY{F}{0} := 0$
	 $\ARRAY{F}{1} := 1$
	 for $i:=2$ to $n$  do
	 	 $\ARRAY{F}{i} := \ARRAY{F}{i-1} + \ARRAY{F}{i-2}$
	 return $\ARRAY{F}{n}$

Na následujícím obrázku je strom větvení rekurzivního řešení. Zkuste si podle něj počítat.2

Z obrázku vidíme, že jsme $F_5$ počítali jednou, $F_4$ také jednou, $F_3$ dvakrát, $F_2$ třikrát a $F_1$ pětkrát. Připomínají vám tyto čísla něco? Od toho pozorování už není daleko k tomu, abychom ukázali, že rekurzivní řešení má časovou složitost alespoň $\Omega(F_n)$. O Fibonacciho číslech je známo, že $F_n \approx \varphi^n$, kde $\varphi = \frac{1+\sqrt{5}}{2}$. Není těžké ukázat, že rekurzivní řešení má časovou složitost $\Theta(\varphi^n)$. O proti němu má nerekurzivní řešení jen lineální časovou složitost.3 Dosáli jsme tedy exponenciálního zrychlení. A světe div se, nejlepší řešení s časovou složitostí $\OO(\log n)$ je ještě exponenciálně krát rychlejší! (viz. cvičení).

Odstranění opakujících se výpočtů tím, že si je uložíme do tabulky, je jedna ze základních myšlenek dynamického programování (viz kapitola [ref]dynamic_programming[/ref]).