In eenvoudige bewoordingen is recursie een manier om het probleem op te lossen door zelf een functie aan te roepen, het woord ' recursief 'Komt van het Latijnse werkwoord' terugkomen ”, Wat betekent dat je iets opnieuw moet doen. Dit is wat de recursieve functie doet, het doet steeds weer hetzelfde, dat wil zeggen dat het zichzelf herinnert. In dit artikel zullen we leren over recursie in python. Hieronder volgen de onderwerpen die in deze blog worden behandeld:
- Wat is recursie in Python?
- Beëindigingsvoorwaarde
- De recursielimiet van Python
- Lijsten afvlakken met recursie
- Voordelen van recursie
- Nadelen van recursie
Wat is recursie in Python?
Recursie is het proces waarbij iets op zichzelf wordt bepaald. We weten dat in Python elke functie elke andere functie kan aanroepen, een functie kan ook zichzelf aanroepen. Dit soort functies die zichzelf aanroepen totdat niet aan de bepaalde voorwaarde is voldaan, worden recursieve functies genoemd.
laten we een paar voorbeelden nemen om te zien hoe dat werkt. Als u een positief geheel getal n krijgt, zou de faculteit zijn.
- n! = n * (n-1) * (n-2) enzovoort.
- 2! = 2 * (2-1)
- een! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Als u de bovenstaande waarden vervangt, krijgt u de volgende uitdrukking
- 4! = 4 * 3 * 2 * 1
We moeten een functie definiëren, laten we zeggen feit (n), die een positief geheel getal of 0 als parameter heeft en de n-de faculteit retourneert, hoe kunnen we dat doen met behulp van recursie?
Laten we eens kijken, om dit te doen met behulp van recursie, moeten we de volgende vergelijking onderzoeken
n! = n. (n-1). (n-2) & hellip3.2.1
hoe semaforen in java te gebruiken
n! = n. (n-1)! #we kunnen de bovenstaande verklaring herschrijven zoals op deze regel
Als we nu 2 als parameter doorgeven, krijgen we:
2! = 2.1! = 2
Evenzo, als we slagen voor 1, krijgen we:
een! = 1,0! = 1
Maar als we de 0 passeren, breekt het
0! = 0. (- 1)! en hier is faculteit voor -1 niet gedefinieerd, dus dit werkt alleen voor waarden> 0
We moeten dus twee cases schrijven
1. n! = n. (n-1)! als n> = 1
2. 1 als n = 0
Dit is een complete oplossing voor alle positieve gehele getallen en 0.
Beëindigingsvoorwaarde
Een recursieve functie moet aan een belangrijke voorwaarde voldoen om te beëindigen. Op weg naar een toestand waarin het probleem kan worden opgelost zonder verdere recursie, zal een recursieve functie worden beëindigd, waardoor het probleem wordt geminimaliseerd in de kleinere substappen. Een recursie kan in een oneindige lus terechtkomen als in de oproepen niet aan de voorwaarde van beëindiging wordt voldaan.
Factoriële voorwaarden:
- faculteit van n = n * (n-1) zolang n groter is dan 1.
- 1 als n = 0
We zullen de bovenstaande faculteit voorwaarden converteren naar python-code:
def fact (n): if n == 1: return n else: return n * fact (n-1)
Laten we een voorbeeld nemen, stel dat we faculteit 4 willen vinden:
fact (4) #this retourneert 4 * fact (3) enzovoort tot n == 1.
Uitgang: 24
Het wordt zo vaak gebruikt als voorbeeld voor recursie vanwege zijn eenvoud en duidelijkheid. Het oplossen van kleinere gevallen van een probleem bij elke stap, wordt dit in de informatica genoemd als recursie.
De recursielimiet van Python
In sommige talen kun je een oneindige recursieve lus maken, maar in Python is er een recursielimiet. Om de limiet te controleren, voert u de volgende functie uit vanuit de sys-module. wat de limiet van de recursieset voor python zal geven.
php installeren op windows 10
import sys sys.getrecursionlimit ()
Uitgang: 1000
U kunt de limiet ook wijzigen met behulp van de functiesetrecursionlimit () van de sys-module, afhankelijk van uw vereiste. Laten we nu een functie maken die zichzelf recursief aanroept totdat deze de limiet overschrijdt en controleert wat er gebeurt:
def recursive (): recursive () if __name__ == '__main__': recursive ()
Als u de bovenstaande code uitvoert, krijgt u een runtime-uitzondering: RuntimeError: maximale recursiediepte overschreden. Python voorkomt dat je een functie maakt die in een nooit eindigende recursieve lus terechtkomt.
Lijsten afvlakken met recursie
Andere dingen die u kunt doen met recursie behalve faculteiten, laten we zeggen dat u een single wilt maken van een lijst die is genest, dit kan worden gedaan met behulp van de onderstaande code:
def flatten (a_list, flat_list = geen): if flat_list is none: flat_list = [] voor item in a_list: if isinstance (item, list): flatten (item, flat_list) else: flat_list.append (item) retourneer flat_list als __name__ == '__main__': genest = [1,2,3, [4,5], 6] x = afvlakken (genest) afdrukken (x)
Uitgang: [1,2,3,4,5,6]
Het uitvoeren van de bovenstaande code zal resulteren in een enkele lijst in plaats van een integer-lijst met een integer-lijst die we als invoer hebben gebruikt. Je kunt hetzelfde ook op andere manieren doen, Python heeft iets genaamd itertools.chain () je kunt de code controleren die wordt gebruikt voor het maken van een functieketen () het is een andere benadering om hetzelfde te doen als wij.
Voordelen van recursie
De code is schoon en elegant in een recursieve functie.
Een samengestelde taak kan met behulp van recursie worden opgesplitst in eenvoudiger deelproblemen.
Het genereren van een reeks is gemakkelijker met recursie dan met een geneste iteratie.
Nadelen van recursie
Het volgen van de logica achter de recursieve functie kan soms moeilijk zijn.
Recursieve oproepen zijn duur (inefficiënt) omdat ze veel geheugen en tijd in beslag nemen.
Recursieve functies zijn moeilijk te debuggen.
In dit artikel hebben we gezien wat recursie is en hoe we recursieve functies kunnen ontwikkelen vanuit de probleemstelling, hoe wiskundig een probleemstelling gedefinieerd kan worden. We hebben een probleem van de faculteit opgelost en de voorwaarden ontdekt die nodig zijn om faculteiten te vinden waaruit we die voorwaarden konden omzetten in python-code, waardoor je begrijpt hoe recursie werkt. Ik vind het netjes dat Python een ingebouwde limiet voor recursie heeft om te voorkomen dat ontwikkelaars slecht geconstrueerde recursieve functies maken. Een belangrijk ding om op te merken is dat recursie moeilijk te debuggen is omdat de functie zichzelf blijft aanroepen.