Ønsker du å utforske rekursjonens verden innenfor programmering? Denne veiledningen i rekursjon med Python vil hjelpe deg i gang.
Rekursjon er en usedvanlig nyttig teknikk for å løse problemer som enhver programmerer bør ha i sin verktøykasse. Til tross for at det kan være litt utfordrende å forstå i begynnelsen, kan rekursjon bidra til å utvikle mer elegante løsninger på komplekse problemstillinger.
I denne opplæringen vil vi ta i bruk en kode-først tilnærming for å lære om rekursjon ved hjelp av Python. Vi skal spesielt gå gjennom følgende punkter:
- Grunnleggende om rekursjon
- Rekursive funksjoner og hvordan de fungerer
- Implementering av rekursive funksjoner i Python
- Forskjeller mellom iterative og rekursive metoder for problemløsning
La oss starte!
Hva er rekursjon?
Rekursjon er en programmeringsmetode hvor en funksjon gjentatte ganger kaller seg selv for å løse et bestemt problem.
Kjernen i rekursjon ligger i en problemløsningsstrategi som innebærer å bryte et komplisert problem ned i mindre, likeartede delproblemer. I praksis lar dette deg løse et problem ved å bruke enklere versjoner av selve problemet.
Så, hvordan implementerer vi rekursjon i kode? For å forstå dette, la oss se nærmere på hvordan rekursive funksjoner opererer.
Forstå rekursive funksjoner
Vi definerer en rekursiv funksjon som en funksjon som kaller seg selv inne i sin egen definisjon. Hvert rekursive kall representerer en mindre eller enklere versjon av det opprinnelige problemet.
For å sikre at rekursjonen en gang stopper, må rekursive funksjoner inneholde ett eller flere basistilfeller – betingelser hvor funksjonen slutter å kalle seg selv og i stedet returnerer et resultat.
La oss utdype dette videre. En rekursiv funksjon består av:
- Basistilfelle: Et basistilfelle er en tilstand (eller flere tilstander) som bestemmer når rekursjonen skal avsluttes. Når basistilfellet er oppnådd, returnerer funksjonen et resultat uten å utføre flere rekursive kall. Et basistilfelle er avgjørende for å forhindre uendelig rekursjon.
- Rekursivt tilfelle: Det rekursive tilfellet beskriver hvordan problemet skal deles opp i mindre delproblemer. I denne delen av funksjonen kaller funksjonen seg selv med endrede inndata. Hvert rekursive kall bringer oss dermed nærmere basistilfellet.
La oss nå se på hva som skjer når du kaller en rekursiv funksjon.
Hvordan rekursjon fungerer i bakgrunnen
Når en funksjon kalles, lagres en oversikt over dens utførelseskontekst på anropsstakken. Denne oversikten inneholder informasjon om funksjonens argumenter, lokale variabler, samt hvor funksjonen skal returnere når den er ferdig.
I tilfelle av rekursive funksjoner, når en funksjon kaller seg selv, plasseres en ny oversikt på anropsstakken, som midlertidig stanser utførelsen av den nåværende funksjonen. Stakken gjør det mulig for Python å holde oversikt over alle pågående funksjonskall, inkludert de fra rekursive kall.
Rekursjonen fortsetter inntil basistilfellet er nådd. Når basistilfellet returnerer et resultat, blir funksjonskallene avviklet ett etter ett – der hver funksjon returnerer sitt resultat til det forrige nivået i anropsstakken. Denne prosessen fortsetter helt til det første funksjonskallet er avsluttet.
Implementering av rekursjon i Python
I denne delen skal vi se på tre enkle eksempler på rekursjon:
- Beregning av fakultetet til et tall
- Beregning av Fibonacci-tall
- Implementering av binærsøk ved hjelp av rekursjon
For hvert eksempel skal vi definere problemet, presentere den rekursive Python-implementasjonen, og forklare hvordan den rekursive implementeringen fungerer.
#1. Fakultetsberegning ved bruk av rekursjon
Oppgave: Beregn fakultetet til et ikke-negativt heltall n, betegnet som n!. Matematisk sett er fakultetet til et tall n lik produktet av alle positive heltall fra 1 til n.
Fakultetsberegning er velegnet for rekursjon, som illustrert her:
Her er den rekursive funksjonen for å beregne fakultetet til et gitt tall n:
def factorial(n):
# Basistilfelle
if n == 0 or n == 1:
return 1
# Rekursivt tilfelle: n! = n * (n-1)!
else:
return n * factorial(n - 1)
La oss beregne 5! ved å bruke funksjonen `factorial()`:
factorial_5 = factorial(5)
print(factorial(5))
# Output: 120
La oss nå undersøke hvordan funksjonen fungerer:
- Vi har et basistilfelle som sjekker om n er lik 0 eller 1. Hvis betingelsen oppfylles, returnerer funksjonen 1. Husk at 0! er 1, og det samme gjelder for 1!.
- Dersom n er større enn 1, beregner vi n! ved å multiplisere n med fakultetet av n-1. Dette uttrykkes som n * factorial(n – 1).
- Funksjonen fortsetter å utføre rekursive kall med reduserende verdier av n inntil den når basistilfellet.
#2. Fibonacci-tall med rekursjon
Oppgave: Finn tallet ved den n-te indeksen i Fibonacci-sekvensen. Fibonacci-sekvensen er definert slik: F(0) = 0, F(1) = 1, og F(n) = F(n-1) + F(n-2) for n >= 2.
def fibonacciSeq(n):
# Basistilfeller
if n == 0:
return 0
elif n == 1:
return 1
# Rekursjon: F(n) = F(n-1) + F(n-2)
else:
return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)
La oss kjøre funksjonen:
fib_5 = fibonacciSeq(5)
print(fib_5)
# Output: 5
Slik fungerer funksjonen:
- La oss begynne med å se på basistilfellene. Hvis n er 0, returnerer den 0. Hvis n er 1, returnerer den 1. Dette tilsvarer F(0) = 0 og F(1) = 1.
- I det rekursive tilfellet, dersom n er større enn 1, beregner funksjonen F(n) ved å legge sammen F(n-1) og F(n-2). Dette uttrykkes som fibonacciSeq(n – 1) + fibonacciSeq(n – 2).
- Funksjonen fortsetter å utføre rekursive kall med reduserende verdier av n inntil den når basistilfellene.
#3. Rekursiv implementering av binærsøk
Oppgave: Implementer en binær søkealgoritme ved hjelp av rekursjon for å finne posisjonen til et bestemt element i en sortert liste.
Her er den rekursive implementeringen av binærsøk:
def binarySearch(arr, target, low, high):
# Basistilfelle: målet ikke funnet
if low > high:
return -1
mid = (low + high) // 2
# Basistilfelle: målet funnet
if arr[mid] == target:
return mid
# Rekursivt tilfelle: søk i venstre eller høyre halvdel av listen
elif arr[mid] > target:
return binarySearch(arr, target, low, mid - 1)
else:
return binarySearch(arr, target, mid + 1, high)
Funksjonen `binarySearch` fortsetter å dele søkeintervallet i to for hvert rekursive kall, inntil den enten finner målet eller fastslår at målet ikke finnes i listen.
Her er et eksempel på hvordan funksjonen brukes:
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
La oss gå gjennom hva funksjonen gjør:
- I den rekursive binære søk-implementeringen har vi to basistilfeller. For det første, dersom `lav` blir større enn `høy`, betyr det at målet ikke er tilstede i listen. Vi returnerer derfor -1 for å signalisere at målet ikke ble funnet.
- Det andre basistilfellet sjekker om elementet ved midterste indeksen, `mid`, i det gjeldende søkeintervallet, er lik målet. Hvis de er like, returnerer vi `mid`-indeksen, som viser at vi har funnet målet.
- I det rekursive tilfellet, dersom det midterste elementet er større enn målet, søker vi rekursivt i venstre halvdel av listen ved å kalle `binarySearch(arr, target, low, mid – 1)`. Hvis det midterste elementet er mindre enn målet, søker vi i høyre halvdel ved å kalle `binarySearch(arr, target, mid + 1, high)`.
Rekursiv vs. iterativ tilnærming
En iterativ tilnærming – bruk av løkker – er en annen vanlig metode for problemløsning. Men hvordan skiller den seg fra rekursjon? La oss finne det ut.
Vi starter med å sammenligne rekursive og iterative løsninger på et kjent problem: beregning av fakultetet til et tall.
Her er den rekursive implementeringen for å beregne fakultet:
def factorialRec(n):
# Basistilfelle
if n == 0 or n == 1:
return 1
# Rekursivt tilfelle: n! = n * (n-1)!
else:
return n * factorial(n - 1)
Siden vi vet at fakultetet til et ikke-negativt tall er produktet av alle tall fra 1 opp til n, kan vi også skrive en iterativ implementering ved hjelp av løkker.
def factorialIter(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
Begge disse implementeringene gir identiske resultater.
factorial_5 = factorialRec(5)
print(factorial_5)
# Output: 120
factorial_5 = factorialIter(5)
print(factorial_0)
# Output: 120
Men er en iterativ tilnærming foretrukket fremfor rekursjon? Ved dyp rekursjon – altså mange funksjonskall – kan du oppleve feil på grunn av at rekursjonsdybden overskrides. Løkker er et bedre alternativ for problemer der en rekursiv implementering krever for mange funksjonskall for å nå basistilfellet.
La oss oppsummere forskjellene mellom iterative og rekursive implementeringer:
| Funksjon | Rekursiv Tilnærming | Iterativ Tilnærming |
| Struktur | Bruker rekursive funksjonskall og er avhengig av anropsstakken. | Bruker løkker for iterasjon uten ekstra funksjonskall. |
| Basistilfeller | Krever eksplisitte basistilfeller for å stoppe rekursjonen. | Bruker typisk løkke-betingelser for terminering. |
| Ytelse | Kan være mindre minneeffektiv på grunn av anropsstakken. Dyp rekursjon kan føre til stabeloverløpsfeil. | Generelt mer minneeffektivt og mindre utsatt for stabeloverløpsfeil. |
| Feilsøking | Kan være vanskelig å feilsøke på grunn av flere funksjonskall og nestede utførelseskontekster. | Vanligvis lettere å feilsøke på grunn av en enkel lineær utførelsesflyt. |
Konklusjon
I denne artikkelen startet vi med å lære hva rekursjon er og hvordan man definerer rekursive funksjoner med basistilfeller og rekursjonsrelasjoner.
Vi har deretter skrevet litt Python-kode – rekursive implementeringer av vanlige programmeringsproblemer. Til slutt har vi sett på forskjellene mellom iterative og rekursive tilnærminger, samt fordeler og ulemper ved hver av dem.
Du kan gjerne sjekke ut denne listen over Python-intervjuspørsmål for videre læring.