Wprowadzenie do rekurencji - jak myśleć rekurencyjnie

1. Czym jest rekurencja?

Rekurencja to technika programowania, w której funkcja wywołuje samą siebie w celu rozwiązania problemu.

Definicja matematyczna:

Rekurencja: patrz "rekurencja" 😄

Analogia ze świata rzeczywistego:

Rosyjskie matroszki (babuszki): - Każda lalka zawiera mniejszą lalkę - Najmniejsza lalka nie zawiera nic (przypadek bazowy) - Otwierając lalkę, odkrywamy mniejszą wersję tego samego problemu

🪆 → 🪆 → 🪆 → 🪆 → 🪆 (najmniejsza, nie da się otworzyć)

2. Anatomia funkcji rekurencyjnej

Każda funkcja rekurencyjna musi mieć dwa kluczowe elementy:

2.1. Przypadek bazowy (base case)

Warunek, który zatrzymuje rekurencję. Bez niego funkcja wywołuje się w nieskończoność!

2.2. Krok rekurencyjny (recursive case)

Wywołanie funkcji dla mniejszego problemu.

Kompletny przykład – silnia:

3. Jak działa rekurencja? (krok po kroku)

Przykład: `factorial(3)`

factorial(3)
  ↓
  3 * factorial(2)
        ↓
        2 * factorial(1)
              ↓
              1 * factorial(0)
                    ↓
                    1  ← przypadek bazowy

Teraz wracamy:
                    1
              1 * 1 = 1
        2 * 1 = 2
  3 * 2 = 6

Wynik: 6

Wizualizacja drzewa wywołań:

            factorial(3)
                 |
            3 * factorial(2)
                     |
                2 * factorial(1)
                         |
                    1 * factorial(0)
                             |
                            1

4. Pierwszy przykład: Odliczanie

4.1. Wersja iteracyjna

4.2. Wersja rekurencyjna

Jak to działa:

odliczanie(5) → wypisz 5, wywołaj odliczanie(4)
odliczanie(4) → wypisz 4, wywołaj odliczanie(3)
odliczanie(3) → wypisz 3, wywołaj odliczanie(2)
odliczanie(2) → wypisz 2, wywołaj odliczanie(1)
odliczanie(1) → wypisz 1, wywołaj odliczanie(0)
odliczanie(0) → wypisz "Start!", STOP

5. Jak myśleć rekurencyjnie?

5.1. Zasada "Divide and Conquer" (Dziel i zwyciężaj)

Podziel problem na mniejsze wersje tego samego problemu.

Przykład: Suma liczb od 1 do n

suma(5) = 5 + suma(4)
suma(4) = 4 + suma(3)
suma(3) = 3 + suma(2)
suma(2) = 2 + suma(1)
suma(1) = 1  ← przypadek bazowy

5.2. Wzór myślenia rekurencyjnego

Znajdź przypadek bazowy – kiedy problem jest trywialny?
Zdefiniuj krok rekurencyjny – jak rozwiązać problem używając mniejszej wersji?
Upewnij się, że zbiegasz do przypadku bazowego – problem musi się zmniejszać!

5.3. Przykład: Potęgowanie

Problem: Oblicz a^n (a do potęgi n)

Myślenie rekurencyjne: - Przypadek bazowy: a^0 = 1 - Krok rekurencyjny: a^n = a * a^(n-1)

Wizualizacja dla potega(2, 4):

potega(2, 4)
= 2 * potega(2, 3)
= 2 * (2 * potega(2, 2))
= 2 * (2 * (2 * potega(2, 1)))
= 2 * (2 * (2 * (2 * potega(2, 0))))
= 2 * (2 * (2 * (2 * 1)))
= 2 * (2 * (2 * 2))
= 2 * (2 * 4)
= 2 * 8
= 16

6. Rekurencja na listach

6.1. Suma elementów listy

Wizualizacja:

suma_listy([1, 2, 3, 4, 5])
= 1 + suma_listy([2, 3, 4, 5])
= 1 + (2 + suma_listy([3, 4, 5]))
= 1 + (2 + (3 + suma_listy([4, 5])))
= 1 + (2 + (3 + (4 + suma_listy([5]))))
= 1 + (2 + (3 + (4 + (5 + suma_listy([])))))
= 1 + (2 + (3 + (4 + (5 + 0))))
= 15

6.2. Długość listy

6.3. Odwracanie listy

6.4. Maximum w liście

7. Rekurencja na stringach

7.1. Odwracanie stringa

7.2. Palindrom (sprawdzanie)

7.3. Zliczanie wystąpień znaku

8. Wizualizacja rekurencji z printem

Dodajmy printy, żeby zobaczyć, co się dzieje:

Wynik:

→ factorial(4)
  → factorial(3)
    → factorial(2)
      → factorial(1)
        → factorial(0)
        ← zwracam 1
      ← zwracam 1
    ← zwracam 2
  ← zwracam 6
← zwracam 24

9. Typowe błędy początkujących

Błąd 1: Brak przypadku bazowego

Błąd 2: Przypadek bazowy nigdy nie jest osiągany

Błąd 3: Zapomnienie o return

Poprawnie:

10. Wzorce rekurencyjne

10.1. Wzorzec "Zmniejsz o 1"

Przykłady: silnia, suma, potęga

10.2. Wzorzec "Podziel na pół"

Przykłady: merge sort, binary search

10.3. Wzorzec "Głowa + ogon"

Przykłady: suma listy, długość listy

11. Kiedy używać rekurencji?

Używaj rekurencji gdy:

✅ Problem ma strukturę rekurencyjną (drzewa, grafy) ✅ Dzielenie problemu jest naturalne (merge sort, quick sort) ✅ Czytelność jest ważniejsza niż wydajność ✅ Problem wymaga backtrackingu (permutacje, sudoku)

Unikaj rekurencji gdy:

❌ Można to łatwo zrobić iteracyjnie (proste pętle) ❌ Wydajność jest krytyczna (rekurencja wolniejsza) ❌ Głębokość może być bardzo duża (stack overflow) ❌ Problem nie ma struktury rekurencyjnej

12. Przykłady problemów rekurencyjnych

12.1. Liczby Fibonacciego

12.2. Liczba cyfr w liczbie

12.3. Suma cyfr liczby

12.4. NWD (Największy Wspólny Dzielnik) – Algorytm Euklidesa