Python Language
Herhaling
Zoeken…
Opmerkingen
Recursie heeft een stopCondition nodig om de recursie te verlaten.
De oorspronkelijke variabele moet worden doorgegeven aan de recursieve functie zodat deze wordt opgeslagen.
Som van getallen van 1 tot n
Als ik de som van getallen van 1 tot n wilde weten, waarbij n een natuurlijk getal is, kan ik 1 + 2 + 3 + 4 + ... + (several hours later) + n . Als alternatief zou ik een for lus kunnen schrijven:
n = 0
for i in range (1, n+1):
n += i
Of ik zou een techniek kunnen gebruiken die bekend staat als recursie:
def recursion(n):
if n == 1:
return 1
return n + recursion(n - 1)
Recursie heeft voordelen boven de bovengenoemde twee methoden. Recursie kost minder tijd dan het schrijven van 1 + 2 + 3 voor een bedrag van 1 tot 3. Voor recursion(4) kan recursie worden gebruikt om achteruit te werken:
Functieoproepen: (4 -> 4 + 3 -> 4 + 3 + 2 -> 4 + 3 + 2 + 1 -> 10)
Terwijl de for lus strikt naar voren werkt: (1 -> 1 + 2 -> 1 + 2 + 3 -> 1 + 2 + 3 + 4 -> 10). Soms is de recursieve oplossing eenvoudiger dan de iteratieve oplossing. Dit is duidelijk bij het implementeren van een omkering van een gekoppelde lijst.
Het wat, hoe en wanneer van recursie
Recursie vindt plaats wanneer een functie-aanroep ervoor zorgt dat dezelfde functie opnieuw wordt aangeroepen voordat de oorspronkelijke functie-aanroep wordt beëindigd. Beschouw bijvoorbeeld de bekende wiskundige uitdrukking x! (dat wil zeggen de faculteit). De faculteit is als volgt gedefinieerd voor alle niet-negatieve gehele getallen:
- Als het nummer 0 is, is het antwoord 1.
- Anders is het antwoord dat getal maal de faculteit van één minder dan dat getal.
In Python kan een naïeve implementatie van de faculteit als volgt worden gedefinieerd als een functie:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
Recursiefuncties kunnen soms moeilijk te begrijpen zijn, dus laten we dit stap voor stap doornemen. Beschouw de uitdrukking factorial(3) . Deze en alle functieaanroepen creëren een nieuwe omgeving . Een omgeving is in feite gewoon een tabel die identificatiegegevens (bijvoorbeeld n , factorial , print , enz.) factorial aan hun overeenkomstige waarden. U kunt op elk moment toegang krijgen tot de huidige omgeving met behulp van de locals() . In de eerste functieaanroep is de enige lokale variabele die wordt gedefinieerd n = 3 . Daarom geeft locals() afdrukken {'n': 3} . Omdat n == 3 , wordt de retourwaarde n * factorial(n - 1) .
Bij deze volgende stap kunnen dingen een beetje verwarrend worden. Als we naar onze nieuwe uitdrukking kijken, weten we al wat n is. We weten echter nog niet wat factorial(n - 1) is. Eerst komt n - 1 overeen met 2 . Vervolgens wordt 2 doorgegeven aan factorial als de waarde voor n . Aangezien dit een nieuwe functieaanroep is, wordt een tweede omgeving gemaakt om deze nieuwe n te slaan. Laat A de eerste omgeving zijn en B de tweede omgeving. A bestaat nog steeds en is gelijk aan {'n': 3} , echter B (wat gelijk is aan {'n': 2} ) is de huidige omgeving. Kijkend naar de functie body, is de retourwaarde opnieuw n * factorial(n - 1) . Laten we, zonder deze expressie te evalueren, deze vervangen door de oorspronkelijke return-expressie. Door dit te doen, we zijn mentaal ontdoen B, dus vergeet niet te vervangen n dienovereenkomstig (dwz verwijzingen naar B 's n worden vervangen door n - 1 die gebruik maakt van A' s n ). Nu wordt de oorspronkelijke return-uitdrukking n * ((n - 1) * factorial((n - 1) - 1)) . Neem even de tijd om ervoor te zorgen dat u begrijpt waarom dit zo is.
Laten we nu het factorial((n - 1) - 1)) gedeelte daarvan evalueren. Omdat A 's n == 3 , geven we 1 aan factorial . Daarom creëren we een nieuwe omgeving C die gelijk is aan {'n': 1} . Nogmaals, de retourwaarde is n * factorial(n - 1) . Laten we dus de factorial((n - 1) - 1)) van de "oorspronkelijke" return-expressie vervangen op dezelfde manier als hoe we de oorspronkelijke return-expressie eerder hebben aangepast. De "oorspronkelijke" uitdrukking is nu n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1))) .
Bijna klaar. Nu moeten we factorial((n - 2) - 1) evalueren. Deze keer passeren we 0 . Daarom komt dit neer op 1 . Laten we nu onze laatste vervanging uitvoeren. De "oorspronkelijke" return-expressie is nu n * ((n - 1) * ((n - 2) * 1)) . Erop wijzend dat de oorspronkelijke terugkeer-uitdrukking wordt geëvalueerd onder A , wordt de uitdrukking 3 * ((3 - 1) * ((3 - 2) * 1)) . Dit komt natuurlijk overeen met 6. Om te bevestigen dat dit het juiste antwoord is, onthoud dat 3! == 3 * 2 * 1 == 6 . Voordat u verder leest, moet u ervoor zorgen dat u het concept van omgevingen volledig begrijpt en begrijpt hoe deze van toepassing zijn op recursie.
De instructie if n == 0: return 1 wordt een base case genoemd. Dit komt omdat het geen recursie vertoont. Een basisscenario is absoluut vereist. Zonder een daarvan kom je oneindige recursie tegen. Dat gezegd hebbende, zolang je ten minste één basisscenario hebt, kun je zoveel cases hebben als je wilt. Zo konden we equivalent hebben geschreven factorial als volgt:
def factorial(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return n * factorial(n - 1)
U kunt ook meerdere recursiegevallen hebben, maar daar zullen we niet op ingaan omdat het relatief ongewoon is en vaak mentaal moeilijk te verwerken is.
U kunt ook "parallelle" recursieve functieoproepen hebben. Overweeg bijvoorbeeld de Fibonacci-reeks die als volgt is gedefinieerd:
- Als het nummer 0 is, is het antwoord 0.
- Als het nummer 1 is, is het antwoord 1.
- Anders is het antwoord de som van de vorige twee Fibonacci-getallen.
We kunnen dit als volgt definiëren:
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n - 2) + fib(n - 1)
Ik zal deze functie niet zo grondig doorlopen als bij factorial(3) , maar de uiteindelijke retourwaarde van fib(5) is gelijk aan de volgende ( syntactisch ongeldige) expressie:
(
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)
)
)
)
Dit wordt (1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1))) wat natuurlijk resulteert in 5 .
Laten we nu nog een paar woordenschattermen behandelen:
- Een staartoproep is gewoon een recursieve functieaanroep die de laatste bewerking is die wordt uitgevoerd voordat een waarde wordt geretourneerd. Voor de duidelijkheid,
return foo(n - 1)is een staartoproep, maarreturn foo(n - 1) + 1is dat niet (omdat de toevoeging de laatste bewerking is). - Tail Call Optimization (TCO) is een manier om automatisch de recursie in recursieve functies te verminderen.
- Tail call eliminatie (TCE) is de reductie van een tail call tot een uitdrukking die kan worden geëvalueerd zonder recursie. TCE is een type TCO.
Tail call-optimalisatie is om een aantal redenen nuttig:
- De tolk kan de hoeveelheid geheugen die wordt ingenomen door omgevingen minimaliseren. Aangezien geen enkele computer onbeperkt geheugen heeft, zouden excessieve recursieve functieaanroepen leiden tot een stackoverloop .
- De tolk kan het aantal stapelframe- schakelaars verminderen.
Python heeft om een aantal redenen geen enkele vorm van TCO geïmplementeerd. Daarom zijn andere technieken vereist om deze beperking te omzeilen. De gekozen methode is afhankelijk van het gebruik. Met enige intuïtie kunnen de definities van factorial en fib relatief eenvoudig als volgt worden omgezet in iteratieve code:
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
Dit is meestal de meest efficiënte manier om recursie handmatig te elimineren, maar het kan nogal moeilijk zijn voor meer complexe functies.
Een ander handig hulpmiddel is de lru_cache- decorateur van Python die kan worden gebruikt om het aantal overbodige berekeningen te verminderen.
U hebt nu een idee hoe u recursie in Python kunt voorkomen, maar wanneer moet u recursie gebruiken? Het antwoord is "niet vaak". Alle recursieve functies kunnen iteratief worden geïmplementeerd. Het is gewoon een kwestie van uitzoeken hoe dat te doen. Er zijn echter zeldzame gevallen waarin recursie in orde is. Recursie is gebruikelijk in Python wanneer de verwachte invoer geen significant aantal recursieve functieaanroepen zou veroorzaken.
Als recursie een onderwerp is dat je interesseert, smeek ik je om functionele talen zoals Scheme of Haskell te bestuderen. In dergelijke talen is recursie veel nuttiger.
Merk op dat het bovenstaande voorbeeld voor de Fibonacci-reeks, hoewel het goed is om te laten zien hoe de definitie in python en later gebruik van de lru-cache moet worden toegepast, een inefficiënte looptijd heeft omdat het 2 recursieve aanroepen doet voor elk niet-basisscenario. Het aantal aanroepen van de functie groeit exponentieel naar n .
Niet-intuïtief zou een efficiëntere implementatie lineaire recursie gebruiken:
def fib(n):
if n <= 1:
return (n,0)
else:
(a, b) = fib(n - 1)
return (a + b, a)
Maar die heeft de kwestie van een paar getallen terug te geven. Dit benadrukt dat sommige functies echt niet veel baat hebben bij recursie.
Boomverkenning met recursie
Stel dat we de volgende boom hebben:
root
- A
- AA
- AB
- B
- BA
- BB
- BBA
Als we nu alle namen van de elementen willen vermelden, kunnen we dit doen met een eenvoudige for-loop. We nemen aan dat er een functie get_name() om een tekenreeks van de naam van een knoop te retourneren, een functie get_children() om een lijst met alle get_children() van een gegeven knooppunt in de boom te get_root() en een functie get_root() naar verkrijg de root node.
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
Dit werkt goed en snel, maar wat als de subknopen zelf subknopen hebben? En die subknooppunten hebben misschien meer subknooppunten ... Wat als u niet van tevoren weet hoeveel er zullen zijn? Een methode om dit op te lossen is het gebruik van recursie.
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
Misschien wilt u niet afdrukken, maar een platte lijst met alle knooppuntnamen retourneren. Dit kan worden gedaan door een rollende lijst als parameter door te geven.
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']
De maximale recursiediepte verhogen
Er is een limiet aan de diepte van mogelijke recursie, die afhangt van de Python-implementatie. Wanneer de limiet is bereikt, wordt een RuntimeError-uitzondering opgeworpen:
RuntimeError: Maximum Recursion Depth Exceeded
Hier is een voorbeeld van een programma dat deze fout zou veroorzaken:
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!
Het is mogelijk om de limiet van de recursiediepte te wijzigen met behulp van
sys.setrecursionlimit(limit)
U kunt controleren wat de huidige parameters van de limiet zijn door het uitvoeren van:
sys.getrecursionlimit()
Het uitvoeren van dezelfde methode hierboven met onze nieuwe limiet die we krijgen
sys.setrecursionlimit(2000)
cursing(0)
# Out: I recursed 1997 times!
Van Python 3.5 is de uitzondering een RecursionError, die is afgeleid van RuntimeError.
Tail Recursion - Bad Practice
Wanneer het enige dat uit een functie wordt geretourneerd een recursieve aanroep is, wordt dit staartrecursie genoemd.
Hier is een voorbeeld van een aftelling geschreven met behulp van staartrecursie:
def countdown(n):
if n == 0:
print "Blastoff!"
else:
print n
countdown(n-1)
Elke berekening die kan worden gemaakt met behulp van iteratie kan ook worden gemaakt met behulp van recursie. Hier is een versie van find_max geschreven met behulp van staartrecursie:
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)
Tail recursion wordt beschouwd als een slechte gewoonte in Python, omdat de Python-compiler geen optimalisatie voor tail recursieve aanroepen afhandelt. De recursieve oplossing gebruikt in dergelijke gevallen meer systeembronnen dan de equivalente iteratieve oplossing.
Tail Recursion Optimization via Stack Introspection
Standaard mag de recursiestapel van Python niet groter zijn dan 1000 frames. Dit kan worden gewijzigd door de sys.setrecursionlimit(15000) die sneller is, deze methode verbruikt echter meer geheugen. In plaats daarvan kunnen we het probleem van Tail Recursion ook oplossen met behulp van stapelintrospectie.
#!/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
Om de recursieve functies te optimaliseren, kunnen we de @tail_call_optimized decorator gebruiken om onze functie aan te roepen. Hier zijn enkele van de meest voorkomende recursie-voorbeelden met de hierboven beschreven decorateur:
Factorie Voorbeeld:
@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 Voorbeeld:
@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.