Algoritem për numrat Fibonaci

[al5f1nx]

Perl 1-liner

$a=0;$b=1;while($i<20){print $b.", ";$var1=$a;$a=$b;$b=$a+$var1;$i++;} 

[Dr Rieux]

Zbatimet me dy thirrje vetreferuese (recursive calls) te tipit f(n) = f(n) + f(n-1) jane shume kohe harxhuese per vlera te medha te n-se. Teknikisht thuhet se ky lloj zbatimi ka kompleksitet kohor eksponencial, gje shume e padeshirueshme ne programim. Mendoni psh f(5). Per f(5) duhet te gjejme f(4) dhe f(3). Per f(4) duhet f(3) dhe f(2). Pa i shkuar deri ne fund duket qe f(3) e kemi llogaritur dy here, njehere per f(4) dhe njehere per f(3) vete, kur njehere na del e na tepron. Zgjidhja eshte qe kete vlere te f(3) ta ruajme (psh ne nje array) per ta perdorur kur te na duhet heret e tjera.

Psh me kete lloj programimi i bie qe per te gjet f(10), f(5) llogaritet 8 here. Ne pergjithesi per te gjetur f(n), f(k) thirret f(n-k) here vlere kjo qe eshte rend eksponencial kundrejt n-se. Po sme besuat provoni te llogarisni psh f(50) me kete menyre, .

Se fundi sekuenca numrave Fibonaci ka formen e mbyllur:
f(n) = [a^n - (1-a)^n] / sqrt(5), ku a = (1+sqrt(5))/2 eshte raporti i arte per te cilen flitet tek Kodi i da Vincit, sqrt ~ rrenja kartore, ^ ~ ngritja ne fuqi.