fuel(6) = fuel(5) + fuel(4) - 3000
= fuel(4) + fuel(3) - 3000 + fuel(3) + fuel(2) - 3000
= fuel(3) + fuel(2) - 3000 + fuel(2) + fuel(1) - 3000 - 3000 + fuel(2) + fuel(1) - 3000 + fuel(1) + fuel(0) - 3000 - 3000
= ...
Ineffektiviteten ligger i att det görs onödigt många rekursiva anrop
för att beräkna funktionsvärden. För att beräkna fuel(6) får vi totalt
25 anrop av fuel(5), fuel(4), fuel(3), fuel(2), fuel(1) och fuel(0).
(jämför med Fibonacci-talen).
Det blir ju mycket enklare att börja med att beräkna fuel(0) och fuel(1), spara dom i en lista, sedan beräkna fuel(2) med hjälp av de sparade värdena och spara undan den, osv
Så här:
fuel(1) = 2990 fuel(2) = fuel(1) + fuel(0) - 3000= 2990 fuel(3) = fuel(2) + fuel(1) - 3000 = 2980 fuel(4) = fuel(3) + fuel(2) - 3000 = 2970 fuel(5) = fuel(4) + fuel(3) - 3000 = 2950 fuel(6) = fuel(5) + fuel(4) - 3000 = 2920