Stos wywołań i debugowanie rekurencji

1. Czym jest stos wywołań?

Stos wywołań (call stack) to struktura danych używana przez program do śledzenia aktywnych wywołań funkcji.

Zasada działania:

Każde wywołanie funkcji:
1. Dodaje nową RAMKĘ (frame) na szczyt stosu
2. Zapisuje: lokalne zmienne, parametry, adres powrotu
3. Po zakończeniu funkcji: ZDEJMUJE ramkę ze stosu

Wizualizacja:

                ┌──────────────┐
                │ funkcja_3()  │ ← TOP (aktualnie wykonywana)
                ├──────────────┤
                │ funkcja_2()  │
                ├──────────────┤
                │ funkcja_1()  │
                ├──────────────┤
                │ main()       │
                └──────────────┘

2. Jak działa stos wywołań? (krok po kroku)

Przykład:

Stos wywołań krok po kroku:

1. Wywołanie funkcja_a()
   STOS: [main, funkcja_a]
   Wypisz: "A: start"

2. Wywołanie funkcja_b() z funkcja_a
   STOS: [main, funkcja_a, funkcja_b]
   Wypisz: "B: start"

3. Wywołanie funkcja_c() z funkcja_b
   STOS: [main, funkcja_a, funkcja_b, funkcja_c]
   Wypisz: "C: wykonuję"

4. Zakończenie funkcja_c()
   STOS: [main, funkcja_a, funkcja_b]
   Wypisz: "B: koniec"

5. Zakończenie funkcja_b()
   STOS: [main, funkcja_a]
   Wypisz: "A: koniec"

6. Zakończenie funkcja_a()
   STOS: [main]

Wynik:

A: start
B: start
C: wykonuję
B: koniec
A: koniec

3. Stos wywołań w rekurencji

Przykład: Silnia

Stos wywołań:

Krok 1: factorial(3)
STOS: [factorial(3)]

Krok 2: factorial(3) wywołuje factorial(2)
STOS: [factorial(3), factorial(2)]

Krok 3: factorial(2) wywołuje factorial(1)
STOS: [factorial(3), factorial(2), factorial(1)]

Krok 4: factorial(1) wywołuje factorial(0)
STOS: [factorial(3), factorial(2), factorial(1), factorial(0)]

Krok 5: factorial(0) zwraca 1 (przypadek bazowy)
STOS: [factorial(3), factorial(2), factorial(1)]
result = 1

Krok 6: factorial(1) zwraca 1 * 1 = 1
STOS: [factorial(3), factorial(2)]
result = 1

Krok 7: factorial(2) zwraca 2 * 1 = 2
STOS: [factorial(3)]
result = 2

Krok 8: factorial(3) zwraca 3 * 2 = 6
STOS: []
result = 6

Wynik:

→ Wywołanie factorial(3)
→ Wywołanie factorial(2)
→ Wywołanie factorial(1)
→ Wywołanie factorial(0)
← Zwracam 1
← Zwracam 1
← Zwracam 2
← Zwracam 6

4. Wizualizacja z wcięciami

Funkcja pomocnicza:

Wynik:

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

5. Symulacja stosu wywołań ręcznie

Możemy symulować stos wywołań używając listy:

Wynik:

Push 4 → Stos: [4]
Push 3 → Stos: [4, 3]
Push 2 → Stos: [4, 3, 2]
Push 1 → Stos: [4, 3, 2, 1]
Pop 1 → Wynik: 1, Stos: [4, 3, 2]
Pop 2 → Wynik: 2, Stos: [4, 3]
Pop 3 → Wynik: 6, Stos: [4]
Pop 4 → Wynik: 24, Stos: []

Wynik końcowy: 24

6. Limit głębokości rekurencji

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

Co się stanie, gdy przekroczymy limit?

Praktyczny przykład – suma do miliona:

Rozwiązanie: Zwiększenie limitu (OSTROŻNIE!)

UWAGA: Zwiększanie limitu może spowodować crash programu!

7. Debugowanie rekurencji

7.1. Print debugging

Najprostsza metoda – dodaj printy:

Wynik pokazuje drzewo wywołań:

→ fib(4)
  → fib(3)
    → fib(2)
      → fib(1)
      ← fib(1) = 1
      → fib(0)
      ← fib(0) = 0
    ← fib(2) = 1
    → fib(1)
    ← fib(1) = 1
  ← fib(3) = 2
  → fib(2)
    → fib(1)
    ← fib(1) = 1
    → fib(0)
    ← fib(0) = 0
  ← fib(2) = 1
← fib(4) = 3

7.2. Licznik wywołań

Zlicz, ile razy funkcja została wywołana:

7.3. Dekorator do debugowania

8. Narzędzia do debugowania

8.1. Python Debugger (pdb)

Komendy pdb: - n (next) – następna linia - s (step) – wejdź do funkcji - c (continue) – kontynuuj - p zmienna (print) – wypisz wartość - bt (backtrace) – pokaż stos wywołań

8.2. Python Tutor (online)

Wizualizuj wykonanie kodu online: https://pythontutor.com/

Korzyści: - Wizualizacja stosu wywołań - Krok po kroku - Zmienne lokalne i globalne

9. Stack trace (ślad stosu)

Gdy wystąpi błąd, Python pokazuje stack trace:

Wynik:

Traceback (most recent call last):
  File "test.py", line 12, in <module>
    funkcja_a()
  File "test.py", line 2, in funkcja_a
    funkcja_b()
  File "test.py", line 5, in funkcja_b
    funkcja_c()
  File "test.py", line 8, in funkcja_c
    raise ValueError("Błąd w funkcji C!")
ValueError: Błąd w funkcji C!

Jak czytać: - Od dołu do góry: najbliższy błąd → najwyższe wywołanie - Każda linia pokazuje: plik, numer linii, funkcja

10. Analiza pamięci stosu

10.1. Rozmiar ramki stosu

10.2. Zużycie pamięci dla głębokiej rekurencji

11. Wykrywanie nieskończonej rekurencji

11.1. Dekorator timeout

11.2. Ograniczenie głębokości ręczne

12. Optymalizacja zużycia stosu

12.1. Rekurencja ogonowa (tail recursion)

Uwaga: Python NIE optymalizuje rekurencji ogonowej!

12.2. Konwersja do iteracji

13. Praktyczne wskazówki debugowania

✅ DO:

Dodaj printy na początku i końcu funkcji
Wizualizuj z wcięciami (level)
Licz wywołania – sprawdź, czy nie za dużo
Testuj małe dane – zacznij od n=2, 3, 4
Używaj debuggera (pdb, IDE)

❌ NIE:

Nie testuj od razu dużych danych (n=1000)
Nie ignoruj RecursionError – to znak problemu
Nie używaj rekurencji dla prostych pętli
Nie zapomnij o przypadku bazowym!

14. Ćwiczenia debugowania

Zadanie 1: Znajdź błąd

Odpowiedź

Brak zmniejszania n! Powinno być `suma_do_n(n - 1)`.

Zadanie 2: Dlaczego RecursionError?

Odpowiedź

Nie zmniejszamy listy! Powinno być `odwroc_liste(lista[:-1])`.

15. Podsumowanie

Stos wywołań:

Struktura LIFO do śledzenia aktywnych funkcji
Każde wywołanie → nowa ramka na stosie
Zakończenie → zdejmujemy ramkę
Python: domyślny limit 1000

Debugowanie rekurencji:

Print debugging – najprostsze i skuteczne
Liczniki wywołań – wykrywaj niewydajność
Python Tutor – wizualizuj online
pdb – zaawansowane debugowanie
Stack trace – czytaj błędy od dołu

Najczęstsze problemy:

Brak przypadku bazowego → nieskończona rekurencja
Niezmniejszanie argumentu → przypadek bazowy nigdy nie osiągnięty
Zapomnienie return → funkcja zwraca None
Za głęboka rekurencja → RecursionError

Optymalizacja:

Ogranicz głębokość ręcznie
Użyj iteracji dla głębokich wywołań
Rozważ memoizację
Python NIE optymalizuje tail recursion!

Co dalej warto poznać:

Rekurencja ogonowa (tail recursion)
Programowanie dynamiczne
Memoizacja
Konwersja rekurencja ↔ iteracja