Python Language
Rekursion
Sök…
Anmärkningar
Rekursion behöver ett stopCondition för att lämna rekursionen.
Den ursprungliga variabeln måste vidarebefordras till rekursiv funktion så att den lagras.
Summan av siffrorna från 1 till n
Om jag ville ta reda på summan av siffror från 1 till n där n är ett naturligt tal kan jag göra 1 + 2 + 3 + 4 + ... + (several hours later) + n . Alternativt kunde jag skriva en for loop:
n = 0
for i in range (1, n+1):
n += i
Eller så kan jag använda en teknik som kallas rekursion:
def recursion(n):
if n == 1:
return 1
return n + recursion(n - 1)
Rekursion har fördelar jämfört med ovanstående två metoder. Rekursion tar mindre tid än att skriva ut 1 + 2 + 3 för en summa från 1 till 3. För recursion(4) kan rekursion användas för att arbeta bakåt:
Funktionssamtal: (4 -> 4 + 3 -> 4 + 3 + 2 -> 4 + 3 + 2 + 1 -> 10)
Medan for loop fungerar strikt framåt: (1 -> 1 + 2 -> 1 + 2 + 3 -> 1 + 2 + 3 + 4 -> 10). Ibland är den rekursiva lösningen enklare än den iterativa lösningen. Detta är uppenbart när man implementerar en reversering av en länkad lista.
Vad, hur och när rekursion
Rekursion inträffar när ett funktionssamtal får samma funktion att ringas igen innan det ursprungliga funktionssamtalet avslutas. Tänk till exempel på det välkända matematiska uttrycket x! (dvs. fabriksoperationen). Fabriksoperationen definieras för alla icke-negativa heltal enligt följande:
- Om numret är 0 är svaret 1.
- Annars är svaret att antalet gånger faktorn för en mindre än det numret.
I Python kan en naiv implementering av den faktiska operationen definieras som en funktion enligt följande:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
Rekursionsfunktioner kan vara svåra att förstå ibland, så låt oss gå igenom detta steg för steg. Tänk på uttrycket factorial(3) . Denna och alla funktionssamtal skapar en ny miljö . En miljö är i princip bara en tabell som kartlägger identifierare (t.ex. n , factorial , print etc.) till deras motsvarande värden. När som helst kan du komma åt den aktuella miljön med locals() . I det första funktionssamtalet är den enda lokala variabeln som definieras n = 3 . Därför skulle utskrift av locals() visa {'n': 3} . Eftersom n == 3 blir returvärdet n * factorial(n - 1) .
Vid det här nästa steget kan saker och ting bli lite förvirrande. När vi tittar på vårt nya uttryck vet vi redan vad n är. Men vi vet ännu inte vad factorial(n - 1) är. Först utvärderar n - 1 till 2 . Då, 2 ledes till factorial som värdet för n . Eftersom detta är ett nytt funktionssamtal skapas en andra miljö för att lagra den nya n . Låt A vara den första miljön och B vara den andra miljön. A finns fortfarande och är lika med {'n': 3} , men B (vilket är lika med {'n': 2} ) är den aktuella miljön. När man tittar på funktionskroppen är returvärdet återigen n * factorial(n - 1) . Utan att utvärdera detta uttryck, låt oss ersätta det i det ursprungliga returuttrycket. Genom att göra detta kasserar vi mentalt B , så kom ihåg att ersätta n enlighet därmed (dvs hänvisningar till B 's n ersätts med n - 1 som använder A ' s n ). Nu blir det ursprungliga returuttrycket n * ((n - 1) * factorial((n - 1) - 1)) . Ta en sekund för att se till att du förstår varför det är så.
Låt oss nu utvärdera factorial((n - 1) - 1)) delen av det. Eftersom A är n == 3 , n == 3 vi 1 till factorial . Därför skapar vi en ny miljö C som är lika med {'n': 1} . Återigen är returvärdet n * factorial(n - 1) . Så låt oss ersätta factorial((n - 1) - 1)) av det "ursprungliga" retursuttrycket på samma sätt som vi justerade det ursprungliga returuttrycket tidigare. Det "ursprungliga" uttrycket är nu n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1))) .
Nästan klar. Nu måste vi utvärdera factorial((n - 2) - 1) . Den här gången passerar vi 0 . Därför utvärderas detta till 1 . Låt oss nu utföra vår sista ersättning. Det ”ursprungliga” returuttrycket är nu n * ((n - 1) * ((n - 2) * 1)) . Påminner om att det ursprungliga returuttrycket utvärderas under A blir uttrycket 3 * ((3 - 1) * ((3 - 2) * 1)) . Detta utvärderas naturligtvis till 6. För att bekräfta att detta är rätt svar, kom ihåg att 3! == 3 * 2 * 1 == 6 . Innan du läser ytterligare ska du vara säker på att du förstår miljöbegreppet och hur de gäller rekursion.
Uttalandet if n == 0: return 1 kallas ett basfall. Det beror på att det inte visar någon rekursion. Ett basfall är absolut nödvändigt. Utan en kommer du att få oändlig rekursion. Med det sagt, så länge du har minst ett basmål, kan du ha så många fall du vill. Vi kan till exempel ha likvärdigt skrivna factorial enligt följande:
def factorial(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return n * factorial(n - 1)
Du kan också ha flera rekursionsfall, men det kommer vi inte in eftersom det är relativt ovanligt och ofta är svårt att behandla mentalt.
Du kan också ha "parallella" rekursiva funktionssamtal. Tänk till exempel Fibonacci-sekvensen som definieras enligt följande:
- Om numret är 0 är svaret 0.
- Om numret är 1 är svaret 1.
- Annars är svaret summan av de föregående två Fibonacci-siffrorna.
Vi kan definiera att detta är enligt följande:
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n - 2) + fib(n - 1)
Jag går inte igenom den här funktionen så noggrant som jag gjorde med factorial(3) , men det slutliga returvärdet för fib(5) motsvarar följande ( syntaktiskt ogiltiga) uttryck:
(
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)
)
)
)
Detta blir (1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1))) som naturligtvis utvärderar till 5 .
Låt oss nu täcka några fler ordförråd:
- Ett svanssamtal är helt enkelt ett rekursivt funktionssamtal som är den sista operationen som ska utföras innan ett värde returneras. För att vara tydlig är
return foo(n - 1)ett svanssamtal, menreturn foo(n - 1) + 1är inte (eftersom tillägget är den sista handlingen). - Tail Call Optimization (TCO) är ett sätt att automatiskt minska rekursionen i rekursiva funktioner.
- Tail Call eliminering (TCE) är reduktionen av ett svarsanrop till ett uttryck som kan utvärderas utan rekursion. TCE är en typ av TCO.
Optimering av svanssamtal är användbart av flera skäl:
- Tolkaren kan minimera mängden minne som upptas av miljöer. Eftersom ingen dator har obegränsat minne skulle överdrivna rekursiva funktionssamtal leda till ett överflöde av stacken .
- Tolkaren kan minska antalet stapelramomkopplare .
Python har ingen form av TCO implementerad av ett antal skäl . Därför krävs andra tekniker för att kjola denna begränsning. Valmetoden beror på användningsfallet. Med viss intuition kan definitionerna av factorial och fib relativt enkelt konverteras till iterativ kod enligt följande:
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
Detta är vanligtvis det mest effektiva sättet att manuellt eliminera rekursion, men det kan bli ganska svårt för mer komplexa funktioner.
Ett annat användbart verktyg är Pythons lru_cache- dekoratör som kan användas för att minska antalet redundanta beräkningar.
Du har nu en idé om hur man undviker rekursion i Python, men när ska du använda rekursion? Svaret är "inte ofta". Alla rekursiva funktioner kan implementeras iterativt. Det är helt enkelt en fråga om hur man gör det. Men det finns sällsynta fall där rekursion är okej. Rekursion är vanligt i Python när de förväntade ingångarna inte skulle orsaka ett betydande antal rekursiva funktionssamtal.
Om rekursion är ett ämne som intresserar dig, ber jag dig att studera funktionella språk som Scheme eller Haskell. På sådana språk är rekursion mycket mer användbar.
Observera att exemplet ovan för Fibonacci-sekvensen, även om det är bra på att visa hur man tillämpar definitionen i python och senare användning av lru-cache, har en ineffektiv körningstid eftersom den gör 2 rekursiva samtal för varje icke-basfall. Antalet samtal till funktionen växer exponentiellt till n .
Snarare icke-intuitivt skulle en mer effektiv implementering använda linjär rekursion:
def fib(n):
if n <= 1:
return (n,0)
else:
(a, b) = fib(n - 1)
return (a + b, a)
Men den har frågan om att returnera ett par nummer. Detta betonar att vissa funktioner verkligen inte får mycket av rekursion.
Trädutforskning med rekursion
Säg att vi har följande träd:
root
- A
- AA
- AB
- B
- BA
- BB
- BBA
Om vi nu vill lista alla namn på elementen kan vi göra detta med en enkel för-loop. Vi antar att det finns en funktion get_name() att returnera en sträng med namnet på en nod, en funktion get_children() att returnera en lista med alla undernoder för en given nod i trädet, och en funktion get_root() till få rotnoden.
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
Detta fungerar bra och snabbt, men vad händer om undernoderna fick sina egna undernoder? Och dessa undernoder kan ha fler undernoder ... Vad händer om du inte vet i förväg hur många det kommer att finnas? En metod för att lösa detta är användningen av rekursion.
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
Du kanske inte vill skriva ut, men returnera en platt lista med alla nodnamn. Detta kan göras genom att lämna en rullande lista som en parameter.
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']
Öka det maximala rekursionsdjupet
Det finns en gräns för djupet för möjlig rekursion, vilket beror på Python-implementeringen. När gränsen uppnås höjs ett RuntimeError-undantag:
RuntimeError: Maximum Recursion Depth Exceeded
Här är ett exempel på ett program som skulle orsaka detta fel:
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!
Det är möjligt att ändra gränsen för rekursionsdjup med
sys.setrecursionlimit(limit)
Du kan kontrollera vad de aktuella parametrarna för gränsen är genom att köra:
sys.getrecursionlimit()
Kör samma metod ovan med vår nya gräns vi får
sys.setrecursionlimit(2000)
cursing(0)
# Out: I recursed 1997 times!
Från Python 3.5 är undantaget en RecursionError, som härrör från RuntimeError.
Rekursion för svans - dålig praxis
När det enda som returneras från en funktion är ett rekursivt samtal, kallas det svansrekursion.
Här är ett exempel på nedräkning skriven med svansrekursion:
def countdown(n):
if n == 0:
print "Blastoff!"
else:
print n
countdown(n-1)
Alla beräkningar som kan göras med iteration kan också göras med rekursion. Här är en version av find_max skriven med svansrekursion:
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)
Rekursion av svans anses vara en dålig praxis i Python, eftersom Python-kompilatorn inte hanterar optimering för rekursiva samtal. Den rekursiva lösningen i sådana fall använder fler systemresurser än den motsvarande iterativa lösningen.
Optimering av svansrekursion genom stackintrospektion
Som standard kan Pythons rekursionsstack inte överstiga 1000 bilder. Detta kan ändras genom att ställa in sys.setrecursionlimit(15000) vilket är snabbare men denna metod förbrukar mer minne. Istället kan vi också lösa problemet med Tail Recursion med hjälp av stapelens introspektion.
#!/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
För att optimera de rekursiva funktionerna kan vi använda @tail_call_optimized dekoratören för att kalla vår funktion. Här är några av de vanliga rekursionsexemplen med dekoratorn som beskrivs ovan:
Faktoriella exempel:
@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.
Fibonacci-exempel:
@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.
