Ciąg Fibonacciego: wzór, tabela i kod w Pythonie

Ciąg Fibonacciego to ciąg liczb, w którym każdy wyraz jest sumą dwóch poprzednich: 0, 1, 1, 2, 3, 5, 8, 13 i tak dalej. To zarazem jeden z najlepszych przykładów na to, jak bardzo sposób zapisu algorytmu zmienia czas jego działania: w naszym pomiarze najprostsza rekurencja w Pythonie liczyła F(35) prawie sekundę, a zwykła pętla zrobiła to w mniej niż mikrosekundę. Ciąg opisał Leonardo z Pizy w 1202 roku, a jego związek ze złotą liczbą jest faktem matematycznym. Z obecnością w przyrodzie bywa różnie: w badaniu 657 słoneczników z 2016 roku w najpewniejszej części danych około trzech czwartych policzonych liczb spiral było liczbami Fibonacciego, ale badacze znaleźli też główki bez takiej struktury.

Ciąg Fibonacciego: definicja i wzór rekurencyjny

Ciąg definiuje się rekurencyjnie: dwa pierwsze wyrazy są ustalone, a każdy kolejny to suma dwóch poprzednich. Encyklopedia ciągów liczbowych OEIS zapisuje go jako A000045: F(n) = F(n−1) + F(n−2), przy czym F(0) = 0 i F(1) = 1.

W podręcznikach spotkasz dwie konwencje startu. Pierwsza, używana w OEIS i w większości kodu, zaczyna od F(0) = 0. Druga zaczyna od F(1) = 1 i F(2) = 1, bez zera. Obie dają te same liczby, różnią się tylko numeracją. Przed rozwiązaniem zadania sprawdź więc, od którego wyrazu liczy autor, bo “dziesiąty wyraz” to w jednej konwencji 34, a w drugiej 55.

Nazwa pochodzi od Leonarda z Pizy, zwanego Fibonaccim. Według biografii w archiwum MacTutor Uniwersytetu St Andrews ciąg pojawia się w jego “Liber abaci” z 1202 roku jako zadanie o królikach. Para królików w zamkniętym miejscu co miesiąc daje nową parę, a każda nowa para zaczyna się rozmnażać od drugiego miesiąca. Liczba par w kolejnych miesiącach to właśnie 1, 1, 2, 3, 5, 8, 13. Ta sama książka spopularyzowała w Europie cyfry indyjsko-arabskie.

Fibonacci nie był pierwszy. Donald Knuth, cytowany w OEIS, zwraca uwagę, że ciąg opisywali wcześniej uczeni indyjscy przy liczeniu rytmów złożonych z sylab krótkich i długich.

Tabela: pierwsze wyrazy ciągu Fibonacciego

Poniżej 21 wyrazów, od F(0) do F(20), w konwencji z zerem na początku. Wartości zgadzają się z plikiem danych OEIS i z wynikiem naszego kodu.

Liczby rosną szybko: F(30) = 832 040, F(50) przekracza 12 miliardów, a F(100) ma 21 cyfr. W językach ze stałym rozmiarem liczb całkowitych wynik szybko przestaje się mieścić w zmiennej, o czym niżej przy C++.

Frontend Master 2026 · Kodożercy

Wreszcie rozumiesz, dlaczego kod od AI raz działa, a raz nie

Frontend Master 2026 to pakiet sześciu kursów Kodożerców, który daje Ci język do prowadzenia kodu od AI: poprawiania, łączenia, rozszerzania i szybkiego znajdowania linijki, którą trzeba zmienić. Bez teorii dla samej teorii.

Wchodzę w to →

Ciąg Fibonacciego w Pythonie: trzy sposoby

Ten sam ciąg można policzyć w Pythonie rekurencją, pętlą albo rekurencją z pamięcią podręczną. Wszystkie trzy funkcje dają identyczne wyniki, co sprawdziliśmy dla n od 0 do 20. Różnią się czasem działania o kilka rzędów wielkości.

Rekurencja naiwna

Ta wersja przepisuje definicję matematyczną jeden do jednego i dlatego pojawia się w każdym podręczniku. Mechanizm rekurencji szerzej opisujemy w artykule o algorytmach rekurencyjnych.

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

print(fib_rek(10))  # 55

Problem widać, gdy rozpiszemy wywołania. Żeby policzyć F(5), funkcja liczy F(4) i F(3), a F(4) znowu liczy F(3). Ta sama wartość jest liczona wiele razy.

Liczba wywołań dla F(n) wynosi 2·F(n+1) − 1. Dla n = 35 to 29 860 703 wywołania funkcji, co policzyliśmy licznikiem w kodzie. Złożoność rośnie wykładniczo, mniej więcej jak 1,618 do potęgi n. Każdy kolejny wyraz kosztuje więc około 1,6 raza więcej czasu niż poprzedni.

Pętla

Pętla trzyma w pamięci tylko dwa ostatnie wyrazy i przesuwa je o krok w każdym obrocie. Złożoność czasowa to O(n), a pamięciowa O(1).

def fib_petla(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_petla(100))  # 354224848179261915075

Python przechowuje liczby całkowite z dowolną precyzją, ograniczoną w praktyce tylko pamięcią komputera, więc ta funkcja policzy także F(1000). Wynik ma 209 cyfr.

Rekurencja z pamięcią: functools.lru_cache

Dekorator lru_cache zapamiętuje wyniki funkcji dla argumentów, z którymi już była wywołana. Dokumentacja Pythona pokazuje go właśnie na przykładzie liczb Fibonacciego i nazywa to techniką programowania dynamicznego.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_cache(n):
    if n < 2:
        return n
    return fib_cache(n - 1) + fib_cache(n - 2)

print(fib_cache(35))  # 9227465

Każda wartość jest liczona raz, więc złożoność spada do O(n). Zostaje jednak głębokość rekurencji. Na naszym komputerze fib_cache(350) wywołany od zera kończył się błędem RecursionError. Dla dużych n bezpieczniejsza jest pętla.

Pomiar czasu: rekurencja kontra pętla

Czas zmierzyliśmy modułem timeit z biblioteki standardowej, biorąc najlepszy wynik z kilku przebiegów. Sprzęt: Intel Core i7-14700F, 64 GB RAM, Windows 11, Python 3.14.3. Pomiar z 10 października 2026 roku.

Różnica przy n = 35 to ponad milion razy. Na innym komputerze liczby wyjdą inne, ale proporcja zostanie podobna, bo wynika z liczby operacji, a nie ze sprzętu. Więcej o porównywaniu algorytmów przez złożoność piszemy w tekście o rodzajach algorytmów i ich złożoności.

Liczby Fibonacciego w C++

W C++ najprościej użyć pętli i typu std::uint64_t, czyli 64-bitowej liczby bez znaku. Listing skompilowaliśmy kompilatorem Microsoft C++ 19.29 z opcjami /std:c++17 /W4, bez ostrzeżeń.

#include <cstdint>
#include <iostream>

// F(n) dla n od 0 do 93; F(94) nie mieści się już w 64 bitach
std::uint64_t fib(unsigned n)
{
    std::uint64_t a = 0, b = 1;
    for (unsigned i = 0; i < n; ++i)
    {
        std::uint64_t next = a + b;
        a = b;
        b = next;
    }
    return a;
}

int main()
{
    for (unsigned n = 0; n <= 10; ++n)
        std::cout << fib(n) << ' ';
    std::cout << '\n' << "F(93) = " << fib(93) << '\n';
}

Program wypisuje 0 1 1 2 3 5 8 13 21 34 55 i F(93) = 12200160415121876738. To największy wyraz, który mieści się w 64 bitach. F(94) przekracza zakres typu i po cichu się przepełnia, bez żadnego komunikatu o błędzie. Jeśli zadanie wymaga większych wyrazów, potrzebna jest biblioteka dużych liczb albo język z takimi liczbami wbudowanymi, jak Python.

Wzór Bineta i złota liczba

Wzór Bineta pozwala policzyć n-ty wyraz ciągu bez liczenia poprzednich: F(n) = (φⁿ − ψⁿ) / √5. W tym wzorze φ = (1 + √5) / 2 ≈ 1,6180339887 to złota liczba, a ψ = (1 − √5) / 2. Ponieważ ψⁿ szybko maleje do zera, OEIS podaje też prostszą postać: F(n) to φⁿ / √5 zaokrąglone do najbliższej liczby całkowitej.

Iloraz dwóch sąsiednich wyrazów zbliża się do złotej liczby. 8 / 5 = 1,6, 13 / 8 = 1,625, 89 / 55 ≈ 1,61818, a 21. wyraz podzielony przez 20. daje już 1,61803. To matematyczny fakt i źródło skojarzenia ciągu ze złotym podziałem.

W kodzie wzór Bineta ma pułapkę. Liczby zmiennoprzecinkowe mają ograniczoną precyzję, więc round(phi**n / sqrt(5)) w Pythonie pierwszy raz pomylił się u nas dla n = 71, dając wynik większy o jeden. Do dokładnych obliczeń zostaje pętla na liczbach całkowitych.

Ciąg Fibonacciego w przyrodzie: co jest prawdą, a co mitem

Liczby Fibonacciego naprawdę pojawiają się w ułożeniu nasion i kwiatków w roślinach, ale nie zawsze, a wiele popularnych przykładów nie ma oparcia w pomiarach.

Najlepiej udokumentowany przykład to słonecznik. W 2016 roku czasopismo Royal Society Open Science opublikowało badanie J. Swintona, E. Ochu i zespołu MSI Turing’s Sunflower Consortium. Wolontariusze zebrali dane o 657 słonecznikach. W najpewniejszej części danych badacze ocenili 768 liczb spiral biegnących w lewo albo w prawo, a 565 z nich było liczbami Fibonacciego. Kolejne 67 miało strukturę bliską Fibonacciemu. Autorzy po raz pierwszy systematycznie opisali też główki zupełnie bez tej struktury. Wniosek praktyczny: Fibonacci w słoneczniku dominuje, ale nie jest prawem bez wyjątków.

Na zdjęciu wyróżniającym: dojrzałe koszyki słonecznika z pestkami ułożonymi w spirale biegnące w dwóch kierunkach. Fot. Kritzolina, Wikimedia Commons, licencja CC BY-SA 4.0.

Mitem jest za to muszla łodzika jako “złota spirala”. Clement Falbo w artykule z 2005 roku w College Mathematics Journal pokazał, że spirale muszli łodzika nie mają proporcji złotej liczby. W tym samym tekście zebrał szerzej twierdzenia o złotej liczbie w sztuce, architekturze i przyrodzie i stwierdził, że wiele z nich jest fałszywych, niepopartych danymi albo mylących. Przy kolejnym “Fibonaccim w naturze” warto więc zapytać, czy ktoś to zmierzył.

Gdzie programista spotyka liczby Fibonacciego

Najczęściej na rozmowie rekrutacyjnej i w nauce algorytmów, rzadziej w produkcyjnym kodzie. Ciąg jest standardowym zadaniem do pokazania rekurencji, zapamiętywania wyników i analizy złożoności, bo w kilku linijkach widać różnicę między wzrostem wykładniczym, około 1,618ⁿ, a liniowym O(n). Dobrze go też rozrysować, zanim napiszesz kod, na przykład jako schemat blokowy z pętlą.

W zespołach pracujących w Scrumie ciąg widać przy szacowaniu zadań metodą planning poker. Według Mountain Goat Software, firmy Mike’a Cohna, typowa talia ma wartości 0, 1, 2, 3, 5, 8, 13, 20, 40 i 100. Początek to liczby Fibonacciego, końcówka jest już zaokrąglona. Rosnące odstępy przypominają, że im większe zadanie, tym mniej dokładny szacunek.

W informatyce teoretycznej jest też kopiec Fibonacciego, struktura danych opisana w 1987 roku przez Michaela Fredmana i Roberta Tarjana w Journal of the ACM. Służy do przyspieszania algorytmów na grafach, takich jak wyszukiwanie najkrótszych ścieżek.

Najczęstsze pytania

Czy ciąg Fibonacciego zaczyna się od 0 czy od 1?

Obie wersje są poprawne. OEIS i większość kodu zaczyna od F(0) = 0, część podręczników od F(1) = F(2) = 1. Różni się tylko numeracja wyrazów, same liczby są takie same.

Ile wynosi F(100), czyli wyraz o numerze 100?

W konwencji z F(0) = 0 wyraz F(100) wynosi 354 224 848 179 261 915 075. Na liście liczonej od zera to 101. pozycja. W Pythonie policzysz go pętlą z tego artykułu, bo typ int ma dowolną precyzję. W C++ na typie 64-bitowym już się nie zmieści.

Jak policzyć liczby Fibonacciego w JavaScripcie?

Najprościej pętlą na typie BigInt, który obsługuje duże liczby całkowite. Zwykły typ Number traci dokładność powyżej 2⁵³, czyli już od F(79).

function fib(n) {
  let a = 0n, b = 1n;
  for (let i = 0; i < n; i++) {
    [a, b] = [b, a + b];
  }
  return a;
}

console.log(fib(100)); // 354224848179261915075n

Czy rekurencja zawsze jest wolniejsza od pętli?

Nie. Wolna jest rekurencja, która wielokrotnie liczy te same wartości. Rekurencja z zapamiętywaniem wyników ma tę samą złożoność co pętla, choć w Pythonie płaci się za nią limitem głębokości wywołań. Jeśli dopiero wybierasz pierwszy język, przyda się też porównanie Pythona i Javy.

Podsumowanie

Ciąg Fibonacciego to suma dwóch poprzednich wyrazów, liczona od F(0) = 0 i F(1) = 1, albo od dwóch jedynek w drugiej konwencji. W kodzie liczy się go najprościej pętlą, która ma złożoność O(n) i w Pythonie radzi sobie z wyrazami o setkach cyfr. Naiwna rekurencja nadaje się do nauki, ale już przy n = 35 wykonała u nas prawie 30 milionów wywołań i liczyła prawie sekundę. lru_cache usuwa powtórzenia, choć zostawia limit głębokości. W C++ typ 64-bitowy kończy się na F(93). Iloraz kolejnych wyrazów dąży do złotej liczby 1,618, co jest faktem matematycznym. W przyrodzie Fibonacci dominuje w słonecznikach, ale z wyjątkami, a muszla łodzika złotą spiralą nie jest.

Mateusz Wojdalski

Specjalista SEO i content marketingu w Devstock. Zajmuję się strategią treści, automatyzacją procesów marketingowych i wdrożeniami AI w codziennej pracy. Badam nowe narzędzia, adaptuję je do realnych zadań i piszę o tym, co faktycznie działa.