Co to jest funkcja rekurencyjna?
Funkcja wywołuje się wielokrotnie, aż spełni warunek rekurencyjny. Funkcja rekurencji dzieli problem na mniejsze problemy i wywołuje własną logikę, aby rozwiązać mniejszy problem. Ta technika jest znana jako dziel i podbij. Jest stosowany w matematyce i informatyce.
Funkcja rekurencyjna obejmuje przypadek podstawowy (lub przypadkowy) i przypadek rekurencyjny. W przypadku podstawowym można rozważyć główny problem do rozwiązania, a przypadek rekurencyjny dzieli problem na mniejsze części, aż osiągnie poziom, na którym można go łatwo rozwiązać. Przypadek rekurencyjny może zwrócić wynik lub może się ponownie wywołać w celu dalszego podziału problemu. Za każdym razem, gdy problem rozkłada się na mniejszy, funkcja wywoływana rekurencyjnie zapisuje stan wywołania i spodziewa się wyniku po jego rozwiązaniu.
Funkcja rekurencyjna w Pythonie
Pojęcie rekurencji pozostaje takie samo w Pythonie. Ta funkcja wywołuje podział problemu na mniejsze. Najprostszym przykładem rekurencji byłoby znalezienie silni liczby.
Powiedzmy, że musimy znaleźć silnię liczby 5 => 5! (Nasz problem)
Aby znaleźć 5! problem można podzielić na mniejsze 5! => 5 x 4!
Tak, aby zdobyć 5! Musimy znaleźć 4! i pomnóż to przez 5.
Podzielmy problem dalej
5! = 4! x 5
4! = 3! x 4
3! = 3 x 2!
2! = 2 x 1!
1! = 1
Kiedy osiągnie najmniejszą porcję, tzn. Otrzymując silnię 1, możemy zwrócić wynik jako
Weźmy przykład pseudokodu: -
Algorytm dla silni
Zobaczmy algorytm silni:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Wywołania funkcji
Załóżmy, że znajdujemy silnię 5.
get_factorial(5) 5 * get_factorial(4) = returns 120 #1st call
get_factorial(4) 4 * get_factorial(3) = returns 24 #2nd call
get_factorial(3) 3 * get_factorial(2) = returns 6 #3rd call
get_factorial(2) 2 * get_factorial(1) = returns 2 #4th call
get_factorial(1) returns 1 #5th call
Wynik końcowy wyniesie 120, gdy rozpoczęliśmy wykonywanie funkcji. Nasza funkcja rekurencji zatrzyma się, gdy liczba zostanie tak zmniejszona, że można uzyskać wynik.
- Pierwsze wywołanie, które otrzyma silnię 5, spowoduje rekurencję, w której zostanie dodane do stosu, a kolejne wywołanie zostanie wykonane po zmniejszeniu liczby do 4.
- Ta rekurencja będzie nadal wywoływać i rozbijać problem na mniejsze części, dopóki nie osiągnie stanu podstawowego.
- Podstawowym warunkiem jest tutaj, gdy liczba wynosi 1.
- Każda funkcja rekurencyjna ma swój własny warunek rekurencyjny i warunek podstawowy.
Plusy i minusy funkcji rekurencyjnej Pythona
- Wykonanie rekurencji jest takie, że nie wykona żadnych obliczeń, dopóki nie osiągnie stanu podstawowego.
- Po osiągnięciu warunków podstawowych może zabraknąć pamięci.
- W dużym problemie, w którym może być milion kroków lub możemy powiedzieć, że milion rekurencji, program może spowodować błąd pamięci lub błąd segmentacji.
- 1000000! = 1000000 * 999999! =?
- Rekurencja jest inna niż iteracja, nie skaluje się jak metoda iteracyjna.
- Różne języki mają różne optymalizacje rekurencji.
- W wielu językach metoda iteracyjna działałaby lepiej niż rekurencja.
- Każdy język ma pewne ograniczenia dotyczące głębokości rekurencji, które możesz napotkać podczas rozwiązywania dużych problemów.
- Czasami trudno jest zrozumieć złożone problemy z rekurencją, podczas gdy iteracja jest dość prosta.
Niektóre zalety
- W niektórych przypadkach rekurencja jest wygodnym i szybszym sposobem użycia.
- Bardzo przydatny w przemierzaniu drzewa i wyszukiwaniu binarnym.
Kod Python - Rekurencja a iteracja
Zrozumieliśmy, czym jest rekurencja i jak działa ona w Pythonie, ponieważ wiemy, że wszystkie języki mają różne implementacje rekurencji dla optymalizacji pamięci i obliczeń. Może zaistnieć przypadek, w którym iteracja byłaby szybsza niż rekurencja.
W tym przypadku porównamy zarówno metodę rekurencji, jak i iteracji, aby zobaczyć, jak radzi sobie Python w obu przypadkach.
1. Kod rekurencyjny dla silni
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2: #base condition
return 1
else:
return n * get_recursive_factorial(n -1) #recursion condition
2. Problem czynnikowy przy użyciu iteracji (zapętlanie)
def get_iterative_factorial(n):
if n < 0:
return -1
else:
fact = 1
for i in range( 1, n+1 ):
fact *= i
return fact
3. Drukowanie wyników
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
Wynik:
Jak widzimy, oba dają takie same wyniki, jak napisaliśmy tę samą logikę. Tutaj nie widzimy żadnej różnicy w wykonaniu.
Dodajmy kod czasu, aby uzyskać więcej informacji o wykonywaniu rekurencji i iteracji w Pythonie.
Zaimportujemy bibliotekę „time” i sprawdzimy, ile czasu zajmuje rekurencja i iteracja, aby zwrócić wynik.
4. Kod z obliczaniem czasu
import time
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2:
return 1
else:
return n * get_recursive_factorial(n-1)
def get_iterative_factorial(n):
if n < 0 :
return -1
else:
fact = 1
for i in range(1, n+1):
fact *= i
return fact
start_time = time.time()
get_recursive_factorial(100)
print("Recursion--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
get_iterative_factorial(100)
print("Iteration--- %s seconds ---" % (time.time() - start_time))
Wykonamy powtarzające się wykonania z inną wartością dla silni i zobaczymy wyniki. Poniższe wyniki mogą się różnić w zależności od maszyny. Użyliśmy MacBooka Pro 16 GB RAM i7.
Do wykonania używamy Pythona 3.7
Przypadek 1: - Współczynnik 6:
Przypadek 2: Współczynnik 50:
Przypadek 3: Współczynnik 100:
Przypadek 4: Współczynnik 500:
Przypadek 5: Współczynnik 1000:
Przeanalizowaliśmy obie metody w innym problemie. Ponadto oba wypadły podobnie, z wyjątkiem przypadku 4.
W przypadku 5 wystąpił błąd podczas robienia tego z rekurencją.
Python otrzymał ograniczenie maksymalnej głębokości, z jaką można przejść z rekurencją, ale ten sam problem udało mi się rozwiązać za pomocą iteracji.
Python ma ograniczenia dotyczące problemu przepełnienia. Python nie jest zoptymalizowany pod kątem rekurencji ogona, a niekontrolowana rekurencja powoduje przepełnienie stosu.
Funkcja „sys.getrecursionlimit ()” określa limit rekurencji.
Limit rekurencji można zmienić, ale nie jest zalecany, może być niebezpieczny.
Wniosek - funkcja rekurencyjna Pythona
- Rekurencja jest przydatnym rozwiązaniem niektórych problemów, takich jak przechodzenie przez drzewa i inne problemy.
- Python nie jest funkcjonalnym językiem programowania i widzimy, że stos rekurencji nie jest tak zoptymalizowany w porównaniu do iteracji.
- Powinniśmy używać iteracji w naszym algorytmie, ponieważ jest ona bardziej zoptymalizowana w Pythonie i zapewnia lepszą prędkość.
Polecane artykuły
Jest to przewodnik po funkcji rekurencyjnej w Pythonie. Tutaj omawiamy, czym jest funkcja rekurencyjna, funkcja rekurencyjna w Pythonie, algorytm dla silni itp. Możesz także przejrzeć nasze inne sugerowane artykuły, aby dowiedzieć się więcej -
- Silnia w Pythonie
- Polecenia Spark Shell
- Najlepsze kompilatory C.
- Rodzaje algorytmów
- Program czynnikowy w JavaScript
- Przewodnik po liście poleceń powłoki Unix
- Rodzaje formularzy w reakcji z przykładami