Rekurencja vs iteracja - porównanie

1. Wprowadzenie

Rekurencja i iteracja to dwa podstawowe podejścia do rozwiązywania problemów powtarzalnych.

Definicje:

Technika Definicja
Rekurencja Funkcja wywołuje samą siebie
Iteracja Używamy pętli (for, while)

Kluczowa prawda:

Każdy problem, który można rozwiązać rekurencyjnie, można też rozwiązać iteracyjnie i vice versa.

2. Proste porównanie – odliczanie

2.1. Wersja rekurencyjna

Cechy: - Wywołuje samą siebie - Warunek stop: n <= 0 - Każde wywołanie dodaje ramkę na stos

2.2. Wersja iteracyjna

Cechy: - Używa pętli while - Warunek stop: n > 0 - Jedna ramka stosu

3. Porównanie wydajności

3.1. Suma liczb od 1 do n

Rekurencja

Złożoność: - Czasowa: O(n) - Pamięciowa: O(n) – stos wywołań

Iteracja

Złożoność: - Czasowa: O(n) - Pamięciowa: O(1) – tylko zmienna suma

3.2. Benchmark – mierzenie czasu

4. Silnia – szczegółowe porównanie

4.1. Rekurencja

Stos wywołań dla factorial_rek(4):

factorial(4)
│ return 4 * factorial(3)
│   └─ factorial(3)
│      │ return 3 * factorial(2)
│      │   └─ factorial(2)
│      │      │ return 2 * factorial(1)
│      │      │   └─ factorial(1)
│      │      │      │ return 1 * factorial(0)
│      │      │      │   └─ factorial(0)
│      │      │      │      │ return 1

Pamięć: 5 ramek na stosie (O(n))

4.2. Iteracja

Wykonanie dla factorial_iter(4):

i = 1: wynik = 1 * 1 = 1
i = 2: wynik = 1 * 2 = 2
i = 3: wynik = 2 * 3 = 6
i = 4: wynik = 6 * 4 = 24
return 24

Pamięć: Tylko zmienne wynik i i (O(1))

4.3. Porównanie

Aspekt Rekurencja Iteracja
Złożoność czasowa O(n) O(n)
Złożoność pamięciowa O(n) O(1)
Czytelność ⭐⭐⭐ ⭐⭐
Wydajność ⭐⭐ ⭐⭐⭐
Prostota ⭐⭐⭐ ⭐⭐

5. Fibonacci – gdzie rekurencja zawodzi

5.1. Rekurencja naiwna

Problem: Wykładnicza złożoność czasowa!

Drzewo wywołań dla fib_rek(5):

                    fib(5)
                   /      \
              fib(4)      fib(3)
             /     \       /    \
        fib(3)   fib(2) fib(2) fib(1)
        /   \     /  \   /  \
    fib(2) fib(1) ...  ...
    /  \
fib(1) fib(0)

Liczba wywołań: 15 dla fib(5), 177 dla fib(10), 2,692,537 dla fib(20)!

Złożoność: O(2^n) – KATASTROFA!

5.2. Iteracja

Złożoność: O(n) – ZNACZNIE lepiej!

5.3. Benchmark

6. Konwersja rekurencja → iteracja

6.1. Wzorzec ogólny

Większość funkcji rekurencyjnych można przekształcić używając stosu:

↓ Konwersja ↓

6.2. Przykład: Suma rekurencyjna → iteracyjna

Rekurencja:

Iteracja ze stosem:

Iteracja prosta:

7. Konwersja iteracja → rekurencja

7.1. Pętla while → rekurencja

Iteracja:

Rekurencja:

7.2. Pętla for → rekurencja

Iteracja:

Rekurencja:

8. Kiedy używać rekurencji?

8.1. Dobre przypadki dla rekurencji

✅ Struktury drzewiastе

Wersja iteracyjna byłaby znacznie bardziej skomplikowana.

✅ Dziel i zwyciężaj (Merge Sort)

✅ Backtracking (permutacje)

8.2. Złe przypadki dla rekurencji

❌ Proste pętle

❌ Duża głębokość

9. Limit rekurencji w Pythonie

Python ma domyślny limit głębokości rekurencji:

9.1. Przekroczenie limitu

9.2. Zwiększenie limitu (OSTROŻNIE!)

10. Złożoność pamięciowa – szczegóły

10.1. Rekurencja – stos wywołań

10.2. Iteracja – stałe zmienne

10.3. Benchmark pamięci

11. Hybrydy – łączenie obu podejść

11.1. Fibonacci z memoizacją (rekurencja + cache)

11.2. Iteracja z rekurencją (Quick Sort)

12. Decyzje projektowe – rekurencja vs iteracja

Kryterium Rekurencja Iteracja
Czytelność ⭐⭐⭐ ⭐⭐
Wydajność ⭐⭐ ⭐⭐⭐
Pamięć ⭐ ⭐⭐⭐
Prostota (drzewa) ⭐⭐⭐ ⭐
Prostota (pętle) ⭐ ⭐⭐⭐
Debugowanie ⭐⭐ ⭐⭐⭐
Stack overflow Ryzyko Brak

Zasada kciuka:

Wybieraj rekurencję dla czytelności, iterację dla wydajności.

13. Podsumowanie

Rekurencja vs Iteracja:

Aspekt Rekurencja Iteracja
Mechanizm Wywołuje siebie Pętla (for/while)
Pamięć O(n) – stos O(1) – zmienne
Wydajność Wolniejsza (overhead) Szybsza
Czytelność Często lepsza Czasem gorsza
Stack overflow Ryzyko dla dużych n Brak ryzyka
Naturalna dla Drzew, grafów, backtrackingu Prostych pętli

Kluczowe wnioski:

  • Każdy problem rekurencyjny można rozwiązać iteracyjnie
  • Rekurencja często czytelniejsza, iteracja szybsza
  • Fibonacci naiwny: rekurencja O(2^n), iteracja O(n)
  • Python ma limit rekurencji (domyślnie 1000)
  • Dla drzew i grafów – rekurencja naturalna
  • Dla prostych pętli – iteracja lepsza

Co dalej warto poznać:

  • Stos wywołań (jak działa pod maską)
  • Rekurencja ogonowa (optymalizacja)
  • Memoizacja (cache dla rekurencji)
  • Programowanie dynamiczne
Wróć do spisu lekcji