Rekurencja
Ostatnia aktualizacja
Rekurencja to funkcja, która wywołuje samą siebie dla mniejszej wersji tego samego problemu, aż dojdzie do przypadku tak małego, że można na niego odpowiedzieć od razu. Ten przypadek to przypadek bazowy i potrzebuje go każda funkcja rekurencyjna: fib(n) dzieli się na fib(n - 1) i fib(n - 2), aż trafi na fib(1) lub fib(0), które po prostu zwracają same siebie. Wizualizacja powyżej uruchamia dokładnie to: kliknij Odtwórz i zobacz, jak wywołania rozgałęziają się w drzewo, docierają do przypadków bazowych w liściach, a potem zwracają swoje wartości w górę, łącząc je na każdym poziomie.
Druga rzecz, którą pokazuje animacja, to stos wywołań: każde wywołanie, które się rozpoczęło, ale jeszcze nie zwróciło wyniku. Stos rośnie, gdy wywołania schodzą głębiej, osiąga szczyt na głębokości rekurencji i zwija się, gdy wracają wyniki. Dlatego głęboka rekurencja może doprowadzić do przepełnienia stosu, a pętla iteracyjna nigdy nie powiększa stosu. Ten sam kształt wywołań napędza przeszukiwanie w głąb, merge sort i większość operacji na drzewie binarnym.
Złożoność czasowa i pamięciowa
Dla naiwnego rekurencyjnego Fibonacciego pokazanego powyżej oraz dwóch standardowych poprawek:
| Podejście | Czas | Pamięć | Uwagi |
|---|---|---|---|
| Naiwna rekurencja | O(2^n) | O(n) | Drzewo wywołań podwaja się na każdym poziomie; pamięć to najgłębszy stos, a nie całe drzewo. |
| Ze spamiętywaniem | O(n) | O(n) | Każde fib(k) jest obliczane raz i zapamiętywane; powtarzające się poddrzewa zamieniają się w odczyty. |
| Pętla iteracyjna | O(n) | O(1) | Dwie przesuwane zmienne całkowicie zastępują stos. |
| Dowolna rekurencja, ogólnie | wywołania × praca na wywołanie | O(max depth) | Stos przechowuje jedną ramkę na każde wywołanie, które się rozpoczęło, ale nie zwróciło wyniku. |
Krok po kroku
| Krok | Co się dzieje |
|---|---|
| 1 | Pierwsze wywołanie fib(n) trafia na stos wywołań. |
| 2 | Potrzebuje fib(n - 1), więc to wywołanie też trafia na stos; rodzic czeka. |
| 3 | Wywołania zagnieżdżają się, aż któreś zapyta o n <= 1: przypadek bazowy odpowiada od razu, bez głębszego wywołania. |
| 4 | Wartość przypadku bazowego wraca do rodzica, który może teraz rozpocząć drugie wywołanie, fib(n - 2). |
| 5 | Gdy oboje dzieci zwrócą wynik, rodzic je dodaje i też zwraca wynik; jego ramka opuszcza stos. |
| 6 | Zwracanie powtarza się w górę drzewa, aż ramka pierwszego wywołania zostanie zdjęta z ostatecznym wynikiem, a stos będzie pusty. |
Przykład krok po kroku
Obliczanie fib(4) w dokładnej kolejności wywołań, tak jak odtwarza je animacja:
| Wywołanie | Stos w tej chwili | Zwraca |
|---|---|---|
fib(4) | fib(4) | czeka na dzieci |
fib(3) | fib(4) > fib(3) | czeka na dzieci |
fib(2) | fib(4) > fib(3) > fib(2) | czeka na dzieci |
fib(1) | fib(4) > fib(3) > fib(2) > fib(1) | 1 (przypadek bazowy) |
fib(0) | fib(4) > fib(3) > fib(2) > fib(0) | 0 (przypadek bazowy) |
fib(2) łączy wyniki | fib(4) > fib(3) > fib(2) | 1 + 0 = 1 |
fib(1) | fib(4) > fib(3) > fib(1) | 1 (przypadek bazowy) |
fib(3) łączy wyniki | fib(4) > fib(3) | 1 + 1 = 2 |
fib(2) ponownie | fib(4) > fib(2) | 1, obliczone od zera |
fib(4) łączy wyniki | fib(4) | 2 + 1 = 3 |
Kiedy używać rekurencji
| Używaj, gdy | Unikaj, gdy |
|---|---|
| Problem jest samopodobny: drzewa, struktury zagnieżdżone, dziel i zwyciężaj | Prosta pętla wyraża to samo bez ramek stosu |
Głębokość jest ograniczona i umiarkowana, jak O(log n) w merge sort | Głębokość może osiągnąć rozmiar danych przy ogromnych wejściach, co grozi przepełnieniem stosu |
| Backtracking potrzebuje stosu, aby pamiętać, gdzie wznowić | Te same podproblemy się powtarzają, a ich nie zapamiętujesz |
| Wersja rekurencyjna jest wyraźnie łatwiejsza do czytania i weryfikacji | Jesteś w gorącej pętli, w której narzut wywołań ma mierzalne znaczenie |
Recursion: kod
Przejrzysta, gotowa do uruchomienia implementacja algorytmu Recursion w językach: Python, JavaScript, Java, C++, C. Wybierz język, skopiuj kod albo otwórz go od razu w edytorze online Coddy.
Recursion: kod (Python)
Python
1calls = 02
3def fib(n, depth=0):4 global calls5 calls += 16 # Print the call with its depth so the recursion is visible7 print(" " * depth + f"fib({n})")8 if n <= 1:9 return n10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)11
12
13print("fib(5) =", fib(5))14print("calls made:", calls)Recursion: kod (JavaScript)
JavaScript
1let calls = 0;2
3function fib(n, depth = 0) {4 calls += 1;5 // Print the call with its depth so the recursion is visible6 console.log(' '.repeat(depth) + `fib(${n})`);7 if (n <= 1) return n;8 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);9}10
11console.log('fib(5) =', fib(5));12console.log('calls made:', calls);Recursion: kod (Java)
Java
1public class Main {2 static int calls = 0;3
4 static int fib(int n, int depth) {5 calls++;6 // Print the call with its depth so the recursion is visible7 System.out.println(" ".repeat(depth) + "fib(" + n + ")");8 if (n <= 1) return n;9 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);10 }11
12 public static void main(String[] args) {13 System.out.println("fib(5) = " + fib(5, 0));14 System.out.println("calls made: " + calls);15 }16}Recursion: kod (C++)
C++
1#include <iostream>2#include <string>3
4int calls = 0;5
6int fib(int n, int depth) {7 calls++;8 // Print the call with its depth so the recursion is visible9 std::cout << std::string(depth * 2, ' ') << "fib(" << n << ")\n";10 if (n <= 1) return n;11 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);12}13
14int main() {15 int result = fib(5, 0);16 std::cout << "fib(5) = " << result << "\n";17 std::cout << "calls made: " << calls << "\n";18 return 0;19}Recursion: kod (C)
C
1#include <stdio.h>2
3int calls = 0;4
5int fib(int n, int depth) {6 calls++;7 /* Print the call with its depth so the recursion is visible */8 printf("%*sfib(%d)\n", depth * 2, "", n);9 if (n <= 1) return n;10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);11}12
13int main(void) {14 printf("fib(5) = %d\n", fib(5, 0));15 printf("calls made: %d\n", calls);16 return 0;17}Rekurencja: najczęstsze pytania
Czym jest przypadek bazowy w rekurencji?
To dane wejściowe na tyle małe, że można na nie odpowiedzieć bez kolejnego wywołania rekurencyjnego. Dla
fib(n) jest to n <= 1, które bezpośrednio zwraca n. Bez osiągalnego przypadku bazowego wywołania nigdy się nie kończą, stos ciągle rośnie, a program kończy się błędem przepełnienia stosu.Czym jest stos wywołań i dlaczego ma znaczenie?
Środowisko uruchomieniowe przechowuje jedną ramkę na każde wywołanie, które się rozpoczęło, ale jeszcze nie zwróciło wyniku, razem z jego argumentami i zmiennymi lokalnymi. Głębokość rekurencji równa się wysokości stosu, więc rekurencja schodząca na
n poziomów zużywa O(n) pamięci, nawet jeśli każde wywołanie wykonuje prawie żadnej pracy. Rząd etykiet pod animacją pokazuje dokładnie ten stos, gdy rośnie i się zwija.Dlaczego rekurencyjny Fibonacci działa w czasie wykładniczym?
Bo te same podproblemy są obliczane w kółko: w przykładzie powyżej
fib(2) jest obliczane dwa razy wewnątrz fib(4), a powielanie mniej więcej podwaja się na każdym poziomie, co daje O(2^n) wywołań. Zapamiętanie każdego wyniku przy pierwszym obliczeniu, czyli spamiętywanie (memoizacja), zwija drzewo do O(n).Czy rekurencja jest lepsza od iteracji?
Żadna nie jest lepsza w każdej sytuacji. Każdą rekurencję można przepisać jako pętlę z jawnym stosem, a każdą pętlę jako rekurencję. Rekurencja wygrywa czytelnością przy problemach samopodobnych, takich jak przechodzenie drzewa czy przeszukiwanie w głąb; iteracja wygrywa pamięcią i narzutem wywołań przy przebiegach liniowych.
Co powoduje przepełnienie stosu w funkcji rekurencyjnej?
Albo brakujący lub nieosiągalny przypadek bazowy, przez co wywołania nigdy się nie kończą, albo poprawna rekurencja, której głębokość jest po prostu za duża dla limitu stosu środowiska, na przykład jedno wywołanie rekurencyjne na element przy milionach elementów. Rozwiązaniem jest zagwarantowanie przypadku bazowego, ograniczenie głębokości lub zamiana na iterację.
Które algorytmy są naturalnie rekurencyjne?
Algorytmy sortowania typu dziel i zwyciężaj, takie jak merge sort i quicksort, przechodzenie drzewa binarnego i grafów, wyszukiwanie binarne, łamigłówki z backtrackingiem, takie jak problem N hetmanów, oraz wszystko, co jest zdefiniowane na strukturze zagnieżdżonej, na przykład JSON czy system plików.
Powiązane materiały
Więcej wizualizacji
