Korepetycje Informatyka

Menu
Skontaktuj się
korepetycje informatyka.pl – korepetycje i kurs do matury z informatyki
Menu
Skontaktuj się

Rekurencja – co to jest? Przykłady w Pythonie krok po kroku

Minimalistyczna okładka artykułu o rekurencji w Pythonie

Rekurencja to jedno z tych pojęć w programowaniu, które na początku może wydawać się skomplikowane. Funkcja wywołująca samą siebie? Brzmi jak sposób na stworzenie programu działającego w nieskończoność. W rzeczywistości rekurencja jest bardzo przydatną techniką, która pozwala rozwiązywać wiele problemów w prosty i czytelny sposób.

W tym wpisie wyjaśniam, co to jest rekurencja, jak działa funkcja rekurencyjna oraz dlaczego tak ważny jest warunek zakończenia. Pokażę też kilka przykładów rekurencji w Pythonie – od prostego odliczania, przez silnię, aż po ciąg Fibonacciego.

Co to jest rekurencja?

Rekurencja to sposób rozwiązywania problemu, w którym funkcja wywołuje samą siebie, ale dla prostszego przypadku.

Najprostszy przykład może wyglądać tak:

Python · odliczanie
def odliczanie(n):
    print(n)
    if n > 0:
        odliczanie(n - 1)

odliczanie(5)

Program wyświetli:

5 → 4 → 3 → 2 → 1 → 0

Funkcja wykonuje część pracy i uruchamia samą siebie z mniejszą wartością. Gdy n osiąga zero, kolejne wywołanie już nie następuje.

Z czego składa się funkcja rekurencyjna?

Poprawnie zbudowana funkcja rekurencyjna ma dwa elementy:

  • przypadek bazowy – określa, kiedy zatrzymać kolejne wywołania,
  • krok rekurencyjny – wywołuje tę samą funkcję dla prostszego problemu.
Python · przypadek bazowy i krok rekurencyjny
def odliczanie(n):
    print(n)
    if n > 0:          # przypadek bazowy: gdy n = 0, zatrzymujemy się
        odliczanie(n - 1)  # krok rekurencyjny: zmniejszamy problem

Każde kolejne wywołanie otrzymuje mniejszą wartość n. To warunek konieczny, aby funkcja rzeczywiście doszła do przypadku bazowego.

Dlaczego warunek zakończenia rekurencji jest tak ważny?

Brak przypadku bazowego jest jednym z najczęstszych błędów przy nauce rekurencji.

Python · błędny przykład
def funkcja(n):
    print(n)
    funkcja(n - 1)

Funkcja będzie próbowała wykonywać kolejne wywołania bez końca:

funkcja(5) → funkcja(4) → … → funkcja(0) → funkcja(-1) → …

Python po pewnym czasie zakończy program błędem RecursionError: maximum recursion depth exceeded. Zanim napiszesz krok rekurencyjny, ustal zawsze: kiedy funkcja ma się zatrzymać?

Rekurencja w Pythonie - przykład z silnią

Jednym z najpopularniejszych przykładów zastosowania rekurencji jest obliczanie silni.

5! = 5 × 4!
4! = 4 × 3!
3! = 3 × 2!

Problem naturalnie można więc zapisać rekurencyjnie:

Python · silnia
def silnia(n):
    if n == 0:
        return 1
    return n * silnia(n - 1)

print(silnia(5))

Wynik: 120.

Więcej sposobów liczenia silni (pętla for, while, wersja w C++) i najczęstsze błędy znajdziesz w osobnym wpisie: silnia – co to jest i jak ją obliczyć.

Jak działa rekurencyjne obliczanie silni?

Przeanalizujmy dokładnie działanie silnia(5):

silnia(5) → 5 × silnia(4)
→ 5 × 4 × silnia(3)
→ 5 × 4 × 3 × silnia(2)
→ 5 × 4 × 3 × 2 × silnia(1)
→ 5 × 4 × 3 × 2 × 1 × silnia(0)
Python · przypadek bazowy
if n == 0:
    return 1
Powrót wyników: 1 → 1 → 2 → 6 → 24 → 120

Funkcje są najpierw wywoływane, a potem zwracają wyniki w odwrotnej kolejności.

Rekurencja a stos wywołań funkcji

Każde wywołanie funkcji musi zostać zapamiętane przez program. Dla silnia(4) wygląda to tak:

silnia(4)
  ↳ silnia(3)
    ↳ silnia(2)
      ↳ silnia(1)
        ↳ silnia(0)

Po osiągnięciu przypadku bazowego program zaczyna wracać:

silnia(0) → 1 → silnia(1) → 1 → silnia(2) → 2 → silnia(3) → 6 → silnia(4) → 24

Takie przechowywanie kolejnych wywołań odbywa się na tzw. stosie wywołań. Bardzo głęboka rekurencja może więc zużywać dużo pamięci.

Ciąg Fibonacciego z wykorzystaniem rekurencji

Kolejnym klasycznym przykładem jest ciąg Fibonacciego: 0, 1, 1, 2, 3, 5, 8, 13….

F(n) = F(n – 1) + F(n – 2)
Python · ciąg Fibonacciego
def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(7))

Wynik: 13. Funkcja ma dwa przypadki bazowe – dla 0 i 1.

Obie wersje, rekurencyjną i iteracyjną, znajdziesz też z pseudokodem w encyklopedii Prymo: ciąg Fibonacciego rekurencyjnie oraz ciąg Fibonacciego iteracyjnie.

Czy rekurencja zawsze jest najlepszym rozwiązaniem?

Rekurencja nie zawsze jest najlepszym rozwiązaniem. Dla ciągu Fibonacciego wersja rekurencyjna jest czytelna, ale dla większych wartości wielokrotnie oblicza te same wyniki.

Python · Fibonacci – wersja rekurencyjna
def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

Wersja iteracyjna jest w tym przypadku wydajniejsza:

Python · Fibonacci – wersja iteracyjna
def fibonacci(n):
    a = 0
    b = 1
    for i in range(n):
        a, b = b, a + b
    return a

Rekurencja nie jest „lepszą pętlą” – to po prostu inny sposób rozwiązania określonego typu problemu.

Rekurencja a iteracja - czym się różnią?

Iteracja powtarza instrukcje za pomocą pętli, np. for lub while. Rekurencja ponownie wywołuje tę samą funkcję.

Silnię możemy policzyć na oba sposoby:

Python · silnia – rekurencja
def silnia(n):
    if n == 0:
        return 1
    return n * silnia(n - 1)
Python · silnia – iteracja
def silnia(n):
    wynik = 1
    for i in range(1, n + 1):
        wynik *= i
    return wynik

Oba programy zwracają ten sam wynik – różni się sposób dojścia do rozwiązania.

Kiedy warto stosować rekurencję?

Rekurencja sprawdza się szczególnie dobrze w problemach, które naturalnie można podzielić na mniejsze wersje tego samego problemu.

Przykłady to:

  • przeszukiwanie struktur drzewiastych,
  • przechodzenie po folderach i podfolderach,
  • algorytmy typu dziel i zwyciężaj,
  • przeszukiwanie grafów,
  • niektóre algorytmy sortowania,
  • obliczanie silni,
  • generowanie kombinacji,
  • rozwiązywanie problemów metodą backtracking.

Dobrym sposobem na rozpoznanie potencjalnego zastosowania rekurencji jest zadanie sobie pytania:

Czy rozwiązanie większego problemu mogę zbudować na podstawie rozwiązania jego mniejszej wersji?

Jeśli odpowiedź brzmi „tak”, rekurencja może być dobrym rozwiązaniem.

Rekurencja - najczęstsze błędy

Podczas pierwszych ćwiczeń z rekurencją najczęściej pojawiają się trzy problemy.

Brak przypadku bazowego

Funkcja wywołuje samą siebie bez końca.

Problem nie staje się prostszy

Python · błędny krok rekurencyjny
def funkcja(n):
    if n == 0:
        return
    funkcja(n + 1)

Przypadek bazowy istnieje, ale dla dodatniego n oddalamy się od zera zamiast się do niego zbliżać.

Nieprawidłowe użycie return

Poprawnie
return n * silnia(n - 1)
Niepoprawnie
n * silnia(n - 1)

W drugiej wersji wynik nie zostanie zwrócony przez funkcję.

Jak nauczyć się rekurencji?

Dobrym ćwiczeniem jest suma liczb od 1 do n. Dla 5 liczymy: 1 + 2 + 3 + 4 + 5.

suma(5) = 5 + suma(4)
suma(4) = 4 + suma(3)
suma(3) = 3 + suma(2)
Python · suma liczb
def suma(n):
    if n == 0:
        return 0
    return n + suma(n - 1)

print(suma(5))

Wynik: 15. To dobre ćwiczenie, jeśli silnia wydaje Ci się jeszcze nieintuicyjna.

Rekurencja na maturze z informatyki

Na maturze z informatyki nie wystarczy przepisać gotowej funkcji rekurencyjnej z pamięci. Trzeba rozumieć, co dzieje się przy każdym wywołaniu.

Przed egzaminem radzę sprawdzić, czy potrafisz:

  • przeanalizować działanie funkcji rekurencyjnej,
  • wskazać przypadek bazowy,
  • określić kolejność wywołań,
  • obliczyć wynik dla konkretnego argumentu,
  • porównać rozwiązanie rekurencyjne z iteracyjnym,
  • samodzielnie zapisać prosty algorytm rekurencyjny.

Zadania w stylu maturalnym (analiza wywołań, wynik dla konkretnego argumentu) przećwiczysz w zadaniach z rekurencji na Prymo. Pełny zakres egzaminu opisuję w przewodniku po maturze z informatyki rozszerzonej.

Jeśli przygotowujesz się do matury i chcesz przećwiczyć rekurencję razem z resztą materiału (algorytmy, Python, bazy danych, zadania z arkuszy), zapraszam na korepetycje z informatyki. Uczą u nas ludzie, którzy sami zdali tę maturę, a pracujemy na konkretnych zadaniach, nie na gotowym kodzie do zapamiętania.

Podsumowanie - co warto zapamiętać?

Rekurencja polega na tym, że funkcja wywołuje samą siebie dla prostszej wersji tego samego problemu. Każda poprawna funkcja rekurencyjna musi mieć przypadek bazowy, który zatrzymuje kolejne wywołania.

Na początku rekurencja może wydawać się mniej intuicyjna niż zwykła pętla. Po rozpisaniu kolejnych wywołań na kartce szybko okazuje się jednak, że jej działanie jest bardzo logiczne.

Moja główna rada: nie ucz się gotowego kodu na pamięć. Lepiej zrozumieć trzy rzeczy:

  • kiedy funkcja się zatrzymuje,
  • jak problem jest zmniejszany,
  • co dzieje się podczas powrotu z kolejnych wywołań.

Gdy zrozumiesz ten mechanizm na przykładzie silni, sumy liczb czy ciągu Fibonacciego, znacznie łatwiej będzie Ci analizować bardziej rozbudowane algorytmy rekurencyjne.

Umów się na zajęcia!

Kategorie

Instagram Facebook Tiktok Compass

Powiązane posty

Minimalistyczna okładka artykułu o silni w Pythonie i C++
Przygotowanie do matury
Szymon Leszkiewicz

Silnia – co to jest i jak ją obliczyć? Python, C++ i przykłady

Silnia to jedno z podstawowych pojęć, z którym spotkasz się podczas nauki matematyki, algorytmiki i programowania. Samo działanie jest proste, ale świetnie pokazuje kilka ważnych mechanizmów – pracę z pętlami, funkcjami oraz rekurencją. W tym wpisie wyjaśniam, co to jest silnia, jak ją obliczyć ręcznie oraz jak napisać program liczący silnię w Pythonie i C++. Pokażę też rozwiązanie iteracyjne i rekurencyjne oraz najczęstsze błędy pojawiające się w takich zadaniach. Co to jest silnia? Silnia liczby

Czytaj więcej »
2026-09-21 Brak komentarzy
Studia po maturze z informatyki: jak wybrać kierunek i 3 alternatywy, gdy się nie dostałeś
Przygotowanie do matury
Szymon Leszkiewicz

Studia po maturze z informatyki: jak wybrać kierunek i 3 alternatywy, gdy się nie dostałeś

Masz przed sobą wyniki kwalifikacji i jedną z dwóch sytuacji. Albo dostałeś się na dwa kierunki i nie wiesz, który wybrać, albo nie dostałeś się na informatykę pierwszego wyboru i szukasz planu B. Ten wpis dotyczy obu sytuacji i jest przeznaczony dla Ciebie, jeśli decyzję o studiach podejmujesz właśnie teraz. Zacznę od rzeczy, którą powtarzam każdemu uczniowi podczas mentoringu dotyczącego wyboru studiów po maturze z informatyki: nazwa kierunku znaczy mniej, niż myślisz. Programy informatyki i

Czytaj więcej »
2026-07-29 Brak komentarzy

Umów pierwszą lekcję

Zostaw kontakt, oddzwonimy. Możesz też zadzwonić od razu – najszybciej ustalimy wszystko przez telefon.

Email

info@korepetycjeinformatyka.pl

Telefon

+48 884 699 256

Zobacz najczęstsze pytania
Social Media - ZOBACZ CO WRZUCAMY!
Instagram Facebook Tiktok