Krótko mówiąc, rekurencja jest sposobem rozwiązania problemu poprzez wywołanie samej funkcji, słowo „ rekurencyjny ”Pochodzi od łacińskiego czasownika„ powtarzać się ”, Co oznacza powtórzenie czegoś. To właśnie robi funkcja rekurencyjna, powtarza to samo raz po raz, tj. Przywołuje samą siebie. W tym artykule dowiemy się o rekurencji w Pythonie. Poniżej znajdują się tematy poruszone na tym blogu:
- Co to jest rekursja w Pythonie?
- Warunek zakończenia
- Limit rekurencji w Pythonie
- Spłaszczanie list z rekurencją
- Zalety rekursji
- Wady rekursji
Co to jest rekursja w Pythonie?
Rekurencja to proces określania czegoś na podstawie samej siebie. Wiemy, że w Pythonie każda funkcja może wywołać każdą inną funkcję, funkcja może również wywołać samą siebie. Te typy funkcji, które wywołują siebie, dopóki określony warunek nie zostanie spełniony, nazywane są funkcjami rekurencyjnymi.
weźmy kilka przykładów, aby zobaczyć, jak to działa. Jeśli dana jest dodatnia liczba całkowita n, silnia będzie.
- n! = n * (n-1) * (n-2) i tak dalej.
- 2! = 2 * (2-1)
- jeden! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Zastąpienie powyższych wartości spowoduje powstanie następującego wyrażenia
- 4! = 4 * 3 * 2 * 1
Musimy zdefiniować funkcję, powiedzmy fakt (n), który przyjmuje dodatnią liczbę całkowitą lub 0 jako swój parametr i zwraca n-tą silnię, jak możemy to zrobić za pomocą rekurencji?
Zobaczmy, aby to zrobić za pomocą rekurencji, musimy zbadać następujące równanie
n! = n. (n-1). (n-2) & hellip3.2.1
n! = n. (n-1)! # możemy przepisać powyższą instrukcję jak w tej linii
Teraz, jeśli jako parametr podamy 2, otrzymamy:
2! = 2,1! = 2
Podobnie, jeśli zdamy 1, otrzymamy:
parsowanie plików xml w java
jeden! = 1,0! = 1
Ale jeśli przekroczymy 0, zepsuje się
0! = 0, (- 1)! i tutaj silnia dla -1 nie jest zdefiniowana, więc działa tylko dla wartości> 0
Musimy więc napisać dwie sprawy
1. n! = n. (n-1)! jeśli n> = 1
2. 1, jeśli n = 0
To jest kompletne rozwiązanie dla wszystkich dodatnich liczb całkowitych i 0.
r uczenie maszynowe na przykładzie
Warunek zakończenia
Funkcja rekurencyjna musi spełnić ważny warunek, aby się zakończyć. Przechodząc do stanu, w którym problem można rozwiązać bez dalszej rekursji, funkcja rekurencyjna zostanie zakończona, minimalizując problem do mniejszych podetapów. Rekursja może zakończyć się nieskończoną pętlą, jeśli warunek zakończenia nie zostanie spełniony w wywołaniach.
Warunki czynnikowe:
- silnia n = n * (n-1) tak długo, jak n jest większe niż 1.
- 1, jeśli n = 0
Zamienimy powyższe warunki silni w kodzie Pythona:
def fakt (n): jeśli n == 1: return n else: return n * fakt (n-1)
Weźmy przykład, powiedzmy, że chcemy znaleźć silnię 4:
fakt (4) # zwróci 4 * fakt (3) i tak dalej, aż n == 1.
Wynik: 24
Ze względu na swoją prostotę i przejrzystość jest często używany jako przykład rekurencji. Rozwiązywanie mniejszych przypadków problemu na każdym etapie, który określa się jako rekursję w informatyce.
Limit rekurencji w Pythonie
W niektórych językach można utworzyć nieskończoną pętlę rekurencyjną, ale w Pythonie istnieje limit rekursji. Aby sprawdzić limit, uruchom następującą funkcję z modułu sys. co da limit rekursji ustawiony dla Pythona.
import sys sys.getrecursionlimit ()
Wynik: 1000
Możesz także zmienić limit za pomocą funkcji functionsetrecursionlimit () modułu sys zgodnie z wymaganiami. Teraz stwórzmy funkcję, która wywołuje się rekurencyjnie, dopóki nie przekroczy limitu i sprawdzi, co się stanie:
def recursive (): recursive () if __name__ == '__main__': recursive ()
Jeśli uruchomisz powyższy kod, otrzymasz wyjątek czasu wykonania: RuntimeError: przekroczono maksymalną głębokość rekursji. Python zapobiega tworzeniu funkcji, która kończy się w niekończącej się pętli cyklicznej.
Spłaszczanie list z rekurencją
Inne rzeczy, które możesz zrobić za pomocą rekurencji, z wyjątkiem silni, powiedzmy, że chcesz utworzyć singiel z listy, która jest zagnieżdżona, można to zrobić za pomocą poniższego kodu:
def flatten (a_list, flat_list = none): if flat_list is none: flat_list = [] for item in a_list: if isinstance (item, list): flatten (item, flat_list) else: flat_list.append (item) return flat_list if __name__ == '__main__': zagnieżdżone = [1,2,3, [4,5], 6] x = spłaszcz (zagnieżdżone) print (x)
Wynik: [1, 2, 3, 4, 5, 6]
Uruchomienie powyższego kodu spowoduje wyświetlenie pojedynczej listy zamiast listy liczb całkowitych zawierającej listę liczb całkowitych, której użyliśmy jako dane wejściowe. Możesz również zrobić to samo, używając również innych sposobów, Python ma coś, co nazywa się itertools.chain () możesz sprawdzić kod użyty do utworzenia łańcucha funkcji () jest to inne podejście do zrobienia tego samego co my.
Zalety rekursji
Kod jest czysty i elegancki w funkcji rekurencyjnej.
Zadanie złożone można podzielić na prostsze podproblemy za pomocą rekurencji.
Generowanie sekwencji jest łatwiejsze z rekurencją niż przy użyciu zagnieżdżonej iteracji.
co jest * w sql
Wady rekursji
Postępowanie zgodnie z logiką funkcji rekurencyjnej może być czasami trudne.
Połączenia rekurencyjne są drogie (nieefektywne), ponieważ zajmują dużo pamięci i czasu.
Funkcje rekurencyjne są trudne do debugowania.
W tym artykule widzieliśmy, czym jest rekurencja i jak możemy opracować funkcje rekurencyjne na podstawie stwierdzenia problemu, jak matematycznie można zdefiniować stwierdzenie problemu. Rozwiązaliśmy problem silni i znaleźliśmy warunki wymagane do znalezienia silni, z których byliśmy w stanie przekształcić te warunki w kod Pythona, dzięki czemu można zrozumieć, jak działa rekurencja. Myślę, że to fajne, że Python ma wbudowany limit rekursji, aby uniemożliwić programistom tworzenie źle skonstruowanych funkcji rekurencyjnych. Należy zauważyć, że rekurencja jest trudna do debugowania, ponieważ funkcja ciągle wywołuje samą siebie.