Ciąg Fibonacciego

Ciąg Fibonacciego to jeden z najsłynniejszych ciągów w matematyce. Zasada jest bardzo prosta: każda kolejna liczba w ciągu jest sumą dwóch poprzednich.

Początkowe wartości ciągu to: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

Na maturze często trzeba napisać algorytm wyliczający $n$-ty wyraz ciągu. Można to zrobić na dwa sposoby: iteracyjnie (pętlą) oraz rekurencyjnie (funkcją wywołującą samą siebie).

Rozwiązanie iteracyjne (Zalecane!)

Rozwiązanie za pomocą pętli jest błyskawiczne ($O(n)$) i to właśnie z niego powinieneś korzystać na egzaminie. Wystarczy zapamiętać dwie poprzednie wartości i w pętli przesuwać je do przodu.

Python

def fib_iter(n):
    # Wyrazy bazowe
    if n == 0: return 0
    if n == 1: return 1
    
    # Dwie zmienne przechowujące wartości (n-1) i (n-2)
    a = 0
    b = 1
    
    for _ in range(2, n + 1):
        # Nowy wyraz to suma dwóch poprzednich
        nowy = a + b
        
        # Przesuwamy nasze zmienne okienko o jeden krok w prawo
        a = b
        b = nowy
        
    return b

print(fib_iter(10)) # Zwróci 55

C++

#include <iostream>
using namespace std;

long long fibIter(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    // Używamy long long, bo liczby Fibonacciego rosną w kosmicznym tempie
    long long a = 0;
    long long b = 1;
    long long nowy;
    
    for (int i = 2; i <= n; i++) {
        nowy = a + b;
        a = b;
        b = nowy;
    }
    return b;
}

int main() {
    cout << fibIter(10) << endl; // 55
    return 0;
}

Rozwiązanie Rekurencyjne (Pułapka!)

Definicja matematyczna ciągu to $F_n = F_{n-1} + F_{n-2}$. Kuszące jest przepisanie tego bezpośrednio jako funkcji rekurencyjnej.

def fib_rek(n):
    if n == 0: return 0
    if n == 1: return 1
    return fib_rek(n - 1) + fib_rek(n - 2)

Złota zasada: Nigdy nie używaj czystej rekurencji do ciągu Fibonacciego! Dlaczego? Gdy liczymy fib_rek(5), program najpierw liczy fib_rek(4) i fib_rek(3). Aby policzyć fib_rek(4), znów liczy zawiłe fib_rek(3) oraz fib_rek(2).

Dla dużych $n$ (np. $n=40$) program liczy ten sam wyraz miliony razy, co zamraża komputer! Złożoność takiego kodu jest wykładnicza $O(2^n)$.

[!IMPORTANT] Dla dociekliwych: Programowanie dynamiczne (Memoizacja) Jeśli bardzo chcesz użyć rekurencji (np. jest to wymóg polecenia na maturze), musisz dodać do niej tzw. memoizację. Polega ona na tym, że po pierwszym obliczeniu $n$-tego wyrazu ciągu, zapisujemy wynik do słownika/tablicy. Jeśli funkcja znowu o niego poprosi, zwracamy gotowy wynik bez wchodzenia w rekurencję! Przekształca to dramatyczny czas $O(2^n)$ w superszybkie $O(n)$. W Pythonie można to osiągnąć dodając przed funkcją specjalną linijkę dekoratora @cache z modułu functools.