W tym samouczku nauczysz się tworzyć funkcję rekurencyjną (wywołującą samą siebie).
Co to jest rekurencja?
Rekurencja to proces definiowania czegoś w kategoriach siebie.
Przykładem świata fizycznego byłoby ustawienie dwóch równoległych luster naprzeciw siebie. Każdy obiekt pomiędzy nimi zostałby odzwierciedlony rekurencyjnie.
Funkcja rekurencyjna w Pythonie
W Pythonie wiemy, że funkcja może wywoływać inne funkcje. Funkcja może nawet wywołać samą siebie. Te typy konstrukcji nazywane są funkcjami rekurencyjnymi.
Poniższy obraz przedstawia działanie funkcji rekurencyjnej o nazwie recurse.
Funkcja rekurencyjna w Pythonie
Poniżej znajduje się przykład funkcji rekurencyjnej służącej do znajdowania silni liczby całkowitej.
Silnia liczby jest iloczynem wszystkich liczb całkowitych od 1 do tej liczby. Na przykład silnia 6 (oznaczona jako 6!) To 1 * 2 * 3 * 4 * 5 * 6 = 720.
Przykład funkcji rekurencyjnej
def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))
Wynik
Silnia 3 to 6
W powyższym przykładzie factorial()jest funkcją rekurencyjną, jak sama siebie nazywa.
Kiedy wywołujemy tę funkcję dodatnią liczbą całkowitą, będzie ona rekurencyjnie wywoływać samą siebie, zmniejszając liczbę.
Każda funkcja mnoży liczbę przez silnię liczby znajdującej się poniżej, aż będzie równa jeden. To rekurencyjne wywołanie można wyjaśnić w następujących krokach.
silnia (3) # pierwsze wezwanie z 3 3 * silnia (2) # drugie wezwanie z 2 3 * 2 * silnia (1) # trzecie wezwanie z 1 3 * 2 * 1 # powrót z trzeciego wezwania jako numer = 1 3 * 2 # powrót z drugiego wezwania 6 # powrót z pierwszego wezwania
Spójrzmy na obraz, który pokazuje krok po kroku proces tego, co się dzieje:
Działanie rekurencyjnej funkcji silni
Nasza rekursja kończy się, gdy liczba zmniejszy się do 1. Nazywa się to warunkiem podstawowym.
Każda funkcja rekurencyjna musi mieć warunek podstawowy, który zatrzymuje rekursję, w przeciwnym razie funkcja wywołuje samą siebie w nieskończoność.
Interpreter Pythona ogranicza głębokość rekurencji, aby uniknąć nieskończonych rekurencji, co skutkuje przepełnieniem stosu.
Domyślnie maksymalna głębokość rekursji wynosi 1000. Przekroczenie limitu skutkuje RecursionError. Spójrzmy na jeden z takich warunków.
def recursor(): recursor() recursor()
Wynik
Traceback (ostatnie połączenie): Plik „”, wiersz 3, w pliku „”, wiersz 2, w pliku „”, wiersz 2, w pliku „”, wiersz 2, w a (Poprzednia linia powtórzona jeszcze 996 razy ) RecursionError: przekroczono maksymalną głębokość rekursji
Zalety rekursji
- Funkcje rekurencyjne sprawiają, że kod wygląda czysto i elegancko.
- Złożone zadanie można podzielić na prostsze podproblemy za pomocą rekurencji.
- Generowanie sekwencji jest łatwiejsze z rekurencją niż przy użyciu zagnieżdżonej iteracji.
Wady rekursji
- Czasami logika stojąca za rekurencją jest trudna do zrozumienia.
- Połączenia rekurencyjne są drogie (nieefektywne), ponieważ zajmują dużo pamięci i czasu.
- Funkcje rekurencyjne są trudne do debugowania.
