Vil du lære alt om rekursjon i programmering? Denne opplæringen om rekursjon i Python hjelper deg med å komme i gang.
Rekursjon er en super nyttig problemløsningsteknikk for å legge til programmererens verktøykasse. Selv om det i utgangspunktet ofte er vanskelig å vikle hodet rundt, kan rekursjon hjelpe deg med å finne mer elegante løsninger på komplekse problemer.
I denne opplæringen tar vi en kode-første tilnærming til å lære rekursjon ved hjelp av Python. Spesielt vil vi dekke:
- Grunnleggende om rekursjon
- Rekursive funksjoner og hvordan de fungerer
- Python-implementering av rekursive funksjoner
- Forskjeller mellom iterative og rekursive tilnærminger til problemløsning
La oss komme i gang!
Innholdsfortegnelse
Hva er rekursjon?
Rekursjon er en programmeringsteknikk der en funksjon kaller seg selv gjentatte ganger for å løse et problem.
I kjernen er rekursjon en problemløsende tilnærming som innebærer å bryte ned et komplekst problem i mindre, identiske delproblemer. I hovedsak lar det deg løse et problem i form av enklere versjoner av seg selv.
Så hvordan implementerer vi rekursjon i kode? For å gjøre det, la oss forstå hvordan rekursive funksjoner fungerer.
Forstå rekursive funksjoner
Vi definerer en rekursiv funksjon som kaller seg selv innenfor sin definisjon. Hvert rekursivt anrop representerer en mindre eller enklere versjon av det opprinnelige problemet.
For å sikre at rekursjonen til slutt avsluttes, må rekursive funksjoner inkludere ett eller flere grunntilfeller – betingelser der funksjonen slutter å kalle seg selv og returnerer et resultat.
La oss bryte ned dette ytterligere. En rekursiv funksjon består av:
- Grunntilfelle: Grunntilfellet er en tilstand (eller tilstander) som bestemmer når rekursjonen skal stoppe. Når grunntilfellet er oppfylt, returnerer funksjonen et resultat uten å foreta flere rekursive anrop. En base case er avgjørende for å forhindre uendelig rekursjon.
- Rekursivt tilfelle: Det rekursive tilfellet definerer hvordan problemet skal brytes ned i mindre delproblemer. I denne delen av funksjonen kaller funksjonen seg selv med modifiserte innganger. Hvert rekursivt anrop er derfor et skritt mot å nå basistilfellet.
La oss deretter diskutere hva som skjer når du kaller en rekursiv funksjon.
Hvordan rekursjon fungerer under panseret
Når en funksjon kalles, blir en oversikt over dens utførelseskontekst plassert på anropsstakken. Denne posten inneholder informasjon om funksjonens argumenter, lokale variabler og plasseringen som skal returneres når funksjonen er fullført.
Når det gjelder rekursive funksjoner, når en funksjon kaller seg selv, blir en ny post skjøvet inn på anropsstakken, som effektivt suspenderer den gjeldende funksjonens utførelse. Stabelen lar Python holde styr på alle ventende funksjonsanrop, inkludert de fra rekursive anrop.
Inntil grunntilfellet er nådd, fortsetter rekursjonen. Når grunntilfellet returnerer et resultat, løses funksjonskallene én etter én – med hver funksjon som returnerer resultatet til forrige nivå i anropsstakken. Denne prosessen fortsetter til det første funksjonskallet er fullført.
Implementering av rekursjon i Python
I denne delen skal vi utforske tre enkle eksempler på rekursjon:
For hvert eksempel vil vi angi problemet, gi den rekursive Python-implementeringen, og deretter forklare hvordan den rekursive implementeringen fungerer.
#1. Faktoriell beregning ved bruk av rekursjon
Oppgave: Regn ut faktoren til et ikke-negativt heltall n, betegnet som n!. Matematisk er faktorialet til et tall n produktet av alle positive heltall fra 1 til n.
Faktorberegningen egner seg godt til rekursjon, som vist:
Her er den rekursive funksjonen for å beregne faktoren til et gitt tall 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)
La oss beregne 5! ved å bruke faktoriell() funksjonen:
factorial_5 = factorial(5) print(factorial(5)) # Output: 120
La oss nå se hvordan funksjonen fungerer:
- Vi har et grunntilfelle som sjekker om n er lik 0 eller 1. Hvis betingelsen er oppfylt, returnerer funksjonene 1. Husk at 0! er 1, og det samme er 1!.
- Hvis n er større enn 1, beregner vi n! ved å multiplisere n med faktoren til n-1. Dette uttrykkes som n * faktorial(n – 1).
- Funksjonen fortsetter å foreta rekursive anrop med synkende verdier på n inntil den når basistilfellet.
#2. Fibonacci-tall med rekursjon
Problem: Finn begrepet ved den n-te indeksen i Fibonacci-sekvens. Fibonacci-sekvensen er definert 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)
La oss kjøre funksjonen:
fib_5 = fibonacciSeq(5) print(fib_5) # Output: 5
Slik fungerer funksjonen:
- La oss starte med å diskutere grunntilfellene. Hvis n er 0, returnerer den 0. Og hvis n er 1, returnerer den 1. Hent frem F(0) = 0 og F(1) = 1.
- I det rekursive tilfellet, hvis n er større enn 1, beregner funksjonen F(n) ved å legge til F(n-1) og F(n-2) ledd. Dette uttrykkes som fibonacciSeq(n – 1) + fibonacciSeq(n – 2).
- Funksjonen fortsetter å foreta rekursive anrop med synkende verdier på n til den når basistilfellene.
#3. Rekursiv implementering av binært søk
Problem: Implementer en binær søkealgoritme ved å bruke rekursjon for å finne posisjonen til et målelement i en sortert liste.
Her er den rekursive implementeringen av binært søk:
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)
Funksjonen binært søk fortsetter å dele søkeintervallet i to med hvert rekursivt anrop til den enten finner målet eller fastslår at målet ikke er på listen.
Her er et eksempel på funksjonen:
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 bryte ned hva funksjonen gjør:
- I den rekursive binære søk-implementeringen har vi to grunntilfeller. For det første, hvis lav blir større enn høy, betyr det at målelementet ikke er på listen. Så vi returnerer -1 for å indikere at målet ikke ble funnet.
- Det andre utgangspunktet sjekker om elementet i den midterste indeksen midt i gjeldende søkeintervall er lik målet. Hvis de samsvarer, returnerer vi indeksen midt, noe som indikerer at vi har funnet målet.
- I det rekursive tilfellet, hvis det midterste elementet er større enn målet, søker vi rekursivt i venstre halvdel av matrisen ved å kalle binarySearch(arr, target, low, mid – 1). Hvis det midterste elementet er mindre enn målet, søker vi etter høyre halvdel ved å kalle binarySearch(arr, target, mid + 1, high).
Rekursiv vs. iterativ tilnærming
Iterativ tilnærming – bruk av looper – er en annen vanlig tilnærming til problemløsning. Så hvordan er det forskjellig fra rekursjon? La oss finne det ut.
Først sammenligner vi rekursive og iterative løsninger på et vanlig problem: å beregne faktorialet til et tall.
Her er den rekursive implementeringen av 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 vet at faktoren 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 loops.
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 foretrekkes en iterativ tilnærming fremfor rekursjon? Når det er dyp rekursjon – med for mange funksjonskall – kan du støte på feil på grunn av overskridelse av rekursjonsdybden. Looping er et bedre alternativ for problemer hvis rekursive implementering krever for mange funksjonskall for å nå basistilfellet.
La oss oppsummere forskjellene mellom iterative og rekursive implementeringer:
FeatureRecursive ApproachIterative ApproachStructureBruker rekursive funksjonskall og er avhengig av anropsstakken.Bruker looper for iterasjon uten ekstra funksjonskall.Base CasesKrever eksplisitte grunntilfeller for å stoppe rekursjonen. Bruker vanligvis looping-betingelser for terminering.YtelseKan være mindre minneeffektiv på grunn av anropsstakken . Dyp rekursjon kan noen ganger føre til stabeloverløpsfeil. Generelt mer minneeffektivt og mindre utsatt for stabeloverløpsfeil. FeilsøkingKan være utfordrende å feilsøke på grunn av flere funksjonskall og nestede utførelseskontekster. Vanligvis lettere å feilsøke på grunn av en enkel lineær flyt av utførelse .Iterativ vs rekursiv tilnærming
Konklusjon
I denne artikkelen startet vi med å lære hva rekursjon er og hvordan man definerer rekursive funksjoner med grunntilfeller og gjentakelsesrelasjoner.
Vi skrev deretter litt Python-kode – rekursive implementeringer av vanlige programmeringsproblemer. Til slutt lærte vi forskjellene mellom iterative og rekursive tilnærminger og fordeler og ulemper ved hver av disse tilnærmingene.
Deretter kan du sjekke ut denne listen over Python-intervjuspørsmål.