Ciąg Fibonacciego to ciąg liczb, w którym pierwszy wyraz jest równy 0, drugi jest równy 1 a każdy następny jest sumą dwóch poprzednich. Można go przedstawić za pomocą następującego zapisu:
Jeżeli chcemy obliczyć wartość 4 wyrazu ciągu użyjemy wzoru:
F4 = F4-1 + F4-2 = F3 + F2
Wzór rekurencyjny nie dostarcza nam informacji o elemencie F3 i F2 więc musimy ponownie rozpisać te wyrazy posługując się wzorem na n:
F3 = F3−1 + F3−2 = F2 + F1
F2 = F2−1 + F2−2 = F1+F0 = 1 + 0 = 1
Już wiemy że, F2 wynosi 1. Dzięki temu możemy obliczyć wartość dla F3 i F4:
F3 = F2 + F1 = 1 + 1 = 2
F4 = F3 + F2 =2 + 1 = 3
Ostatecznie 3 wyraz ciągu (czyli wyraz z indeksem 4) Fibonacciego wynosi 3.
Ciąg Fibonacciego – metoda iteracyjna
p – poprzedni wyraz (na początku równy zerowemu wyrazowi)
w – obecny wyraz (na początku równy pierwszemu wyrazowi)
Pętla for i in range(n-1) wykona się n-1 razy, czyli np. dla n=2 wykona się 1 raz.
Można oczywiście taki ciąg zapisać też w innej formie . Poniższy algorytm przedstawia trochę inny sposób obliczania danego elementu ciągu:
Ciąg Fibonacciego – metoda rekurencyjna
Rekurencja, rekursja (z łac. recurrere, przybiec z powrotem) – odwoływanie się funkcji lub definicji do samej siebie.
Tą metodą algorytm napisany w języku Python może przyjąć następujący format:
