Masz funkcję, która ma przejść po zagnieżdżonych folderach, drzewie kategorii albo strukturze komentarzy? Rekurencja pozwala rozwiązywać taki problem przez wywoływanie funkcji przez nią samą, ale tylko wtedy, gdy każde kolejne wywołanie zbliża się do warunku zakończenia.
Rekurencja rozkłada problem na mniejsze wywołania
- Funkcja wywołuje samą siebie, przekazując prostszy przypadek do rozwiązania.
- Warunek bazowy zatrzymuje kolejne wywołania.
- Każde wywołanie zajmuje miejsce na stosie, więc zbyt głęboka rekurencja może zakończyć się błędem.
- Drzewa i struktury zagnieżdżone często łatwiej przetwarzać rekurencyjnie niż pętlą.
- Powtarzane obliczenia, jak w naiwnym Fibonacciem, mogą sprawić, że rekurencja będzie niepotrzebnie wolna.
Funkcja rozwiązuje mniejszą wersję tego samego problemu
Wyobraź sobie, że sprawdzasz, ile plików znajduje się w folderze, który może zawierać kolejne foldery. Funkcja liczy pliki na bieżącym poziomie, a dla każdego podfolderu uruchamia tę samą operację. Właśnie na tym polega rekurencja: problem dzieli się na mniejsze przypadki o tej samej strukturze.
Każda poprawna funkcja rekurencyjna ma dwa elementy. Warunek bazowy zwraca wynik bez kolejnego wywołania, a krok rekurencyjny wywołuje funkcję dla prostszego argumentu. Jeśli krok nie przybliża do warunku bazowego, program może wywoływać się aż do wyczerpania stosu.
Przykład obliczania silni w Pythonie pokazuje ten układ:
def silnia(n):
if n <= 1: # warunek bazowy
return 1
return n * silnia(n - 1) # krok rekurencyjnyDla silnia(4) funkcja schodzi do silnia(1), a potem zwraca wyniki po kolei: 1, 2, 6, 24. Najpierw powstają wywołania, później wyniki wracają w odwrotnej kolejności - i to prowadzi do roli stosu.
Stos wywołań wyjaśnia, skąd bierze się błąd
Każde wywołanie funkcji musi zachować informacje potrzebne do późniejszego powrotu: między innymi argumenty i miejsce, w którym program ma kontynuować. Te dane trafiają na stos wywołań, strukturę działającą podobnie do stosu talerzy: najpierw kończy się to wywołanie, które uruchomiono jako ostatnie.
Przy folderach o niewielkiej głębokości nie stanowi to zwykle problemu. Jeśli jednak wejście jest bardzo długim łańcuchem zagnieżdżeń, liczba aktywnych wywołań rośnie. W Pythonie interpreter ogranicza głębokość stosu; dokumentacja modułu sys opisuje funkcje odczytu i zmiany tego limitu oraz ostrzega, że ustawienie go zbyt wysoko może zagrozić stabilności interpretera.
Podobny objaw w JavaScripcie to między innymi błąd „Maximum call stack size exceeded”. Dokumentacja MDN o zbyt głębokiej rekurencji wskazuje brak warunku bazowego i nadmierną liczbę wywołań jako typowe przyczyny. Nie zwiększaj limitu w ciemno: najpierw sprawdź, czy argument na pewno zmienia się w stronę zakończenia.
Gdy problem polega na prostym powtarzaniu operacji dla kolejnych elementów, pętla może być bezpieczniejsza. Przy strukturze rozgałęzionej rekurencja często czytelniej odwzorowuje sam problem.
Wybierz rekurencję dla struktury, a pętlę dla prostego liczenia
Dwie implementacje mogą dać ten sam wynik, ale różnić się czytelnością i zużyciem pamięci. Uważam, że rekurencja jest najbardziej przekonująca wtedy, gdy struktura danych sama układa się w podproblemy, jak drzewo katalogów albo węzły drzewa składniowego.
| Sytuacja | Co zwykle pasuje lepiej | Dlaczego |
|---|---|---|
| Przechodzenie po drzewie kategorii | Rekurencja | Każda kategoria może mieć podkategorie tego samego rodzaju. |
| Sumowanie elementów listy o znanej długości | Pętla | Nie trzeba utrzymywać osobnego wywołania dla każdego elementu. |
| Przeszukiwanie wielu możliwych układów, np. ruchów w grze | Rekurencja z kontrolą gałęzi | Każdy wybór prowadzi do kolejnych stanów; błędne ścieżki można cofać. |
| Przetwarzanie bardzo głębokiego, liniowego wejścia | Pętla albo jawny stos | Ogranicza ryzyko przepełnienia stosu wywołań. |
Przy przechodzeniu po drzewie rekurencyjna funkcja może obsłużyć bieżący węzeł, a potem wywołać się dla jego dzieci. Przy długiej liście takie podejście zwykle dodaje tylko zbędny stos. Jeśli struktura nie rozgałęzia się i da się ją opisać prostą pętlą, zacznij od pętli.
Naiwny Fibonacci pokazuje, że poprawny wynik może kosztować za dużo
Rekurencja może być logicznie poprawna, a mimo to wykonywać ogrom pracy. W klasycznej definicji Fibonacciego każda wartość powstaje z dwóch wcześniejszych, więc prosta funkcja rekurencyjna wielokrotnie oblicza te same liczby.
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)Dla fib(5) ta wersja wykonuje 15 wywołań funkcji łącznie, choć wiele z nich powtarza obliczenia dla tych samych argumentów. Zwiększając n, szybko tworzysz rozgałęziające się drzewo pracy. To dobry przykład, dlaczego sam warunek bazowy nie gwarantuje wydajnego algorytmu.
Można zapamiętywać już policzone wyniki, czyli zastosować memoizację, albo obliczać kolejne wartości w pętli. Dla Fibonacciego pętla jest prostym wyborem, bo wystarczy pamiętać dwie poprzednie liczby. Rekurencję zostawiłbym dla problemów, których struktura naturalnie rozgałęzia się, a nie dla samego efektu eleganckiego zapisu.
Przed uruchomieniem sprawdź trzy rzeczy
Gdy funkcja rekurencyjna nie działa, nie zaczynaj od przepisywania całego algorytmu. Najpierw przejdź po wywołaniach i sprawdź, co dzieje się z argumentem. Większość błędów w podstawowej rekurencji da się namierzyć, śledząc drogę do warunku bazowego.
- Brak zakończenia: czy istnieje przypadek, który zwraca wynik bez kolejnego wywołania?
- Brak postępu: czy argument w każdym kroku rzeczywiście zbliża się do tego przypadku?
- Nadmierna głębokość: czy wejście może tworzyć tak długi łańcuch, że stos nie pomieści wszystkich wywołań?
Przy debugowaniu wypisz argument funkcji przed wywołaniem rekurencyjnym. Jeśli kolejne wartości stoją w miejscu albo oddalają się od warunku bazowego, błąd jest w kroku rekurencyjnym, nie w samym mechanizmie. Rekurencja staje się zrozumiała, gdy potrafisz wskazać jej koniec i każdy krok prowadzący do tego końca.
