Med enkla ord är rekursion ett sätt att lösa problemet genom att ha en funktion som kallar sig själv, Ordet “ rekursiv ”Härstammar från det latinska verbet” upprepas ”, Vilket innebär att göra om något. Detta är vad den rekursiva funktionen gör, den gör om samma sak om och om igen, dvs den påminner om sig själv. I den här artikeln lär vi oss om rekursion i python. Följande är ämnen som tas upp i den här bloggen:
- Vad är rekursion i Python?
- Uppsägningsvillkor
- Pythons rekursionsgräns
- Platta listor med rekursion
- Fördelar med rekursion
- Nackdelar med rekursion
Vad är rekursion i Python?
Rekursion är processen att bestämma något i termer av sig själv. Vi vet att i Python kan vilken funktion som helst kalla någon annan funktion, en funktion kan också anropa sig själv. Dessa typer av funktioner som kallar sig själva tills det vissa villkoret inte är uppfyllt betecknas som rekursiva funktioner.
låt oss ta några exempel för att se hur det fungerar. Om du får ett positivt heltal n skulle faktorn vara.
- n! = n * (n-1) * (n-2) och så vidare.
- 2! = 2 * (2-1)
- ett! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Att ersätta ovanstående värden kommer att resultera i följande uttryck
- 4! = 4 * 3 * 2 * 1
Vi måste definiera en funktion låter oss säga fakta (n) som tar positivt heltal eller 0 som sin parameter och returnerar den n: e faktorn, hur kan vi göra det med rekursion?
Låt oss se, för att göra det med rekursion måste vi undersöka följande ekvation
n! = n. (n-1). (n-2) & hellip3.2.1
n! = n. (n-1)! # vi kan skriva om ovanstående uttalande som på den här raden
Nu här om vi passerar 2 som parameter får vi:
2! = 2,1! = 2
På samma sätt, om vi passerar 1 får vi:
ett! = 1,0! = 1
Men om vi passerar 0 går det sönder
0! = 0. (- 1)! och här definieras inte faktor för -1 så det fungerar bara för värden> 0
Så vi måste skriva två fall
1. n! = n. (n-1)! om n> = 1
2. 1 om n = 0
Detta är en komplett lösning för alla positiva heltal och 0.
Uppsägningsvillkor
En rekursiv funktion måste uppfylla ett viktigt villkor för att avslutas. När vi går mot ett tillstånd där problemet kan lösas utan ytterligare rekursion kommer en rekursiv funktion att avslutas, vilket minimerar problemet till de mindre delstegen. En rekursion kan hamna i en oändlig slinga om villkoret för uppsägning inte uppfylls i samtalen.
Faktiska förhållanden:
- faktor av n = n * (n-1) så länge n är större än 1.
- 1 om n = 0
Vi kommer att konvertera ovanstående faktorvillkor i pythonkod:
def fact (n): om n == 1: returnera annat: returnera n * fact (n-1)
Låt oss ta ett exempel, säga att vi vill hitta en faktor av 4:
fakta (4) # detta kommer att returnera 4 * fakta (3) och så vidare tills n == 1.
Produktion: 24
Det används så ofta som ett exempel för rekursion på grund av dess enkelhet och tydlighet. Lösa mindre förekomster av ett problem i varje steg som det kallades rekursion inom datavetenskap.
Pythons rekursionsgräns
På vissa språk kan du skapa en oändlig rekursiv slinga men i Python finns det en rekursionsgräns. För att kontrollera gränsen kör du följande funktion från sys-modulen. vilket ger gränsen för rekursionsuppsättningen för python.
lägg till två nummer i java
importera sys sys.getrecursionlimit ()
Produktion: 1000
Du kan också ändra gränsen med sys-modulens funktioner setrecursionlimit () enligt ditt krav. Nu ska vi skapa en funktion som kallar sig rekursivt tills den överskrider gränsen och kontrollerar vad som händer:
def rekursiv (): rekursiv () om __namn__ == '__main__': rekursiv ()
Om du kör ovanstående kod får du ett undantag för runtime: RuntimeError: maximalt rekursionsdjup överskridits. Python hindrar dig från att skapa en funktion som hamnar i en oändlig rekursiv slinga.
Platta listor med rekursion
Andra saker du kan göra med rekursion förutom faktum, låt oss säga att du vill skapa singel från en lista som är kapslad, det kan göras med hjälp av koden nedan:
def platta (a_list, flat_list = none): om flat_list är ingen: flat_list = [] för objekt i a_list: om ärinstans (objekt, lista): platta (objekt, flat_list) annat: flat_list.append (objekt) returnera flat_list om __name__ == '__main__': kapslad = [1,2,3, [4,5], 6] x = platta (kapslade) tryck (x)
Produktion: [1,2,3,4,5,6]
Att köra ovanstående kod kommer att resultera i en enda lista istället för heltalslista som innehåller heltalslista som vi använde som ingång. Du kan också göra samma sak på andra sätt, Python har något som heter itertools.chain () du kan kontrollera koden som används för att skapa en funktionskedja () det är en annan metod att göra samma sak som vi gjorde.
Fördelar med rekursion
Koden är ren och elegant i en rekursiv funktion.
En sammansatt uppgift kan delas upp i enklare delproblem med rekursion.
Att generera sekvens är lättare med rekursion än att använda någon kapslad iteration.
Nackdelar med rekursion
Att följa logiken bakom rekursiv funktion kan vara svår ibland.
Rekursiva samtal är dyra (ineffektiva) eftersom de tar upp mycket minne och tid.
Rekursiva funktioner är svåra att felsöka.
I den här artikeln såg vi vad rekursion är och hur kan vi utveckla rekursiva funktioner från problemuttaget, hur matematiskt ett problemuttal kan definieras. Vi löste ett fakturaproblem och fick reda på de förutsättningar som krävs för att hitta fakta som vi kunde omvandla dessa villkor till pythonkod för att ge dig en förståelse för hur rekursion fungerar. Jag tycker att det är snyggt att Python har en inbyggd gräns för rekursion för att hindra utvecklare från att skapa dåligt konstruerade rekursiva funktioner. En viktig sak att lägga märke till är att rekursion är svår att felsöka eftersom funktionen fortsätter att ringa sig själv.