BITEDU.PL

Rekurencja w różnych kontekstach

1. Wstęp – co to w ogóle znaczy „rekurencja”?

Zacznijmy od prostego przykładu z życia.

Wyobraź sobie, że stoisz przed lustrem, a za Tobą stoi drugie lustro.
Co widzisz?
Siebie w nieskończoności – obraz w obrazie, w obrazie, w obrazie…

To właśnie rekurencja.
Sytuacja, w której coś odwołuje się samo do siebie.

W języku łacińskim „recurrere” znaczy „powracać” – i dokładnie o to chodzi: powrót do początku, ale w mniejszej skali.

2. Rekurencja w codziennym życiu

Rekurencja to nie tylko temat z informatyki.
Pojawia się w sztuce, naturze, a nawet w ludzkim zachowaniu.

Kilka przykładów:

  • Rosyjska matrioszka – każda lalka kryje w sobie mniejszą kopię samej siebie.
  • Gałąź drzewa – z jednej wyrastają mniejsze, z nich jeszcze mniejsze.
  • Fraktale – wzory, które powtarzają się w nieskończoność (np. płatek śniegu).
  • Lustro w lustrze – obraz powtarza się bez końca.
  • Życie codzienne: ktoś tłumaczy komuś, jak coś tłumaczyć – to też rekurencja!

Wszystkie te zjawiska mają wspólny motyw: powtarzanie tego samego wzoru wewnątrz siebie.

3. Rekurencja w myśleniu – czyli jak człowiek planuje

Każdy z nas używa rekurencji, choć nieświadomie.
Gdy planujesz coś dużego (np. remont pokoju), myślisz:

  1. Muszę pomalować pokój.
  2. Żeby pomalować, muszę kupić farbę.
  3. Żeby kupić farbę, muszę pojechać do sklepu.
  4. Żeby pojechać do sklepu, muszę zatankować auto…

Widzisz? Każdy krok to mniejsze zadanie w obrębie większego.
Tak działa rekurencja – duży problem rozbijasz na mniejsze, które rozwiązują się w ten sam sposób.

4. Rekurencja w informatyce – funkcja, która woła samą siebie

W programowaniu rekurencja to sposób, w jaki funkcja wywołuje samą siebie, aż do momentu, gdy nie trzeba już nic więcej liczyć.

Schemat:

FUNKCJA()
 └── robi coś
 └── woła samą siebie z prostszym zadaniem
 └── aż dojdzie do najprostszego przypadku

Taki najprostszy przypadek nazywamy warunkiem końcowym albo bazowym – bez niego rekurencja nigdy by się nie skończyła (program zapętliłby się jak lustra w lustrze).

5. Pierwszy przykład – odliczanie

Zacznijmy bardzo prosto:

def odliczanie(n):
    if n == 0:
        print("Start!")
    else:
        print(n)
        odliczanie(n - 1)

odliczanie(5)

Wynik:

5
4
3
2
1
Start!

Jak to działa:

  • Funkcja odliczanie wywołuje samą siebie z coraz mniejszą liczbą.
  • Gdy n == 0, kończy działanie (to warunek bazowy).
  • Po drodze wykonuje ten sam schemat dla każdego kroku.

6. Przykład 2 – silnia (faktorial)

Silnia to klasyczny przykład rekurencji:
5! = 5 * 4 * 3 * 2 * 1

Zamiast robić pętlę, funkcja może „powtarzać się” sama:

def silnia(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * silnia(n - 1)

print(silnia(5))

Wynik:

120

Jak to myśleć:

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

Każde wywołanie czeka, aż to mniejsze się zakończy – dokładnie jak pudełka matrioszek.

7. Przykład 3 – ciąg Fibonacciego

To ciąg, w którym każdy kolejny element to suma dwóch poprzednich:
0, 1, 1, 2, 3, 5, 8, 13...

Rekurencja świetnie tu pasuje:

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

for i in range(8):
    print(fib(i), end=" ")

Wynik:

0 1 1 2 3 5 8 13

Każde wywołanie fib(n) uruchamia dwa kolejne: fib(n-1) i fib(n-2).
To jak drzewo – rozgałęzia się, aż dojdzie do podstawy (0 i 1).

8. Rekurencja a stos

Za każdym razem, gdy funkcja wywołuje samą siebie, komputer odkłada jej dane na stosie – pamięci podręcznej, gdzie trzyma wszystkie „niedokończone wywołania”.

Wygląda to tak:

silnia(5)
→ czeka na silnia(4)
   → czeka na silnia(3)
      → czeka na silnia(2)
         → czeka na silnia(1)
            → zwraca 1

Każdy poziom wraca z wynikiem do poprzedniego — aż stos się „rozpakowuje”.
Dlatego rekurencja i stos to nierozłączne pojęcia.

9. Gdzie spotkasz rekurencję w prawdziwym świecie

  • W grach komputerowych – generowanie drzew, map, labiryntów.
  • W grafice – fraktale, płatki śniegu, symetrie.
  • W wyszukiwaniu – przeszukiwanie folderów, drzew plików.
  • W sztucznej inteligencji – drzewa decyzji, algorytmy rozumowania.
  • W matematyce – rozwiązywanie równań przez dzielenie problemu na mniejsze.

10. Zadania dla ucznia

  1. Napisz funkcję rekurencyjną, która wypisze liczby od 1 do n.
  2. Napisz funkcję rekurencyjną suma(n), która zwróci sumę liczb od 1 do n.
  3. Przerób funkcję silnia tak, by wypisywała każdy krok obliczeń.
  4. Spróbuj zapisać fib(n) bez rekurencji, używając pętli.
    Porównaj, która wersja działa szybciej.
  5. Dla chętnych: narysuj drzewo wywołań funkcji fib(5) – zobaczysz, jak się rozgałęzia.

11. Najczęstsze błędy przy rekurencji

  • Brak warunku końcowego → program zapętli się w nieskończoność.
  • Zbyt głęboka rekurencja → komputerowi zabraknie pamięci (błąd „RecursionError”).
  • Zbyt ogólne myślenie → pamiętaj, że rekurencja zawsze musi zmierzać do prostszego problemu.

12. Podsumowanie

  • Rekurencja to sposób rozwiązywania problemów poprzez odwoływanie się do siebie w mniejszej skali.
  • W informatyce oznacza funkcję, która wywołuje samą siebie, aż do osiągnięcia prostego przypadku.
  • Każde wywołanie trafia na stos, który komputer „rozpakowuje” po kolei.
  • Rekurencja pozwala myśleć logicznie i hierarchicznie – rozbijając duże zadania na mniejsze kroki.

13. Do zapamiętania jednym zdaniem

Rekurencja to jak nauczanie samego siebie — rozwiązujesz problem, robiąc to samo, tylko krok po kroku, coraz prościej.