Python Language
Rekurencja
Szukaj…
Uwagi
Rekurencja wymaga warunku zatrzymania stopCondition , aby wyjść z rekurencji.
Oryginalna zmienna musi zostać przekazana do funkcji rekurencyjnej, aby została zapisana.
Suma liczb od 1 do n
Gdybym chciał znaleźć sumę liczb od 1 do n gdzie n jest liczbą naturalną, mogę zrobić 1 + 2 + 3 + 4 + ... + (several hours later) + n . Alternatywnie, mógłbym napisać pętlę for :
n = 0
for i in range (1, n+1):
n += i
Lub mógłbym użyć techniki znanej jako rekurencja:
def recursion(n):
if n == 1:
return 1
return n + recursion(n - 1)
Rekurencja ma zalety w stosunku do powyższych dwóch metod. Rekurencja zajmuje mniej czasu niż wypisanie 1 + 2 + 3 dla sumy od 1 do 3. W przypadku recursion(4) rekurencja może być wykorzystana do pracy wstecz:
Wywołania funkcji: (4 -> 4 + 3 -> 4 + 3 + 2 -> 4 + 3 + 2 + 1 -> 10)
Podczas gdy pętla for działa ściśle do przodu: (1 -> 1 + 2 -> 1 + 2 + 3 -> 1 + 2 + 3 + 4 -> 10). Czasami rozwiązanie rekurencyjne jest prostsze niż rozwiązanie iteracyjne. Jest to widoczne przy wdrażaniu odwrócenia połączonej listy.
Co, jak i kiedy rekurencji
Rekurencja występuje, gdy wywołanie funkcji powoduje ponowne wywołanie tej samej funkcji przed zakończeniem pierwotnego wywołania funkcji. Rozważmy na przykład dobrze znane wyrażenie matematyczne x! (tzn. operacja silnia). Operacja silnia jest zdefiniowana dla wszystkich nieujemnych liczb całkowitych w następujący sposób:
- Jeśli liczba wynosi 0, odpowiedź brzmi 1.
- W przeciwnym razie odpowiedzią jest liczba razy silnia o jeden mniejsza od tej liczby.
W Pythonie naiwną implementację operacji silni można zdefiniować jako funkcję w następujący sposób:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
Funkcje rekurencyjne mogą czasami być trudne do zrozumienia, więc przejrzyjmy ten krok po kroku. Rozważ wyrażenie factorial(3) . To i wszystkie wywołania funkcji tworzą nowe środowisko . Środowisko jest w zasadzie tylko tabelą, która odwzorowuje identyfikatory (np. n , factorial , print itp.) Na odpowiadające im wartości. W dowolnym momencie możesz uzyskać dostęp do bieżącego środowiska za pomocą locals() . W pierwszym wywołaniu funkcji jedyną zdefiniowaną zmienną lokalną jest n = 3 . Dlatego drukowanie locals() pokazuje {'n': 3} . Ponieważ n == 3 , zwracana wartość staje się n * factorial(n - 1) .
Na następnym etapie sprawy mogą stać się nieco zagmatwane. Patrząc na nasze nowe wyrażenie, wiemy już, czym jest n . Jednak nie wiemy jeszcze, co to jest factorial(n - 1) . Po pierwsze, n - 1 ocenia się na 2 . Następnie 2 jest przekazywane do factorial jako wartość n . Ponieważ jest to nowe wywołanie funkcji, stworzono drugie środowisko do przechowywania tego nowego n . Niech A będzie pierwszym środowiskiem, a B drugim środowiskiem. W jeszcze istnieje, jest równa {'n': 3} jednak B (co odpowiada {'n': 2} ) jest w obecnych warunkach. Patrząc na ciało funkcji, zwracana wartość jest znowu n * factorial(n - 1) . Nie oceniając tego wyrażenia, zastąpmy je pierwotnym wyrażeniem zwrotnym. Robiąc to, mentalnie odrzucamy B , więc pamiętaj, aby odpowiednio podstawić n (tj. Odniesienia do B ' n są zastąpione przez n - 1 który używa A ' n ). Teraz oryginalne wyrażenie zwrotne staje się n * ((n - 1) * factorial((n - 1) - 1)) . Poświęć chwilę, aby upewnić się, że rozumiesz, dlaczego tak jest.
Teraz factorial((n - 1) - 1)) część tego. Ponieważ A ' n == 3 , przekazujemy 1 do factorial . Dlatego tworzymy nowe środowisko C, które jest równe {'n': 1} . Ponownie wartość zwracana jest n * factorial(n - 1) . Zastąpmy więc factorial((n - 1) - 1)) „oryginalnego” wyrażenia zwrotnego podobnie do tego, jak wcześniej zmieniliśmy pierwotne wyrażenie zwrotne. „Oryginalne” wyrażenie to teraz n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1))) .
Prawie skończone. Teraz musimy ocenić factorial((n - 2) - 1) . Tym razem mijamy 0 . Dlatego ocenia się na 1 . Teraz wykonajmy naszą ostatnią zamianę. „Oryginalne” wyrażenie zwrotne to teraz n * ((n - 1) * ((n - 2) * 1)) . Przypominając, że oryginalne wyrażenie zwrotne jest oceniane pod A , wyrażenie staje się 3 * ((3 - 1) * ((3 - 2) * 1)) . To oczywiście daje wynik 6. Aby potwierdzić, że jest to poprawna odpowiedź, pamiętaj, że 3! == 3 * 2 * 1 == 6 . Przed dalszą lekturą upewnij się, że w pełni rozumiesz koncepcję środowisk i ich zastosowanie do rekurencji.
Instrukcja if n == 0: return 1 nazywa się przypadkiem podstawowym. Jest tak, ponieważ nie wykazuje rekurencji. Podstawowa obudowa jest absolutnie wymagana. Bez niego wpadniesz w nieskończoną rekurencję. Powiedziawszy to, dopóki masz przynajmniej jedną skrzynkę podstawową, możesz mieć tyle skrzynek, ile chcesz. Na przykład moglibyśmy napisać factorial w następujący sposób:
def factorial(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return n * factorial(n - 1)
Możesz również mieć wiele przypadków rekurencji, ale nie zajmiemy się tym, ponieważ jest to stosunkowo rzadkie i często trudne do mentalnego przetworzenia.
Możesz również mieć „równoległe” wywołania funkcji rekurencyjnych. Rozważmy na przykład sekwencję Fibonacciego, która jest zdefiniowana następująco:
- Jeśli liczba wynosi 0, odpowiedź brzmi 0.
- Jeśli liczba wynosi 1, odpowiedź brzmi 1.
- W przeciwnym razie odpowiedzią jest suma dwóch poprzednich liczb Fibonacciego.
Możemy to zdefiniować następująco:
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n - 2) + fib(n - 1)
Nie będę przechodził przez tę funkcję tak dokładnie, jak to zrobiłem z factorial(3) , ale końcowa wartość zwracana przez fib(5) jest równoważna z następującym (niepoprawnie syntaktycznie ) wyrażeniem:
(
fib((n - 2) - 2)
+
(
fib(((n - 2) - 1) - 2)
+
fib(((n - 2) - 1) - 1)
)
)
+
(
(
fib(((n - 1) - 2) - 2)
+
fib(((n - 1) - 2) - 1)
)
+
(
fib(((n - 1) - 1) - 2)
+
(
fib((((n - 1) - 1) - 1) - 2)
+
fib((((n - 1) - 1) - 1) - 1)
)
)
)
Staje się to (1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1))) co oczywiście daje wynik 5 .
Teraz omówmy jeszcze kilka terminów słownictwa:
- Wywołanie ogona to po prostu rekurencyjne wywołanie funkcji, które jest ostatnią operacją, jaka ma zostać wykonana przed zwróceniem wartości. Dla jasności,
return foo(n - 1)to wywołanie ogonowe, alereturn foo(n - 1) + 1nie (ponieważ dodawanie jest ostatnią operacją). - Optymalizacja wywołania ogona (TCO) to sposób na automatyczne zmniejszenie rekurencji w funkcjach rekurencyjnych.
- Eliminacja wywołania ogona (TCE) to redukcja wywołania ogona do wyrażenia, które można ocenić bez rekurencji. TCE jest rodzajem TCO.
Optymalizacja wezwania ogona jest pomocna z wielu powodów:
- Tłumacz może zminimalizować ilość pamięci zajmowanej przez środowiska. Ponieważ żaden komputer nie ma nieograniczonej pamięci, nadmierne wywołania funkcji rekurencyjnych doprowadziłyby do przepełnienia stosu .
- Tłumacz może zmniejszyć liczbę przełączników ramek stosu .
Python nie ma żadnej formy TCO wdrożonej z wielu powodów . Dlatego w celu obejścia tego ograniczenia wymagane są inne techniki. Wybór metody zależy od przypadku użycia. Z pewną intuicją definicje factorial i fib można stosunkowo łatwo przekonwertować na kod iteracyjny w następujący sposób:
def factorial(n):
product = 1
while n > 1:
product *= n
n -= 1
return product
def fib(n):
a, b = 0, 1
while n > 0:
a, b = b, a + b
n -= 1
return a
Jest to zazwyczaj najskuteczniejszy sposób ręcznego eliminowania rekurencji, ale może być trudniejszy w przypadku bardziej złożonych funkcji.
Innym przydatnym narzędziem jest dekorator lru_cache Pythona, którego można użyć do zmniejszenia liczby zbędnych obliczeń.
Masz teraz pomysł, jak uniknąć rekurencji w Pythonie, ale kiedy powinieneś używać rekurencji? Odpowiedź brzmi „nie często”. Wszystkie funkcje rekurencyjne mogą być implementowane iteracyjnie. Wystarczy po prostu dowiedzieć się, jak to zrobić. Są jednak rzadkie przypadki, w których rekurencja jest w porządku. Rekurencja jest powszechna w Pythonie, gdy oczekiwane dane wejściowe nie spowodowałyby znacznej liczby wywołań funkcji rekurencyjnych.
Jeśli rekurencja jest tematem, który Cię interesuje, zachęcam do nauki języków funkcjonalnych, takich jak Scheme lub Haskell. W takich językach rekurencja jest znacznie bardziej przydatna.
Należy zauważyć, że powyższy przykład sekwencji Fibonacciego, chociaż dobry w pokazaniu, jak zastosować definicję w pythonie, a później w użyciu pamięci podręcznej lru, ma nieefektywny czas działania, ponieważ wykonuje 2 rekurencyjne wywołania dla każdego przypadku innego niż podstawowy. Liczba wywołań funkcji rośnie wykładniczo do n .
Raczej nieintuicyjnie bardziej wydajna implementacja użyłaby rekurencji liniowej:
def fib(n):
if n <= 1:
return (n,0)
else:
(a, b) = fib(n - 1)
return (a + b, a)
Ale ten ma problem ze zwróceniem pary liczb. Podkreśla to, że niektóre funkcje naprawdę niewiele zyskują na rekurencji.
Eksploracja drzew z rekurencją
Powiedzmy, że mamy następujące drzewo:
root
- A
- AA
- AB
- B
- BA
- BB
- BBA
Teraz, jeśli chcemy wymienić wszystkie nazwy elementów, moglibyśmy to zrobić za pomocą prostej pętli for. Zakładamy, że istnieje funkcja get_name() do zwrócenia ciągu nazwy węzła, funkcja get_children() do zwrócenia listy wszystkich get_children() danego węzła w drzewie oraz funkcja get_root() do pobierz węzeł główny.
root = get_root(tree)
for node in get_children(root):
print(get_name(node))
for child in get_children(node):
print(get_name(child))
for grand_child in get_children(child):
print(get_name(grand_child))
# prints: A, AA, AB, B, BA, BB, BBA
Działa to szybko i dobrze, ale co, jeśli podwęzły mają własne podwęzły? A te podwęzły mogą mieć więcej podwęzłów ... A jeśli nie wiesz wcześniej, ile będzie? Metodą rozwiązania tego jest użycie rekurencji.
def list_tree_names(node):
for child in get_children(node):
print(get_name(child))
list_tree_names(node=child)
list_tree_names(node=get_root(tree))
# prints: A, AA, AB, B, BA, BB, BBA
Być może nie chcesz drukować, ale zwraca płaską listę wszystkich nazw węzłów. Można tego dokonać przekazując jako listę zmienną listę.
def list_tree_names(node, lst=[]):
for child in get_children(node):
lst.append(get_name(child))
list_tree_names(node=child, lst=lst)
return lst
list_tree_names(node=get_root(tree))
# returns ['A', 'AA', 'AB', 'B', 'BA', 'BB', 'BBA']
Zwiększenie maksymalnej głębokości rekurencji
Istnieje limit głębokości możliwej rekurencji, który zależy od implementacji Pythona. Po osiągnięciu limitu zgłaszany jest wyjątek RuntimeError:
RuntimeError: Maximum Recursion Depth Exceeded
Oto przykład programu, który spowodowałby ten błąd:
def cursing(depth):
try:
cursing(depth + 1) # actually, re-cursing
except RuntimeError as RE:
print('I recursed {} times!'.format(depth))
cursing(0)
# Out: I recursed 1083 times!
Można zmienić limit głębokości rekurencji za pomocą
sys.setrecursionlimit(limit)
Możesz sprawdzić, jakie są bieżące parametry limitu, uruchamiając:
sys.getrecursionlimit()
Korzystając z tej samej metody powyżej, z naszym nowym limitem, który otrzymujemy
sys.setrecursionlimit(2000)
cursing(0)
# Out: I recursed 1997 times!
Od wersji Python 3.5 wyjątkiem jest RecursionError, który pochodzi z RuntimeError.
Rekurencja ogona - zła praktyka
Gdy jedyną rzeczą zwracaną z funkcji jest wywołanie rekurencyjne, jest to określane jako rekurencja ogona.
Oto przykładowe odliczanie napisane przy użyciu rekurencji ogona:
def countdown(n):
if n == 0:
print "Blastoff!"
else:
print n
countdown(n-1)
Wszelkie obliczenia, które można wykonać za pomocą iteracji, można również wykonać za pomocą rekurencji. Oto wersja find_max napisana przy użyciu rekurencji ogona:
def find_max(seq, max_so_far):
if not seq:
return max_so_far
if max_so_far < seq[0]:
return find_max(seq[1:], seq[0])
else:
return find_max(seq[1:], max_so_far)
Rekurencja tail jest uważana za złą praktykę w Pythonie, ponieważ kompilator Python nie obsługuje optymalizacji wywołań rekurencyjnych tail. Rozwiązanie rekurencyjne w takich przypadkach wykorzystuje więcej zasobów systemowych niż równoważne rozwiązanie iteracyjne.
Optymalizacja rekurencji ogona poprzez introspekcję stosu
Domyślnie stos rekurencyjny Pythona nie może przekraczać 1000 ramek. Można to zmienić, ustawiając sys.setrecursionlimit(15000) który jest szybszy, jednak ta metoda zużywa więcej pamięci. Zamiast tego możemy również rozwiązać problem rekurencji ogona za pomocą introspekcji stosu.
#!/usr/bin/env python2.4
# This program shows off a python decorator which implements tail call optimization. It
# does this by throwing an exception if it is it's own grandparent, and catching such
# exceptions to recall the stack.
import sys
class TailRecurseException:
def __init__(self, args, kwargs):
self.args = args
self.kwargs = kwargs
def tail_call_optimized(g):
"""
This function decorates a function with tail call
optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such
exceptions to fake the tail call optimization.
This function fails if the decorated
function recurses in a non-tail context.
"""
def func(*args, **kwargs):
f = sys._getframe()
if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
raise TailRecurseException(args, kwargs)
else:
while 1:
try:
return g(*args, **kwargs)
except TailRecurseException, e:
args = e.args
kwargs = e.kwargs
func.__doc__ = g.__doc__
return func
Aby zoptymalizować funkcje rekurencyjne, możemy użyć dekoratora @tail_call_optimized do wywołania naszej funkcji. Oto kilka typowych przykładów rekurencji z wykorzystaniem dekoratora opisanego powyżej:
Przykład czynnikowy:
@tail_call_optimized
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
return factorial(n-1, n*acc)
print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.
Przykład Fibonacciego:
@tail_call_optimized
def fib(i, current = 0, next = 1):
if i == 0:
return current
else:
return fib(i - 1, next, current + next)
print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.