Wat is een recursieve functie?
Functie roept zichzelf steeds opnieuw op totdat het voldoet aan een recursieve toestand. Een recursiefunctie splitst het probleem op in kleinere problemen en roept zijn eigen logica op om het kleinere probleem op te lossen. Deze techniek staat bekend als verdeel en heers. Het wordt gebruikt in wiskunde en informatica.
De recursieve functie omvat een basisgeval (of terminalgeval) en een recursief geval. In het basisscenario kunt u overwegen het grootste probleem op te lossen en het recursieve geval verdeelt het probleem in kleinere delen totdat het een niveau bereikt waarop het gemakkelijk kan worden opgelost. Een recursief geval kan een resultaat opleveren of het kan zichzelf opnieuw oproepen om het probleem verder te verdelen. Elke keer dat het probleem in een kleiner probleem opslaat, slaat de functie die steeds recursief wordt opgeroepen de status van het gesprek op en verwacht het resultaat van zichzelf na het oplossen van het probleem.
Recursieve functie in Python
Het concept van recursie blijft hetzelfde in Python. De functie roept zichzelf op om het probleem op te splitsen in kleinere problemen. Het eenvoudigste voorbeeld dat we kunnen bedenken, is het vinden van de factor van een getal.
Laten we zeggen dat we de faculteit van getal 5 => 5 moeten vinden! (Ons probleem)
Om er 5 te vinden! het probleem kan worden onderverdeeld in kleinere 5! => 5 x 4!
Dus om 5 te krijgen! We moeten er 4 vinden! en vermenigvuldig het met 5.
Laten we het probleem blijven verdelen
5! = 4! x 5
4! = 3! x 4
3! = 3 x 2!
2! = 2 x 1!
1! = 1
Wanneer het de kleinste brok bereikt, dat wil zeggen, als we de faculteit van 1 krijgen, kunnen we het resultaat teruggeven als
Laten we een voorbeeld van een pseudocode nemen: -
Algoritme voor faculteit
Laten we het algoritme voor faculteit bekijken:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Functie oproepen
Stel dat we een faculteit van 5 vinden.
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
Het eindresultaat zal 120 zijn waar we begonnen met de uitvoering van de functie. Onze recursiefunctie stopt wanneer het aantal zo is verlaagd dat het resultaat kan worden verkregen.
- De eerste oproep die de faculteit 5 krijgt, resulteert in een recursieve toestand waarin deze wordt toegevoegd aan de stapel en een andere oproep zal worden gedaan nadat het aantal tot 4 is verlaagd.
- Deze recursie zal blijven bellen en het probleem in kleinere stukken breken totdat het de basisconditie bereikt.
- De basisvoorwaarde is hier wanneer het nummer 1 is.
- Elke recursieve functie heeft zijn eigen recursieve toestand en een basisvoorwaarde.
Voors en tegens van Python recursieve functie
- De uitvoering van recursie is zodanig dat er geen berekeningen worden uitgevoerd totdat de basisvoorwaarde is bereikt.
- Bij het bereiken van basiscondities kan het geheugen vol raken.
- In een groot probleem waarbij er een miljoen stappen kunnen zijn of we kunnen zeggen dat een miljoen recursies om het programma te doen, geheugenfout of een segmentatiefout kunnen geven.
- 1000000! = 1000000 * 999999! =?
- Recursie is anders dan iteratie en schaalt niet op als een iteratieve methode.
- Verschillende talen hebben verschillende optimalisaties voor recursie.
- In veel talen zou de iteratieve methode beter presteren dan recursie.
- Elke taal heeft enkele beperkingen met betrekking tot de diepte van recursie die u kunt tegenkomen bij het oplossen van grote problemen.
- Soms is het moeilijk om de complexe problemen met recursie te begrijpen, terwijl het met iteratie vrij eenvoudig is.
Enkele voordelen
- In sommige gevallen is recursie een handige en snellere manier om te gebruiken.
- Zeer nuttig bij het doorkruisen van de boom en het zoeken naar binaire bestanden.
Python-code - recursie versus herhaling
We begrepen wat recursie is en hoe het werkt in Python, omdat we weten dat alle talen een verschillende implementatie van recursie hebben voor geheugen- en computeroptimalisaties. Er kan een geval zijn waarbij iteratie sneller zou zijn dan recursie.
Hier zouden we zowel de recursie- als iteratiemethode vergelijken om te zien hoe Python in beide gevallen presteert.
1. Recursiecode voor factoren
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. Factorieprobleem met iteratie (looping)
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. Resultaten afdrukken
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
Output:
Zoals we kunnen zien, geven beide dezelfde uitvoer als we dezelfde logica hebben geschreven. Hier zien we geen verschil in uitvoering.
Laten we wat tijdcode toevoegen om meer informatie te krijgen over de uitvoering van recursie en iteratie in Python.
We zullen de "tijd" -bibliotheek importeren en controleren hoe lang recursie en iteratie duren om het resultaat te retourneren.
4. Code met tijdberekening
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))
We zullen herhaalde uitvoeringen met een andere waarde voor faculteit uitvoeren en de resultaten bekijken. De onderstaande resultaten kunnen per machine verschillen. We hebben MacBook Pro 16 GB RAM i7 gebruikt.
We gebruiken Python 3.7 voor uitvoering
Geval 1: - Factorie van 6:
Case 2: Factorial van 50:
Case 3: Factorial van 100:
Case 4: Factorial van 500:
Case 5: Factorial van 1000:
We hebben beide methoden in een ander probleem geanalyseerd. Bovendien hebben beide op dezelfde manier gepresteerd, behalve in geval 4.
In geval 5 kregen we een foutmelding tijdens het doen met recursie.
Python kreeg een beperking op de maximale diepte die je kunt gebruiken met recursie, maar hetzelfde probleem dat ik met iteratie kon oplossen.
Python heeft beperkingen tegen het probleem van overloop. Python is niet geoptimaliseerd voor staartrecursie en ongecontroleerde recursie veroorzaakt een stapeloverloop.
De functie "sys.getrecursionlimit ()" geeft u de limiet voor recursie.
De recursielimiet kan worden gewijzigd, maar wordt niet aanbevolen. Het kan gevaarlijk zijn.
Conclusie - Recursieve functie Python
- Recursie is een handige oplossing voor sommige problemen, zoals boom doorkruisen en andere problemen.
- Python is geen functionele programmeertaal en we kunnen zien dat de recursiestapel niet zo geoptimaliseerd is in vergelijking met iteratie.
- We zouden iteratie in ons algoritme moeten gebruiken, omdat het meer geoptimaliseerd is in Python en u een betere snelheid geeft.
Aanbevolen artikelen
Dit is een handleiding voor recursieve functies in Python. Hier bespreken we Wat is Recursieve functie, Recursieve functie in Python, Algorithm voor faculteit, enz. U kunt ook onze andere voorgestelde artikelen bekijken voor meer informatie–
- Factorial in Python
- Spark Shell-opdrachten
- Beste C-compilers
- Soorten algoritmen
- Factorieprogramma in JavaScript
- Handleiding voor de lijst met Unix Shell-opdrachten
- Soorten formulieren reageren met voorbeelden