Introduktion till rekursion i Python

Är du intresserad av att fördjupa dig i rekursionens värld inom programmering? Denna guide om rekursion i Python är designad för att hjälpa dig att komma igång.

Rekursion är en ovärderlig teknik för problemlösning som varje programmerare bör ha i sin verktygslåda. Även om det kan kännas utmanande i början, kan rekursion erbjuda mer eleganta lösningar på komplexa problem.

I den här handledningen kommer vi att fokusera på en praktisk, kod-först-metod för att utforska rekursion med Python. Vi kommer specifikt att behandla följande ämnen:

  • Grundläggande principer för rekursion
  • Rekursiva funktioner och deras funktionssätt
  • Implementering av rekursiva funktioner i Python
  • Skillnader mellan iterativa och rekursiva metoder för att lösa problem

Låt oss sätta igång!

Vad är rekursion?

Rekursion är en programmeringsteknik där en funktion anropar sig själv flera gånger för att lösa ett specifikt problem.

I grund och botten handlar rekursion om att bryta ner ett invecklat problem till enklare, liknande delproblem. Denna teknik tillåter dig att lösa ett problem genom att formulera det i termer av enklare versioner av sig självt.

Så, hur applicerar vi rekursion i kod? Låt oss först undersöka hur rekursiva funktioner fungerar.

Förstå rekursiva funktioner

En rekursiv funktion definieras genom att den anropar sig själv inuti sin egen definition. Varje sådant anrop representerar en mindre eller mer grundläggande version av det ursprungliga problemet.

För att säkerställa att rekursionen inte fortsätter i oändlighet, måste rekursiva funktioner innehålla ett eller flera basfall. Basfallen är villkor som indikerar när funktionen ska sluta anropa sig själv och returnera ett resultat.

Låt oss dela upp det här ytterligare. En rekursiv funktion består av:

  • Basfall: Detta är ett villkor som definierar när rekursionen ska avslutas. När basfallet uppnås, returnerar funktionen ett resultat utan att göra ytterligare rekursiva anrop. Ett basfall är kritiskt för att förhindra att funktionen körs oändligt.
  • Rekursivt fall: Det rekursiva fallet beskriver hur problemet delas upp i mindre delproblem. Inom denna del anropar funktionen sig själv med justerade ingångsvärden. Varje rekursivt anrop för oss närmare basfallet.

Låt oss nu diskutera vad som sker när en rekursiv funktion anropas.

Hur rekursion fungerar i grunden

När en funktion anropas, sparas en post om dess exekveringssammanhang i anropsstacken. Denna post innehåller detaljer om funktionens argument, lokala variabler, samt den plats den ska återvända till efter avslutad exekvering.

När det gäller rekursiva funktioner, skjuts en ny post till anropsstacken varje gång funktionen anropar sig själv. Detta resulterar i att den aktuella funktionskörningen temporärt avbryts. Stacken ger Python möjlighet att hålla koll på alla väntande funktionsanrop, inklusive de som kommer från rekursiva anrop.

Rekursionen fortsätter tills basfallet uppnås. När basfallet returnerar ett resultat, börjar funktionsanropen att lösas upp ett efter ett, där varje funktion ger sitt resultat till den föregående nivån i anropsstacken. Denna process fortsätter tills det ursprungliga funktionsanropet har slutförts.

Implementering av rekursion i Python

I det här avsnittet kommer vi att utforska rekursion genom tre konkreta exempel:

  • Beräkning av fakulteten för ett tal
  • Generering av Fibonacci-tal
  • Implementering av binär sökning med rekursion

För varje exempel kommer vi att presentera problemet, visa den rekursiva implementeringen i Python och förklara hur den fungerar.

#1. Fakultetsberäkning med hjälp av rekursion

Problem: Beräkna fakulteten för ett icke-negativt heltal n, vilket skrivs som n!. Matematiskt sett är fakulteten av ett tal n produkten av alla positiva heltal från 1 till n.

Fakultetsberäkning är ett bra exempel för att illustrera rekursion, som framgår av följande:

Här är den rekursiva funktionen för att beräkna fakulteten för ett givet tal n:

def factorial(n):
    # Basfall
    if n == 0 or n == 1:
        return 1
    # Rekursivt fall: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

Låt oss beräkna 5! med hjälp av funktionen factorial():

factorial_5 = factorial(5)
print(factorial(5))
# Utmatning: 120

Låt oss se hur funktionen fungerar:

  • Vi har ett basfall som kontrollerar om n är 0 eller 1. Om så är fallet, returnerar funktionen 1. Kom ihåg att 0! är 1, liksom 1!.
  • Om n är större än 1, beräknar vi n! genom att multiplicera n med fakulteten av n-1. Detta uttrycks som n * factorial(n – 1).
  • Funktionen fortsätter att göra rekursiva anrop med mindre värden på n tills den når basfallet.

#2. Fibonacci-tal med rekursion

Problem: Hitta termen vid det n:te indexet i Fibonacci-sekvensen. Fibonacci-sekvensen definieras på följande sätt: F(0) = 0, F(1) = 1 och F(n) = F(n-1) + F(n-2) för n >= 2.

def fibonacciSeq(n):
    # Basfall
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # Rekursion: F(n) = F(n-1) + F(n-2)
    else:
        return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)

Låt oss köra funktionen:

fib_5 = fibonacciSeq(5)
print(fib_5)
# Utmatning: 5

Så här fungerar funktionen:

  • Låt oss först prata om basfallen. Om n är 0, returneras 0. Om n är 1, returneras 1. Kom ihåg att F(0) = 0 och F(1) = 1.
  • I det rekursiva fallet, om n är större än 1, beräknar funktionen F(n) genom att addera termerna F(n-1) och F(n-2). Detta uttrycks som fibonacciSeq(n – 1) + fibonacciSeq(n – 2).
  • Funktionen fortsätter att göra rekursiva anrop med minskande värden på n tills basfallen nås.

#3. Rekursiv implementering av binär sökning

Problem: Implementera en binär sökningsalgoritm med rekursion för att hitta positionen för ett målelement i en sorterad lista.

Här är den rekursiva implementationen av binär sökning:

def binarySearch(arr, target, low, high):
    # Basfall: mål hittades inte
    if low > high:
        return -1

    mid = (low + high) // 2

    # Basfall: mål hittades
    if arr[mid] == target:
        return mid
    # Rekursivt fall: sök vänster eller höger halva av arrayen
    elif arr[mid] > target:
        return binarySearch(arr, target, low, mid - 1)
    else:
        return binarySearch(arr, target, mid + 1, high)

Funktionen binarySearch fortsätter att halvera sökområdet vid varje rekursivt anrop tills antingen målet hittas eller det fastställs att målet inte finns i listan.

Här är ett exempel på hur funktionen används:

arr = [5, 8, 13, 24, 37, 49, 51, 64, 72, 88, 96]
target = 37
idx = binarySearch(arr, target, 0, len(arr)-1)
print(idx)
# Utmatning: 4

Låt oss se vad funktionen gör steg för steg:

  • I den binära sökningsrekursiva implementationen har vi två basfall. För det första, om ”låg” blir större än ”hög”, betyder det att målelementet inte finns i listan. I detta fall returneras -1 för att indikera att målet inte hittades.
  • Det andra basfallet kontrollerar om elementet i mitten av det aktuella sökområdet matchar målet. Om en matchning finns returneras indexet ”mitt”.
  • I det rekursiva fallet, om elementet i mitten är större än målet, söker funktionen rekursivt i den vänstra halvan av arrayen genom att anropa binarySearch(arr, target, low, mid – 1). Om mittelementet är mindre än målet söker funktionen rekursivt i den högra halvan genom att anropa binarySearch(arr, target, mid + 1, high).

Rekursiv vs. Iterativ metod

En iterativ metod, som använder loopar, är ett annat vanligt sätt att lösa problem. Så, hur skiljer det sig från rekursion? Låt oss ta reda på det.

Först kommer vi att jämföra rekursiva och iterativa lösningar för ett vanligt problem: att beräkna fakulteten för ett tal.

Här är den rekursiva implementationen för fakultetsberäkning:

def factorialRec(n):
    # Basfall
    if n == 0 or n == 1:
        return 1
    # Rekursivt fall: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

Eftersom vi vet att fakulteten för ett icke-negativt heltal är produkten av alla tal från 1 upp till n, kan vi även skriva en iterativ implementation med hjälp av loopar.

def factorialIter(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

Båda dessa implementationer ger identiska resultat.

factorial_5 = factorialRec(5)
print(factorial_5)
# Utmatning: 120

factorial_5 = factorialIter(5)
print(factorial_0)
# Utmatning: 120

Men är en iterativ metod att föredra framför rekursion? Vid djup rekursion – med för många funktionsanrop – kan du stöta på fel på grund av att rekursionsdjupet överskrids. Loopar är ett bättre alternativ för problem vars rekursiva implementation kräver för många funktionsanrop för att nå basfallet.

Låt oss summera skillnaderna mellan iterativa och rekursiva implementationer:

Funktion Rekursiv metod Iterativ metod
Struktur Använder rekursiva funktionsanrop och förlitar sig på anropsstacken. Använder loopar för iteration utan ytterligare funktionsanrop.
Basfall Kräver explicita basfall för att stoppa rekursionen. Använder vanligen loopingvillkor för avslutning.
Prestanda Kan vara mindre minneseffektiv på grund av anropsstacken. Djup rekursion kan ibland leda till stack overflow-fel. Generellt mer minneseffektiv och mindre benägen att stack overflow-fel.
Felsökning Kan vara utmanande att felsöka på grund av flera funktionsanrop och kapslade exekveringssammanhang. Vanligtvis lättare att felsöka på grund av ett enkelt linjärt flöde av exekvering.

Iterativ vs rekursiv metod

Slutsats

I den här artikeln började vi med att undersöka vad rekursion är och hur man definierar rekursiva funktioner med basfall och rekursiva samband.

Vi skrev sedan lite Python-kod – rekursiva implementationer av vanliga programmeringsproblem. Slutligen tittade vi på skillnaderna mellan iterativa och rekursiva metoder, samt fördelarna och nackdelarna med varje tillvägagångssätt.

Kolla in den här listan med Python intervjufrågor.