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 -

  1. Silnia w Pythonie
  2. Polecenia Spark Shell
  3. Najlepsze kompilatory C.
  4. Rodzaje algorytmów
  5. Program czynnikowy w JavaScript
  6. Przewodnik po liście poleceń powłoki Unix
  7. Rodzaje formularzy w reakcji z przykładami