Med enkle ord er rekursion en måde at løse problemet på ved at lade en funktion kalde sig selv, ordet “ rekursiv ”Stammer fra det latinske verbum“ gentage sig ”, Hvilket betyder at gøre noget igen. Dette er hvad den rekursive funktion gør, den gentager det samme igen og igen, dvs. det minder om sig selv. I denne artikel lærer vi om rekursion i python. Følgende er de emner, der er dækket af denne blog:
- Hvad er rekursion i Python?
- Opsigelsesbetingelse
- Pythons rekursionsgrænse
- Fladlister med rekursion
- Fordele ved rekursion
- Ulemper ved rekursion
Hvad er rekursion i Python?
Rekursion er processen med at bestemme noget i forhold til sig selv. Vi ved, at i Python kan enhver funktion kalde enhver anden funktion, en funktion kan også kalde sig selv. Disse typer af funktioner, der kalder sig selv, indtil den bestemte betingelse ikke er opfyldt, betegnes som rekursive funktioner.
lad os tage et par eksempler for at se, hvordan det fungerer. Hvis du får et positivt heltal n, ville det faktiske være.
- n! = n * (n-1) * (n-2) og så videre.
- 2! = 2 * (2-1)
- en! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Udskiftning af ovenstående værdier resulterer i følgende udtryk
- 4! = 4 * 3 * 2 * 1
Vi er nødt til at definere en funktion lader sig sige fakta (n), der tager positivt heltal eller 0 som sin parameter og returnerer den nende faktor, hvordan kan vi gøre det ved hjælp af rekursion?
Lad os se, for at gøre det ved hjælp af rekursion er vi nødt til at undersøge følgende ligning
n! = n. (n-1). (n-2) & hellip3.2.1
n! = n. (n-1)! # vi kan omskrive ovenstående udsagn som på denne linje
Nu her, hvis vi passerer 2 som parameter, får vi:
2! = 2,1! = 2
hvordan man opretter en singleton-klasse i java
Tilsvarende, hvis vi passerer 1, får vi:
en! = 1,0! = 1
Men hvis vi passerer 0, går det i stykker
0! = 0. (- 1)! og her er faktor for -1 ikke defineret, så dette fungerer kun for værdier> 0
Så vi er nødt til at skrive to sager
1. n! = n. (n-1)! hvis n> = 1
2. 1 hvis n = 0
Dette er en komplet løsning til alle positive heltal og 0.
Opsigelsesbetingelse
En rekursiv funktion skal opfylde en vigtig betingelse for at afslutte. Når vi bevæger os mod en tilstand, hvor problemet kan løses uden yderligere rekursion, afsluttes en rekursiv funktion, hvilket minimerer problemet i de mindre deltrin. En rekursion kan ende i en uendelig løkke, hvis betingelsen for opsigelse ikke er opfyldt i opkaldene.
Faktiske forhold:
- faktor af n = n * (n-1) så længe n er større end 1.
- 1 hvis n = 0
Vi konverterer ovenstående faktorforhold i python-kode:
def fact (n): hvis n == 1: returnere andet: returnere n * fact (n-1)
Lad os tage et eksempel og sige, at vi vil finde en faktor 4:
faktum (4) # dette returnerer 4 * faktum (3) og så videre indtil n == 1.
Produktion: 24
Det bruges så ofte som et eksempel til rekursion på grund af dets enkelhed og klarhed. Løsning af mindre forekomster af et problem ved hvert trin kaldte det rekursion inden for datalogi.
Pythons rekursionsgrænse
På nogle sprog kan du oprette en uendelig rekursiv sløjfe, men i Python er der en rekursionsgrænse. For at kontrollere grænsen skal du køre følgende funktion fra sys-modulet. hvilket giver grænsen for rekursionssættet for python.
java konvertere dobbelt til int
importer sys sys.getrecursionlimit ()
Produktion: 1000
Du kan også ændre grænsen ved hjælp af sys-modulets funktionssætrecursionlimit () i henhold til dit krav. Lad os nu oprette en funktion, der kalder sig rekursivt, indtil den overskrider grænsen og kontrollerer, hvad der sker:
def rekursiv (): rekursiv () hvis __navn__ == '__main__': rekursiv ()
Hvis du kører ovenstående kode, får du en runtime-undtagelse: RuntimeError: maksimal rekursionsdybde overskredet. Python forhindrer dig i at oprette en funktion, der ender i en uendelig rekursiv sløjfe.
Fladlister med rekursion
Andre ting, du kan gøre ved hjælp af rekursion bortset fra fakta, lad os sige, at du vil oprette single fra en liste, der er indlejret, det kan gøres ved hjælp af koden nedenfor:
def flad (a_list, flat_list = none): hvis flat_list ikke er: flat_list = [] for element i a_list: hvis isinstance (item, list): flad (item, flat_list) ellers: flat_list.append (item) return flat_list if __name__ == '__main__': indlejret = [1,2,3, [4,5], 6] x = flad (indlejret) print (x)
Produktion: [1,2,3,4,5,6]
Kørsel af ovenstående kode resulterer i en enkelt liste i stedet for heltalsliste, der indeholder heltalsliste, som vi brugte som input. Du kan også gøre det samme på andre måder, Python har noget, der hedder itertools.chain (), du kan kontrollere koden, der bruges til at oprette en funktionskæde (), det er en anden tilgang at gøre det samme som vi gjorde.
Fordele ved rekursion
Koden er ren og elegant i en rekursiv funktion.
En sammensat opgave kan opdeles i enklere delproblemer ved hjælp af rekursion.
Generering af sekvens er lettere med rekursion end ved brug af indlejret iteration.
Ulemper ved rekursion
Det kan være svært at følge logikken bag rekursiv funktion nogle gange.
Rekursive opkald er dyre (ineffektive), da de tager meget hukommelse og tid.
Rekursive funktioner er svære at fejle.
I denne artikel så vi, hvad rekursion er, og hvordan kan vi udvikle rekursive funktioner ud fra problemstillingen, hvor matematisk en problemstilling kan defineres. Vi løste et problem med faktoriet og fandt ud af de betingelser, der kræves for at finde fakta, hvorfra vi var i stand til at konvertere disse betingelser til python-kode, hvilket giver dig forståelsen af, hvordan rekursion fungerer. Jeg synes det er pænt, at Python har en indbygget grænse for rekursion for at forhindre udviklere i at oprette dårligt konstruerede rekursive funktioner. En vigtig ting at bemærke er, at rekursion er svært at fejle, da funktionen fortsætter med at kalde sig selv.