Har du någonsin fastnat i en till synes oändlig cykel där ett problem fortsätter att förgrenas i mindre fragment?
Om så är fallet kan du ha kommit till den fängslande världen av rekursion. Även om det kan tyckas vara svårt att förstå, oroa dig inte! I det här inlägget går vi på en intressant resa för att lära oss om typer av rekursioner.
Så spänn fast dig när vi utforskar många rekursiva tillvägagångssätt. Förbered dig på att gå in i rekursionens fascinerande värld och observera dess anmärkningsvärda förmåga att lösa komplicerade problem.
Vad är egentligen rekursioner?
I grundläggande ord är rekursion en kraftfull programmeringsteknik som inkluderar en funktion som anropar sig själv under exekvering. Det är som att stirra in i en spegel och se en bild inuti en bild, vilket resulterar i en självrefererande cykel.
Vi kan ta itu med stora problem med hjälp av rekursion genom att dela upp dem i mindre, mer hanterbara delproblem.
Det liknar att sätta ihop en sticksåg, där en del länkar till andra delar för att skapa en helhetsbild. Rekursion låter oss lösa problem på ett elegant och effektivt sätt genom att upprepa samma uppsättning instruktioner med olika input.
1-direkt rekursion
Direkt rekursion är den mest grundläggande typen av rekursion, där en funktion anropar sig själv direkt. Det innebär att man delar upp ett problematiskt problem i mindre delproblem tills ett basfall uppnås, vilket leder till uppsägning.
Den rekursiva funktionen anropar sig själv med olika ingångar, vilket gör att exekveringen av samma uppsättning instruktioner kan upprepas. Varje anrop bygger på det föregående och närmar sig gradvis basfallet som gör att rekursion tar slut.
Låt oss kolla detta exempel.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
Produktion:
5
4
3
2
1
2-Indirekt rekursion
Indirekt rekursion lägger till en spännande twist till den rekursiva vägen. Till skillnad från direkt rekursion, som innebär att en funktion uttryckligen anropar sig själv, inkluderar indirekt rekursion en kedja av funktionsanrop.
En funktion anropar en annan, som sedan kan anropa den ursprungliga funktionen eller någon annan funktion som slutligen går tillbaka till originalet. Denna sammanlänkade väv av funktionsanrop producerar en fängslande dans där flera funktioner samverkar för att lösa ett problem.
Exempelvis:
def function_A(n):
if n > 0:
print("A:", n)
function_B(n - 1)
def function_B(n):
if n > 0:
print("B:", n)
function_A(n - 1)
function_A(3)
Produktion:
A: 3
B: 2
A: 1
3-linjär rekursion
Överväg en resa längs en rak rutt, ett steg i taget, tills du når ditt mål. Denna sekventiella teknik förkroppsligas av linjär rekursion, där en funktion utför ett enda rekursivt anrop i varje funktionsiteration.
Med varje rekursivt anrop flyttas den rekursiva processen närmare ett basfall genom att sänka problemets storlek. Det fortsätter på ett tydligt och linjärt sätt och löser delproblem ett i taget tills det slutgiltiga svaret nås.
Exempelvis:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
Produktion:
120
4-träd rekursion
När en funktion förgrenas till flera rekursiva anrop kommer vi in i trädrekursionens värld. En funktion i trädrekursion genererar många rekursiva anrop, som vart och ett löser ett separat delproblem, precis som grenarna i ett träd gör.
Denna förgreningsstruktur möjliggör samtidig undersökning av flera rutter, vilket effektivt bryter ner komplicerade problem i mindre, relaterade komponenter.
Exempelvis:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
Produktion:
8
5-kapslade rekursion
Kapslad rekursion tillför en spännande grad av komplexitet till det rekursiva universum. I denna form av rekursion inkorporerar en funktion ett rekursivt anrop som ett argument inom ett annat rekursivt anrop.
Det inre rekursiva anropet verkar på ett värde som är beroende av det yttre rekursiva anropet. Komplexiteten växer med varje kapslad anrop, och kulminerar i ett spännande mönster av kapslade rekursiva anrop.
Exempelvis:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Resultat:
91
6-svansrekursion
Svansrekursion är en optimeringsteknik för rekursiva algoritmer som kan förbättra deras prestanda. Det rekursiva anropet visas som den slutliga åtgärden av en funktion med svansrekursion, att göra.
Eftersom det inte finns några utestående operationer efter det rekursiva anropet, kan kompilatorn eller tolken förenkla rekursionen genom att ersätta den med ett enkelt hopp.
Denna optimeringsmetod, känd som tail call optimization, minskar kravet på att varje rekursivt anrop ska behålla en stackram, vilket resulterar i ökad hastighet och lägre minnesanvändning.
Exempelvis:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Ut ut:
120
7-icke-svansrekursion
Till skillnad från svansrekursion innebär icke-svansrekursion extra aktiviteter som utförs efter det rekursiva anropet inom en funktion. Innan fler åtgärder kan utföras måste varje rekursivt anrop slutföras och återkomma.
Som en konsekvens, tills basfallet uppnås och rekursionen slutar, upprätthålls en stapel av utestående operationer. Icke-svansrekursion använder ofta mer minne och är mindre effektiv än svansrekursion, men det är fortfarande ett användbart verktyg för att ta itu med en mängd olika problem.
Exempelvis:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
Produktion:
15
Sammanfatta
Rekursion är ett spännande koncept inom programmering. Det tillåter oss att tackla komplicerade problem på ett rekursivt, självreferensiellt sätt.
Det erbjuder en distinkt metod för att tänka på och lösa problem, bryta ner dem i mindre, mer hanterbara bitar. När du arbetar med rekursion är det dock viktigt att använda uppmärksamma några punkter.
Du bör identifiera lämpliga basfall som gör att rekursionen tar slut. Om de inte är närvarande kan funktionen fortsätta att kalla sig för alltid.
För det andra, baserat på det aktuella scenariot, kan valet av lämplig typ av rekursion leda till mer effektiva och eleganta lösningar. Försök hitta vad som fungerar bäst för problemet i handen. När du arbetar med stora rekursionsdjup, var medveten om potentiella faror som stackoverflow.
Kommentera uppropet