Rekurencja ogonowa

1. Czym jest rekurencja ogonowa?

Rekurencja ogonowa (tail recursion) to szczególny przypadek rekurencji, gdzie wywołanie rekurencyjne jest ostatnią operacją w funkcji.

Definicja:

Funkcja ma rekurencję ogonową, jeśli wywołanie rekurencyjne jest ostatnią rzeczą, którą funkcja robi (nie ma żadnych operacji PO rekurencji).

2. Porównanie: ogonowa vs nie-ogonowa

2.1. NIE-ogonowa (zwykła rekurencja)

Dlaczego NIE jest ogonowa? - Po powrocie z factorial_nie_ogonowa(n - 1) musimy pomnożyć wynik przez n - Funkcja nie może zakończyć się od razu – musi poczekać na wynik i go przetworzyć

2.2. Ogonowa (tail recursive)

Dlaczego JEST ogonowa? - Wywołanie rekurencyjne to ostatnia operacja - Nie ma nic do zrobienia po powrocie z rekurencji - Funkcja może od razu przekazać sterowanie

3. Wizualizacja różnicy

3.1. NIE-ogonowa – factorial(4)

factorial(4)
  return 4 * factorial(3)           ← Czeka na wynik, żeby pomnożyć
              return 3 * factorial(2) ← Czeka
                         return 2 * factorial(1)
                                    return 1 * factorial(0)
                                               return 1

Powrót:
                                               1
                                    1 * 1 = 1
                         2 * 1 = 2
              3 * 2 = 6
  4 * 6 = 24

Stos wywołań:

factorial(4) - czeka na factorial(3)
  factorial(3) - czeka na factorial(2)
    factorial(2) - czeka na factorial(1)
      factorial(1) - czeka na factorial(0)
        factorial(0) - zwraca 1

Wszystkie ramki MUSZĄ pozostać na stosie!

3.2. Ogonowa – factorial_ogonowa(4, 1)

factorial_ogonowa(4, 1)
  return factorial_ogonowa(3, 4)    ← Nic nie czeka, od razu przekaż
    return factorial_ogonowa(2, 12)
      return factorial_ogonowa(1, 24)
        return factorial_ogonowa(0, 24)
          return 24

W kompilatorze z TCO (Tail Call Optimization):
Tylko JEDNA ramka na stosie w danym momencie!

Kluczowa różnica: - NIE-ogonowa: O(n) pamięci (wszystkie ramki na stosie) - Ogonowa (z TCO): O(1) pamięci (jedna ramka wielokrotnie używana)

4. Przekształcanie na rekurencję ogonową

Wzorzec przekształcenia:

4.1. Przykład: Suma liczb

NIE-ogonowa:

Ogonowa:

Użycie:

4.2. Przykład: Odwracanie listy

NIE-ogonowa:

Ogonowa:

Test:

5. Python a optymalizacja rekurencji ogonowej

5.1. Prawda o Pythonie

Python NIE optymalizuje rekurencji ogonowej (TCO)!

5.2. Dlaczego Python nie ma TCO?

Guido van Rossum (twórca Pythona) celowo NIE dodał TCO:

  1. Stack trace byłby niekompletny (gorsze debugowanie)
  2. Filozofia Pythona – "Explicit is better than implicit"
  3. Wydajność – można użyć iteracji

5.3. Rozwiązanie: Konwersja do iteracji

6. Symulacja TCO w Pythonie

Możemy ręcznie zasymulować TCO używając pętli:

Jak to działa: 1. Zamiast rekurencji zwracamy obiekt TailCall 2. trampoline "odbija" wywołania w pętli 3. Tylko jedna ramka stosu w danym momencie

7. Języki z TCO vs bez TCO

Język TCO? Uwagi
Python ❌ NIE Celowo brak, użyj iteracji
JavaScript ⚠️ Zależy ES6+ ma TCO, ale słabe wsparcie
Java ❌ NIE JVM nie wspiera
C/C++ ⚠️ Zależy Zależy od kompilatora i optymalizacji
Scheme ✅ TAK Wymaga TCO przez standard
Haskell ✅ TAK Domyślnie optymalizuje
Scala ✅ TAK Tylko dla self-recursion (@tailrec)
Rust ✅ TAK LLVM optymalizuje

8. Rekurencja ogonowa vs iteracja

8.1. Wydajność

8.2. Konwersja rekurencja ogonowa → iteracja

Każdą rekurencję ogonową można mechanicznie przekształcić do iteracji:

Przykład – silnia:

9. Rekurencja wzajemna ogonowa

Dwie lub więcej funkcji wywołujących się nawzajem:

Problem w Pythonie: Nadal RecursionError dla dużych n!

Rozwiązanie: Iteracja z flagą

10. Ćwiczenia

Zadanie 1: Przekształć na rekurencję ogonową

Rozwiązanie

Zadanie 2: Długość listy (ogonowa)

11. Kiedy używać rekurencji ogonowej?

✅ Używaj gdy:

  • Język wspiera TCO (Scheme, Haskell, Scala)
  • Chcesz czytelny kod funkcyjny
  • Problem ma naturę sekwencyjną

❌ Unikaj gdy:

  • Język nie ma TCO (Python, Java)
  • Iteracja jest prostsza
  • Wydajność jest kluczowa

W Pythonie:

Rekurencja ogonowa w Pythonie = iteracja z extra steps

Lepiej użyj od razu pętli!

12. Podsumowanie

Rekurencja ogonowa:

  • Wywołanie rekurencyjne to ostatnia operacja
  • Nie ma nic do zrobienia po powrocie
  • W językach z TCO → O(1) pamięci
  • W Pythonie → bez różnicy (brak TCO)

Przekształcenie na ogonową:

  1. Dodaj akumulator jako parametr
  2. Wykonuj operacje przed rekurencją
  3. Zwracaj wynik akumulatora w przypadku bazowym

Python a TCO:

  • Python celowo nie ma TCO
  • Rekurencja ogonowa = tak samo wolna jak zwykła
  • Rozwiązanie: użyj iteracji!

Konwersja:

Rekurencja ogonowa → Iteracja (mechaniczna konwersja)
while not stop_condition:
    akumulator = new_value
    n = decrease(n)

Kluczowa prawda:

W Pythonie rekurencja ogonowa nie daje korzyści. Jeśli planujesz rekurencję ogonową – użyj od razu iteracji!

Co dalej warto poznać:

  • Trampoline pattern (symulacja TCO)
  • Continuation-passing style (CPS)
  • Języki funkcyjne (Haskell, Scheme)
  • Programowanie funkcyjne w praktyce
Wróć do spisu lekcji