Widzieliśmy, że funkcje umożliwiają organizowanie i ponowne wykorzystanie części naszego kodu. Widzieliśmy również, że funkcję można zdefiniować za pomocą innych funkcji. W tej lekcji dowiadujemy się, że funkcja może być zdefiniowana przez samą siebie! To bardzo użyteczne podejście nosi nazwę rekurencji (rekursji). Legenda głosi, że "aby zrozumieć rekurencję, musisz najpierw zrozumieć rekurencję".
Przykład
W naszej lekcji na pętlach użyliśmy pętli while, aby utworzyć następujące wyjście.
5 4 3 2 1 Blastoff!Oto program, który używa rekurencji do osiągnięcia tego samego efektu.
Dodamy dodatkowe wydruki, aby zrozumieć, jak program działa. Ta wersja programu odczytuje również liczbę, od której ma sie rozpocząć liczenie.
Jeśli chcesz wypróbować inne wartości wejściowe, skorzystaj w powyższym programie z opcji Wprowadź dane. Wypróbuj najpierw 0 i zobaczyć, co się dzieje, a następnie 1.
Gdy na wejściu mamy 5, program najpierw wywołuje kopię funkcji countdown dla n=5, która drukuje 5 i wywołuje countdown(4). To trwa aż do countdown(0), kiedy to drukuje "Blastoff!" I nie wywołuje więcej countdown. Gdy Python dla n=0 kończy wywoływanie funkcji countdown, Python powraca do funkcji, która go wywołała, co oznacza, że teraz n=1 dla funkcji countdown. Potem wrócimy do wywołania n=2, i tak dalej.
Aby staranniej sprawdzić nasze rozumowanie, możesz także w wizualizerze prześledzić rekurencyjny kod:
Ten „twist” sprawia, że rekurencja jest wyjątkową wśród funkcji, które widzieliśmy wcześniej, wiele wersji tej funkcji działa jednocześnie. Oznacza to, że jest więcej niż jedna ramka odpowiadająca tej samej funkcji (w wizualizerze). Jest to dość podobne do tego, co widzieliśmy w wizualizerze, gdzie jedna funkcja wywoływała drugą, z tą róznicą, że tu, funkcja wywołująca jest taka sama jak funkcja wywołana. Trzeba jednak pamiętać, że na każdym kroku są używane tak naprawdę tylko zmienne "bieżące" (najnowsza / najniższa ramka) – ramki, które nie są dolne są "wstrzymane" a ich zmienne niedostępne.
Teraz twoja kolej, by napisać kod. Zmodyfikuj funkcję countdown tak, aby liczyła w górę zamiast w dół.
Następnie zmieńmy nasz program countdown tak, aby liczył w krokach co 2. Na wyjściu powinniśmy otrzymać 5, 3, 1, Blastoff! Zmienimy argument funkcji z n-1 na n-2. Czy coś jeszcze musimy zmienić?
Można zauważyć, że ten program nie działa zgodnie z naszymi oczekiwaniami. Drukował 5, 3, 1, tak jak chcemy, ale zamiast tego zatrzymywał się na -1, -3, -5 i dalej biegł w nieskończoność. (A bardziej dokładniej, zabraknie czasu i pamięci, ponieważ każde wywołanie rekurencyjne zajmuje trochę więcej pamięci roboczej, zobacz ten sam przykład w wizualizerze).
Podczas projektowania funkcji rekurencyjnej musimy być ostrożni, aby jej kolejne wywołania nie trwały w nieskończoność! Zmodyfikuj program countdownBy2 tak, aby prawidłowo zatrzymał się na 1 (lub 2, jeśli n jest parzyste) i wydrukował "Blastoff!".
Projektowanie Funkcji Rekurencyjnych
Funkcja rekurencyjna oznacza funkcję, która wywołuje samą siebie. Ale musi istnieć kilka przypadków, kiedy funkcja nie wywołuje samej siebie, bo inaczej, program by działał w nieskończoność, jak widzieliśmy powyżej. Przypadek bazowy stanowi część funkcji rekurencyjnej, w której nie ma wywoływania samej siebie. W powyższym przykładzie dla n<=0 mieliśmy przypadek bazowy. Projektowanie funkcji rekurencyjnej wymaga starannego wybrania przypadku bazowego i upewnienia się, że każda sekwencja wywołań funkcji ostatecznie dotrze do przypadku bazowego.
W następnym ćwiczeniu został już zaprogramowany przypadek bazowy, a twoim zadaniem jest zapisać resztę funkcji rekurencyjnej.
Teraz zapisz funkcję rekurencyjną, która wywołuje digitalSum jako podprogram.
Ten niezwykle krótki program oblicza największy wspólny dzielnik dwóch liczb. To jeden z najstarszych znanych algorytmów zwany algorytmem Euklidesa .
Ćwiczenia
def gcd(a, b):
if b == 0: return a
return gcd(b, a % b)
print(gcd(20, 12))
Matematycy uważają, że każda sekwencja gradowa osiąga ostatecznie 1, niezależnie od tego, od jakiej wartości n zaczniemy. Jednak nikt tego jeszcze nie udowodnił.
Listy Zagnieżdżone
Oto interesujące naturalne zastosowanie rekursji. Zagnieżdżona lista to miejsce, w którym można umieścić kilka list wewnątrz innych; możliwe jest zrobienie tego wielokrotnie. Na przykład, zagnieżdżona lista liczb całkowitych to [[1, 2], [9, 10]], jak również [[1], 2] i x = [[1], 2, [3, [[4]]]]. Ostatni przykład listy zagnieżdżonej to lista trzech elementów: x[0]==[1], aby rozpocząć, a następnie x[1]==2, a następnie x[2]==[3, [[4]]]. (Więc x, postrzegane jako lista o długości 3). Zauważ, że lista jak [1, 2, 3] również liczy się jako zagnieżdżona lista. Czy możemy napisać funkcję, aby znaleźć całkowitą sumę wszystkich zagnieżdżonych list liczb całkowitych? Na przykład, przy wejściu [[5], 2, [10, 8, [[7]]]] należałoby oczekiwać wartości 32.
To zadanie jest trudne dla pętli while lub pętli for, ponieważ chcemy, aby funkcja, która działa na zagnieżdżonych listach z dowolnym kształtem/formatem. Jednak zagnieżdżone listy mają naturalnie rekurencyjną strukturę: lista zagnieżdżona jest listą, z której każdy element jest albo (a) liczbą całkowitą, albo (b) listą zagnieżdżoną. Gdy obliczymy sumę każdej części głównej listy, suma tych wartości będzie sumą całkowitą. Możemy to wyrazić następującym kodem; używając isinstance(x, int), która daje wartość typu boolowskiego informując, czy x jest typu całkowitego (w przeciwieństwie do listy).
Rekursja służy do podziału każdej zagnieżdżonej listy na mniejsze części. Na przykład, nestedListSum([1, [3, 4], 5]) wykonuje łącznie 6 wywołań rekurencyjnych: początkowe, potem dla 1, a następnie dla [3, 4], a następnie dla 3, potem dla 4, (przy czym suma [3, 4] jest zwracana jako 7), a na końcu dla 5 (po tym otrzymano łącznie 13). Oto ten sam kod w wizualizerze.
Linijki
Rekursja jest również związana z fraktalami - obrazy zawierające wiele kopii siebie. Przykładem jest banner na górze tej strony. Następujące ćwiczenie tworzy prosty powtarzający się wzór, który używa rekursji.
Gratulacje! Jesteś gotowy, aby przejść do następnej lekcji.