Vil du lære alt om rekursion i programmering? Denne vejledning om rekursion i Python hjælper dig med at komme i gang.
Rekursion er en super hjælpsom problemløsningsteknik til at tilføje til din programmørs værktøjskasse. Selvom det i starten ofte er svært at pakke dit hoved om, kan rekursion hjælpe dig med at finde mere elegante løsninger på komplekse problemer.
I denne tutorial tager vi en kode-først tilgang til at lære rekursion ved hjælp af Python. Vi vil især dække:
- Det grundlæggende i rekursion
- Rekursive funktioner og hvordan de virker
- Python implementering af rekursive funktioner
- Forskelle mellem iterative og rekursive tilgange til problemløsning
Lad os komme igang!
Indholdsfortegnelse
Hvad er rekursion?
Rekursion er en programmeringsteknik, hvor en funktion kalder sig selv gentagne gange for at løse et problem.
I sin kerne er rekursion en problemløsningstilgang, der involverer at nedbryde et komplekst problem i mindre, identiske delproblemer. Grundlæggende giver det dig mulighed for at løse et problem i form af enklere versioner af sig selv.
Så hvordan implementerer vi rekursion i kode? For at gøre det, lad os forstå, hvordan rekursive funktioner fungerer.
Forståelse af rekursive funktioner
Vi definerer en rekursiv funktion, der kalder sig selv inden for sin definition. Hvert rekursivt kald repræsenterer en mindre eller enklere version af det oprindelige problem.
For at sikre, at rekursionen til sidst afsluttes, skal rekursive funktioner omfatte et eller flere basistilfælde – betingelser, hvorunder funktionen holder op med at kalde sig selv og returnerer et resultat.
Lad os nedbryde dette yderligere. En rekursiv funktion består af:
- Grundtilfælde: Grundtilfældet er en tilstand (eller betingelser), der bestemmer, hvornår rekursionen skal stoppe. Når basistilfældet er opfyldt, returnerer funktionen et resultat uden at foretage yderligere rekursive kald. Et basistilfælde er afgørende for at forhindre uendelig rekursion.
- Rekursivt tilfælde: Det rekursive tilfælde definerer, hvordan problemet opdeles i mindre underproblemer. I denne del af funktionen kalder funktionen sig selv med modificerede input. Hvert rekursivt opkald er derfor et skridt i retning af at nå basissagen.
Lad os derefter diskutere, hvad der sker, når du kalder en rekursiv funktion.
Hvordan rekursion virker under hætten
Når en funktion kaldes, placeres en registrering af dens eksekveringskontekst på opkaldsstakken. Denne post indeholder oplysninger om funktionens argumenter, lokale variabler og den placering, der skal returneres, når funktionen er færdig med at udføre.
I tilfælde af rekursive funktioner, når en funktion kalder sig selv, skubbes en ny post ind på opkaldsstakken, hvilket effektivt suspenderer den aktuelle funktions udførelse. Stakken giver Python mulighed for at holde styr på alle afventende funktionskald, inklusive dem fra rekursive kald.
Indtil basistilfældet er nået, fortsætter rekursionen. Når basissagen returnerer et resultat, løses funktionskaldene et efter et – hvor hver funktion returnerer sit resultat til det forrige niveau af opkaldsstakken. Denne proces fortsætter, indtil det indledende funktionskald er fuldført.
Implementering af rekursion i Python
I dette afsnit vil vi udforske tre enkle eksempler på rekursion:
For hvert eksempel vil vi angive problemet, levere den rekursive Python-implementering og derefter forklare, hvordan den rekursive implementering fungerer.
#1. Faktoriel beregning ved hjælp af rekursion
Opgave: Beregn faktortallet for et ikke-negativt heltal n, angivet som n!. Matematisk er fakultetet af et tal n produktet af alle positive heltal fra 1 til n.
Faktorberegningen egner sig godt til rekursion, som vist:
Her er den rekursive funktion til at beregne fakultetet af et givet tal n:
def factorial(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case: n! = n * (n-1)!
else:
return n * factorial(n - 1)
Lad os beregne 5! ved at bruge funktionen factorial():
factorial_5 = factorial(5) print(factorial(5)) # Output: 120
Lad os nu se, hvordan funktionen fungerer:
- Vi har et grundtilfælde, der kontrollerer, om n er lig med 0 eller 1. Hvis betingelsen er opfyldt, returnerer funktionerne 1. Husk at 0! er 1, og det er 1 også!.
- Hvis n er større end 1, beregner vi n! ved at gange n med faktoren n-1. Dette er udtrykt som n * factorial(n – 1).
- Funktionen bliver ved med at foretage rekursive opkald med faldende værdier på n, indtil den når basissagen.
#2. Fibonacci-tal med rekursion
Problem: Find termen ved det n-te indeks i Fibonacci sekvens. Fibonacci-sekvensen er defineret som følger: F(0) = 0, F(1) = 1, og F(n) = F(n-1) + F(n-2) for n >= 2.
def fibonacciSeq(n):
# Base cases
if n == 0:
return 0
elif n == 1:
return 1
# Recursion: F(n) = F(n-1) + F(n-2)
else:
return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)
Lad os køre funktionen:
fib_5 = fibonacciSeq(5) print(fib_5) # Output: 5
Sådan fungerer funktionen:
- Lad os starte med at diskutere basissagen. Hvis n er 0, returnerer det 0. Og hvis n er 1, returnerer det 1. Hent F(0) = 0 og F(1) = 1.
- I det rekursive tilfælde, hvis n er større end 1, beregner funktionen F(n) ved at tilføje F(n-1) og F(n-2) led. Dette udtrykkes som fibonacciSeq(n – 1) + fibonacciSeq(n – 2).
- Funktionen bliver ved med at foretage rekursive opkald med faldende værdier på n, indtil den når basistilfældene.
#3. Rekursiv implementering af binær søgning
Problem: Implementer en binær søgealgoritme ved hjælp af rekursion for at finde placeringen af et målelement i en sorteret liste.
Her er den rekursive implementering af binær søgning:
def binarySearch(arr, target, low, high):
# Base case: target not found
if low > high:
return -1
mid = (low + high) // 2
# Base case: target found
if arr[mid] == target:
return mid
# Recursive case: search left or right half of the array
elif arr[mid] > target:
return binarySearch(arr, target, low, mid - 1)
else:
return binarySearch(arr, target, mid + 1, high)
Funktionen binarySearch bliver ved med at dele søgeintervallet i to med hvert rekursivt kald, indtil den enten finder målet eller bestemmer, at målet ikke er på listen.
Her er et eksempel på funktionen:
arr = [5, 8, 13, 24, 37, 49, 51, 64, 72, 88, 96] target = 37 idx = binarySearch(arr, target, 0, len(arr)-1) print(idx) # Output: 4
Lad os nedbryde, hvad funktionen gør:
- I den rekursive binære søgningsimplementering har vi to basistilfælde. For det første, hvis lav bliver større end høj, betyder det, at målelementet ikke er på listen. Så vi returnerer -1 for at indikere, at målet ikke blev fundet.
- Den anden basiscase kontrollerer, om elementet i det midterste indeks midt i det aktuelle søgeinterval er lig med målet. Hvis de matcher, returnerer vi indekset midt, hvilket indikerer, at vi har fundet målet.
- I det rekursive tilfælde, hvis det midterste element er større end målet, søger vi rekursivt i venstre halvdel af arrayet ved at kalde binarySearch(arr, target, low, mid – 1). Hvis det midterste element er mindre end målet, søger vi efter den højre halvdel ved at kalde binarySearch(arr, target, mid + 1, high).
Rekursiv vs. Iterativ tilgang
Iterativ tilgang – ved hjælp af loops – er en anden almindelig tilgang til problemløsning. Så hvordan adskiller det sig fra rekursion? Lad os finde ud af det.
Først sammenligner vi rekursive og iterative løsninger på et almindeligt problem: beregning af et tals fakultet.
Her er den rekursive implementering af faktorberegning:
def factorialRec(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case: n! = n * (n-1)!
else:
return n * factorial(n - 1)
Fordi vi ved, at fakultetet af et ikke-negativt tal er produktet af alle tal fra 1 op til n, kan vi også skrive en iterativ implementering ved hjælp af loops.
def factorialIter(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
Begge disse implementeringer giver identiske resultater.
factorial_5 = factorialRec(5) print(factorial_5) # Output: 120 factorial_5 = factorialIter(5) print(factorial_0) # Output: 120
Men foretrækkes en iterativ tilgang frem for rekursion? Når der er dyb rekursion – med for mange funktionskald – kan du løbe ind i fejl på grund af overskridelse af rekursionsdybden. Looping er en bedre mulighed for problemer, hvis rekursive implementering kræver for mange funktionskald for at nå basissagen.
Lad os opsummere forskellene mellem iterative og rekursive implementeringer:
FeatureRecursive ApproachIterative ApproachStructureBruger rekursive funktionskald og er afhængig af opkaldsstakken.Bruger loops til iteration uden yderligere funktionskald.Base CasesKræver eksplicitte basiscases for at stoppe rekursionen.Anvender typisk looping-betingelser til terminering.Ydeevne kan være mindre hukommelseseffektiv på grund af opkaldsstakken . Dyb rekursion kan nogle gange føre til stak overløbsfejl. Generelt mere hukommelseseffektiv og mindre tilbøjelig til stak overløbsfejl. FejlretningKan være udfordrende at fejlfinde på grund af flere funktionskald og indlejrede udførelseskontekster. Typisk nemmere at debugge på grund af et ligetil lineært udførelsesflow .Iterativ vs rekursiv tilgang
Konklusion
I denne artikel startede vi med at lære, hvad rekursion er, og hvordan man definerer rekursive funktioner med basistilfælde og gentagelsesrelationer.
Vi skrev derefter noget Python-kode – rekursive implementeringer af almindelige programmeringsproblemer. Til sidst lærte vi forskellene mellem iterative og rekursive tilgange og fordele og ulemper ved hver af disse tilgange.
Tjek derefter denne liste over Python-interviewspørgsmål.