Wat is recursie?
recursie is het proces van het definiëren van iets in termen van zichzelf.
een fysieke wereld voorbeeld zou zijn om twee parallelle spiegels tegenover elkaar te plaatsen. Elk object tussen hen zou recursief worden gereflecteerd.
Python recursieve functie
In Python weten we dat een functie andere functies kan aanroepen. Het is zelfs mogelijk dat de functie zichzelf roept. Deze types van construct worden genoemd als recursieve functies.
de volgende afbeelding toont de werking van een recursieve functie genaamd recurse.
Dit is een voorbeeld van een recursieve functie om de faculteit van een geheel getal te vinden.
Faculteit van een getal is het product van alle gehele getallen van 1 tot dat getal. Bijvoorbeeld, de faculteit van 6 (aangeduid als 6!) is 1*2*3*4*5*6 = 720.
voorbeeld van een recursieve functie
def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1))num = 3print("The factorial of", num, "is", factorial(num))Output
The factorial of 3 is 6
in het bovenstaande voorbeeld is factorial() een recursieve functie zoals het zichzelf noemt.
wanneer we deze functie aanroepen met een positief geheel getal, zal het zichzelf recursief aanroepen door het aantal te verminderen.
elke functie vermenigvuldigt het getal met de faculteit van het getal eronder totdat het gelijk is aan één. Deze recursieve aanroep kan in de volgende stappen worden uitgelegd.
factorial(3) # 1st call with 33 * factorial(2) # 2nd call with 23 * 2 * factorial(1) # 3rd call with 13 * 2 * 1 # return from 3rd call as number=13 * 2 # return from 2nd call6 # return from 1st call
Laten we eens kijken naar een beeld dat geeft een stap-voor-stap proces van wat er gaande is:
Onze recursie wanneer het aantal reduceert tot 1. Dit wordt de basisvoorwaarde genoemd.
elke recursieve functie moet een basisvoorwaarde hebben die de recursie stopt of anders roept de functie zichzelf oneindig aan.
De Python interpreter beperkt de dieptes van recursie om oneindige recursies te voorkomen, wat resulteert in stack overflows.
standaard is de maximale diepte van recursie 1000. Als de limiet wordt overschreden, resulteert dit in RecursionError. Laten we eens kijken naar een dergelijke voorwaarde.
def recursor(): recursor()recursor()Output
Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a RecursionError: maximum recursion depth exceeded
voordelen van recursie
- recursieve functies laten de code er schoon en elegant uitzien.
- een complexe taak kan worden opgesplitst in eenvoudigere subproblemen met behulp van recursie.
- Sequentiegeneratie is gemakkelijker met recursie dan met geneste iteratie.
nadelen van recursie
- soms is de logica achter recursie moeilijk te volgen.
- recursieve aanroepen zijn duur (inefficiënt) omdat ze veel geheugen en tijd in beslag nemen.
- recursieve functies zijn moeilijk te debuggen.