Introduktion till rekursion i Python

av

Vill du lära dig allt om rekursion i programmering? Denna handledning om rekursion i Python hjälper dig att komma igång.

Rekursion är en superhjälpsam problemlösningsteknik att lägga till din programmerares verktygslåda. Även om det i början ofta är svårt att linda huvudet, kan rekursion hjälpa dig att komma på mer eleganta lösningar på komplexa problem.

I den här handledningen kommer vi att ta en kod-först-metod för att lära in rekursion med Python. I synnerhet kommer vi att täcka:

  • Grunderna i rekursion
  • Rekursiva funktioner och hur de fungerar
  • Python-implementering av rekursiva funktioner
  • Skillnader mellan iterativa och rekursiva metoder för problemlösning

Låt oss börja!

Vad är rekursion?

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

I sin kärna är rekursion ett problemlösningssätt som innebär att bryta ner ett komplext problem i mindre, identiska delproblem. I huvudsak låter det dig lösa ett problem i form av enklare versioner av sig själv.

Så, hur implementerar vi rekursion i kod? För att göra det, låt oss förstå hur rekursiva funktioner fungerar.

Förstå rekursiva funktioner

Vi definierar en rekursiv funktion som kallar sig inom sin definition. Varje rekursivt anrop representerar en mindre eller enklare version av det ursprungliga problemet.

För att säkerställa att rekursionen så småningom upphör, måste rekursiva funktioner inkludera ett eller flera basfall – villkor under vilka funktionen slutar anropa sig själv och returnerar ett resultat.

Låt oss bryta ner detta ytterligare. En rekursiv funktion består av:

  • Basfall: Basfallet är ett tillstånd (eller villkor) som bestämmer när rekursionen ska upphöra. När basfallet är uppfyllt returnerar funktionen ett resultat utan att göra några ytterligare rekursiva anrop. Ett basfall är viktigt för att förhindra oändlig rekursion.
  • Rekursivt fall: Det rekursiva fallet definierar hur man delar upp problemet i mindre delproblem. I denna del av funktionen anropar funktionen sig själv med modifierade ingångar. Varje rekursivt samtal är därför ett steg mot att nå basfallet.

Låt oss sedan diskutera vad som händer när du anropar en rekursiv funktion.

Hur rekursion fungerar under huven

När en funktion anropas, placeras en post över dess exekveringskontext på anropsstacken. Den här posten innehåller information om funktionens argument, lokala variabler och platsen som ska returneras när funktionen är klar.

När det gäller rekursiva funktioner, när en funktion anropar sig själv, skjuts en ny post till anropsstacken, vilket effektivt avbryter den aktuella funktionens exekvering. Stacken tillåter Python att hålla reda på alla väntande funktionsanrop, inklusive de från rekursiva anrop.

Tills basfallet uppnås fortsätter rekursionen. När basfallet returnerar ett resultat, löses funktionsanropen ett efter ett – med varje funktion som returnerar sitt resultat till föregående nivå i anropsstacken. Denna process fortsätter tills det första funktionsanropet slutförs.

Implementering av rekursion i Python

I det här avsnittet kommer vi att utforska tre enkla exempel på rekursion:

  • Beräkna fakulteten för ett tal
  • Beräknar Fibonacci-tal
  • Implementering av binär sökning med hjälp av rekursion.

    • För varje exempel kommer vi att ange problemet, tillhandahålla den rekursiva Python-implementeringen och sedan förklara hur den rekursiva implementeringen fungerar.

    #1. Faktoriell beräkning med hjälp av rekursion

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

    Faktorialberäkningen lämpar sig väl för rekursion, som visas:

    Här är den rekursiva funktionen för att beräkna fakulteten för ett 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)

    Låt oss beräkna 5! använder funktionen factorial():

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

    Låt oss nu se hur funktionen fungerar:

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

    #2. Fibonacci-tal med rekursion

    Problem: Hitta termen vid det n:te indexet i Fibonacci-sekvens. Fibonacci-sekvensen definieras enligt följande: F(0) = 0, F(1) = 1 och F(n) = F(n-1) + F(n-2) för 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)

    Låt oss köra funktionen:

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

    Så här fungerar funktionen:

    • Låt oss börja med att diskutera basfallen. Om n är 0, returnerar det 0. Och om n är 1, returnerar det 1. Kom ihåg 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 den når basfallen.

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

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

    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 fortsätter att dela sökintervallet på mitten med varje rekursivt anrop tills den antingen hittar målet eller fastställer att målet inte finns i listan.

    Här är ett exempel 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

    Låt oss dela upp vad funktionen gör:

    • I den binära sökrekursiva implementeringen 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. Så vi returnerar -1 för att indikera att målet inte hittades.
    • Det andra basfallet kontrollerar om elementet i mitten av indexet i mitten av det aktuella sökintervallet är lika med målet. Om de matchar returnerar vi indexet mitt, vilket indikerar att vi har hittat målet.
    • I det rekursiva fallet, om mittelementet är större än målet, söker vi 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 vi efter den högra halvan genom att anropa binarySearch(arr, target, mid + 1, high).

    Rekursiv vs. Iterativ metod

    Iterativt tillvägagångssätt – att använda loopar – är ett annat vanligt tillvägagångssätt för problemlösning. Så, hur skiljer det sig från rekursion? Låt oss ta reda på.

    Först jämför vi rekursiva och iterativa lösningar på ett vanligt problem: att beräkna ett tals faktorial.

    Här är den rekursiva implementeringen av faktorberäkning:

    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)

    Eftersom vi vet att faktorn för ett icke-negativt tal är produkten av alla tal från 1 upp till n, kan vi också skriva en iterativ implementering med loopar.

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

    Båda dessa implementeringar ger identiska resultat.

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

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

    Men är ett iterativt tillvägagångssätt att föredra framför rekursion? När det finns djup rekursion – med för många funktionsanrop – kan du stöta på fel på grund av att rekursionsdjupet överskrids. Looping är ett bättre alternativ för problem vars rekursiva implementering kräver för många funktionsanrop för att nå basfallet.

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

    FeatureRecursive ApproachIterative ApproachStructureAnvänder rekursiva funktionsanrop och förlitar sig på anropsstacken.Använder loopar för iteration utan ytterligare funktionsanrop.Base CasesKräver explicita basfall för att stoppa rekursionen.Använder vanligtvis loopingvillkor för avslutning.PrestandanKan 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ökningKan 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 lära oss vad rekursion är och hur man definierar rekursiva funktioner med basfall och återfallsrelationer.

    Vi skrev sedan lite Python-kod – rekursiva implementeringar av vanliga programmeringsproblem. Slutligen lärde vi oss skillnaderna mellan iterativa och rekursiva metoder och för- och nackdelarna med var och en av dessa tillvägagångssätt.

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