Ciąg Fibonacciego Python
Język Programowania

Ciąg Fibonacciego Python w praktyce – rekurencja, iteracja i analiza złożoności algorytmu

2026-04-21 /

Liczby Fibonacciego są jednym z najczęściej używanych przykładów podczas nauki algorytmiki, ponieważ na prostym schemacie pokazują kilka ważnych rzeczy naraz: zależność rekurencyjną, koszt obliczeń, pamięć programu i różnicę między rozwiązaniem eleganckim a rozwiązaniem praktycznym. Ten temat wraca zarówno na studiach, jak i podczas rozmów technicznych, bo dobrze ujawnia sposób myślenia programisty. Dobrym punktem wejścia do takich ćwiczeń jest Ciąg Fibonacciego Python.

Dlaczego Ciąg Fibonacciego Python dobrze pokazuje różnicę między rekurencją a iteracją

Ciąg Fibonacciego definiuje się bardzo prosto. Dwa pierwsze wyrazy to najczęściej:

  • F(0) = 0
  • F(1) = 1

Każdy kolejny wyraz jest sumą dwóch poprzednich:

  • F(n) = F(n – 1) + F(n – 2)

Powstaje więc sekwencja:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34…

To wygląda niewinnie, ale właśnie tutaj dobrze widać różnicę między zapisem matematycznym a rzeczywistym wykonaniem programu. Matematycznie definicja rekurencyjna jest naturalna. Programistycznie może być bardzo kosztowna.

Najczęstszy błąd początkujących polega na założeniu, że skoro zapis rekurencyjny jest krótki i „ładny”, to będzie też najlepszy wydajnościowo. W praktyce zwykle jest odwrotnie.

Wzór matematyczny i podstawowe zależności

ElementZapis
Definicja początkowaF(0) = 0
Definicja początkowaF(1) = 1
Zależność rekurencyjnaF(n) = F(n – 1) + F(n – 2)
PrzykładF(5) = F(4) + F(3) = 3 + 2 = 5

Najprostsza implementacja rekurencyjna w Python

JęzykKod
Pythondef fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)

Kod jest krótki i dobrze oddaje definicję matematyczną. Problem pojawia się przy większych wartościach.

Dla fib(40) program wykonuje ogromną liczbę powtórzonych obliczeń. fib(30) jest liczone wielokrotnie, podobnie fib(29), fib(28) i tak dalej. Proces zaczyna przypominać lawinę.

Wersja iteracyjna znacznie bliższa praktyce

JęzykKod
Pythondef fib_iter(n):
a = 0
b = 1
for i in range(n):
a, b = b, a + b
return a

Tutaj nie ma powtórnych obliczeń. Program przechodzi po kolejnych wartościach raz i kończy działanie w czasie liniowym.

To jest wersja, którą realnie stosuje się częściej.

Jak Ciąg Fibonacciego Python ujawnia koszt czasowy i problem nadmiarowych obliczeń

Analiza złożoności to moment, w którym ten przykład przestaje być tylko ćwiczeniem akademickim.

Rekurencja bez pamięci podręcznej ma złożoność wykładniczą, w przybliżeniu:

O(2^n)

To oznacza bardzo szybki wzrost czasu wykonania. Różnica między n = 20 a n = 40 nie jest „dwa razy większa”, tylko wielokrotnie większa.

Wersja iteracyjna działa w:

O(n)

i zużywa stałą ilość pamięci.

To ogromna różnica.

Porównanie podejść

MetodaZłożoność czasowaZłożoność pamięciowaPraktyczne użycie
Rekurencja naiwnaO(2^n)O(n)głównie nauka
IteracjaO(n)O(1)bardzo praktyczne
Rekurencja z memoizacjąO(n)O(n)dobra równowaga

Memoizacja jako rozwiązanie pośrednie

Memoizacja polega na zapamiętywaniu wcześniej obliczonych wyników. Dzięki temu rekurencja nie liczy tych samych wartości wiele razy.

JęzykKod
Pythonmemo = {}

def fib_memo(n):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
return memo[n]

To rozwiązanie jest często wybierane na zajęciach z dynamic programming, bo dobrze pokazuje ideę pamięci podręcznej.

Ten sam problem w C

JęzykKod
C#include <stdio.h>

int fib(int n)
{
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}

int main()
{
printf("%d\n", fib(10));
return 0;
}

W C problem wydajności jest dokładnie taki sam. Język nie rozwiązuje złej strategii algorytmicznej.

Wersja iteracyjna w C++

JęzykKod
C++#include <iostream>
using namespace std;

int fib(int n)
{
int a = 0;
int b = 1;
for (int i = 0; i < n; i++)
{
int temp = a;
a = b;
b = temp + b;
}
return a;
}

Tu dobrze widać proceduralny, przewidywalny przebieg programu bez kosztownego rozgałęziania.

Zastosowania poza zadaniami akademickimi i zależność z programowaniem dynamicznym

Sam ciąg rzadko jest celem biznesowym projektu. Nie buduje się systemu płatności tylko po to, żeby liczyć Fibonacciego. Ważne jest jednak to, czego ten przykład uczy.

Najważniejsza lekcja to rozpoznawanie problemów z nakładającymi się podproblemami.

Jeżeli algorytm wielokrotnie liczy te same fragmenty pracy, warto sprawdzić:

  • czy można użyć memoizacji
  • czy da się przejść na bottom-up
  • czy iteracja będzie prostsza i szybsza

To jest dokładnie fundament programowania dynamicznego.

Podobny mechanizm pojawia się w:

  • obliczaniu najkrótszych ścieżek
  • problemie plecakowym
  • obliczaniu odległości Levenshteina
  • analizie sekwencji DNA
  • optymalizacji kosztów i harmonogramów

Student zwykle widzi tylko „kolejny przykład z Fibonaccim”, ale później ten sam schemat wraca w systemach produkcyjnych.

Praktyczne zastosowania i testowanie kodu na przykładzie Ciąg Fibonacciego Python

Samo napisanie funkcji to za mało. Trzeba jeszcze sprawdzić poprawność.

Typowe błędy:

  • złe warunki początkowe
  • przesunięcie indeksów (F(1)=1 czy F(1)=0)
  • przepełnienie typu liczbowego w C/C++
  • mylenie rekurencji z wydajnością
  • brak testów dla małych wartości

Błąd w definicji początkowej powoduje, że cały ciąg staje się inny, a program nadal „wygląda poprawnie”.

Prosty test kontrolny

WejścieOczekiwany wynik
00
11
21
32
55
1055

Krótki test w Python

JęzykKod
Pythonfor i in range(11):
print(i, fib_iter(i))

Takie testy są banalne, ale oszczędzają godziny szukania błędu później.

W praktyce warto też mierzyć czas wykonania. Program, który daje poprawny wynik po 40 sekundach, często jest po prostu zły projektowo.

Na co uważać przy pracy z dużymi wartościami n i przy zadaniach rekrutacyjnych

Dla dużych n pojawia się kolejny problem: rozmiar liczby.

Python radzi sobie dobrze, ponieważ obsługuje liczby całkowite o arbitralnej długości. W C i C++ standardowe typy mają ograniczenia.

Przykładowo:

  • int zwykle kończy się w okolicach 2 miliardów
  • long long daje większy zakres, ale nadal skończony

Dla większych indeksów trzeba używać bibliotek big integer albo liczyć modulo, jeśli zadanie tego wymaga.

W zadaniach rekrutacyjnych bardzo często pojawia się wariant:

„Oblicz n-ty wyraz modulo 1 000 000 007”

To już nie jest szkolny przykład, tylko test znajomości ograniczeń pamięci i czasu.

Wersja z modulo

JęzykKod
Pythondef fib_mod(n):
mod = 1000000007
a = 0
b = 1
for i in range(n):
a, b = b % mod, (a + b) % mod
return a

Takie podejście pojawia się bardzo często w konkursach algorytmicznych.

FAQ

Czy rekurencja zawsze jest gorsza od iteracji?

Nie. Rekurencja bywa czytelniejsza i naturalna dla problemów drzewiastych, np. DFS czy parsowanie struktur. Problem pojawia się wtedy, gdy powtarza te same obliczenia bez kontroli.

Dlaczego fib(40) działa tak długo w wersji naiwnej?

Bo funkcja wielokrotnie liczy te same wartości. fib(38) i fib(37) uruchamiają kolejne identyczne gałęzie obliczeń, a ich liczba rośnie wykładniczo.

Czy memoizacja zawsze jest najlepszym wyborem?

Nie zawsze. Czasem prostsza i szybsza będzie iteracja bottom-up. Memoizacja jest świetna dydaktycznie i wygodna przy bardziej złożonych zależnościach.

Czy warto uczyć się tego przykładu, skoro rzadko występuje w realnym projekcie?

Tak, bo nie chodzi o sam ciąg, tylko o sposób myślenia algorytmicznego. Ten sam schemat wraca później w dużo poważniejszych problemach.

Czy Python jest dobrym językiem do takich ćwiczeń?

Tak, szczególnie na początku. Kod jest krótki, łatwo testować przypadki brzegowe i nie trzeba od razu walczyć z ograniczeniami typów liczbowych.

Ciąg Fibonacciego jest prosty tylko na pierwszy rzut oka. W rzeczywistości to bardzo dobry test rozumienia algorytmów, złożoności i jakości decyzji programistycznych. Właśnie dlatego wraca tak często i właśnie dlatego warto go pisać więcej niż raz.

Źródło Foto: Freepik

Zobacz również

Python Range

Python Range

2026-04-19
Jak stworzyć grę na Androida

Jak stworzyć grę na Androida – kompleksowy przewodnik techniczny dla programistów

2026-03-06
Jak się programuje

Jak się programuje i buduje poprawne, wydajne oraz czytelne rozwiązania krok po kroku

2026-03-27

Dodaj komentarz