Bevezetés a rekurzióba Pythonban

Szeretne mindent megtudni a programozás rekurziójáról? Ez az oktatóanyag a Python rekurziójáról segít az indulásban.

A rekurzió egy rendkívül hasznos problémamegoldó technika, amellyel a programozó eszköztárát bővítheti. Bár kezdetben gyakran nehéz körülölelni a fejét, a rekurzió segíthet elegánsabb megoldások kidolgozásában az összetett problémákra.

Ebben az oktatóanyagban a kód-első megközelítést alkalmazzuk a Python használatával történő rekurzió megtanulásához. Különösen a következőkre térünk ki:

  • A rekurzió alapjai
  • Rekurzív függvények és működésük
  • Rekurzív függvények Python implementációja
  • A problémamegoldás iteratív és rekurzív megközelítései közötti különbségek

Kezdjük el!

Mi az a rekurzió?

A rekurzió olyan programozási technika, amelyben egy függvény ismételten meghívja magát egy probléma megoldására.

A rekurzió lényegében egy problémamegoldó megközelítés, amely magában foglalja egy összetett probléma kisebb, azonos részproblémákra bontását. Lényegében lehetővé teszi egy probléma megoldását önmaga egyszerűbb változataiban.

Tehát hogyan valósítsuk meg a rekurziót a kódban? Ehhez ismerjük meg a rekurzív függvények működését.

Rekurzív függvények megértése

Definiálunk egy rekurzív függvényt, amely a definícióján belül meghívja magát. Minden rekurzív hívás az eredeti probléma kisebb vagy egyszerűbb változatát képviseli.

Annak biztosítására, hogy a rekurzió végül leálljon, a rekurzív függvényeknek tartalmazniuk kell egy vagy több alapesetet – olyan feltételeket, amelyek mellett a függvény leállítja önmaga hívását, és eredményt ad vissza.

Bontsuk ezt tovább. A rekurzív függvény a következőkből áll:

  • Alapeset: Az alapeset egy feltétel (vagy feltételek), amelyek meghatározzák, hogy a rekurzió mikor álljon le. Ha az alapeset teljesül, a függvény minden további rekurzív hívás nélkül eredményt ad vissza. Az alapeset elengedhetetlen a végtelen rekurzió elkerüléséhez.
  • Rekurzív eset: A rekurzív eset határozza meg, hogyan bontsuk fel a problémát kisebb részproblémákra. A függvény ezen részében a függvény módosított bemenetekkel hívja meg magát. Ezért minden rekurzív hívás egy lépés az alapeset elérése felé.

Ezután beszéljük meg, mi történik egy rekurzív függvény meghívásakor.

Hogyan működik a rekurzió a motorháztető alatt

Egy függvény meghívásakor a végrehajtási környezet rekordja kerül a hívási verembe. Ez a rekord információkat tartalmaz a függvény argumentumairól, helyi változóiról és a visszaadandó helyről, ha a függvény befejezi a végrehajtást.

  A legjobb hátizsákok főiskolai hallgatóknak laptoppal

Rekurzív függvények esetén, amikor egy függvény meghívja magát, egy új rekord kerül a hívási verembe, ami gyakorlatilag felfüggeszti az aktuális függvény végrehajtását. A verem lehetővé teszi a Python számára, hogy nyomon kövesse az összes függőben lévő függvényhívást, beleértve a rekurzív hívásokból származókat is.

Amíg el nem érjük az alapesetet, a rekurzió folytatódik. Amikor az alapeset eredményt ad vissza, a függvényhívások egyenként kerülnek feloldásra – minden függvény visszaadja eredményét a hívásverem előző szintjére. Ez a folyamat addig folytatódik, amíg a kezdeti függvényhívás be nem fejeződik.

Rekurzió megvalósítása Pythonban

Ebben a részben a rekurzió három egyszerű példáját fogjuk megvizsgálni:

  • Szám faktoriálisának kiszámítása
  • Fibonacci számok számítása
  • Bináris keresés megvalósítása rekurzió segítségével.
  • Minden egyes példa esetében elmondjuk a problémát, megadjuk a Python rekurzív megvalósítását, majd elmagyarázzuk, hogyan működik a rekurzív megvalósítás.

    #1. Tényezőszámítás rekurzió segítségével

    Probléma: Számítsa ki egy n nem negatív egész szám faktoriálisát! Matematikailag egy n szám faktoriálisa az 1-től n-ig terjedő összes pozitív egész szorzata.

    A faktoriális számítás jól alkalmazható rekurzióra, amint az látható:

    Íme a rekurzív függvény egy adott n szám faktoriálisának kiszámításához:

    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)

    Számítsuk ki az 5-öt! a faktoriális() függvény használatával:

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

    Most nézzük meg, hogyan működik a függvény:

    • Van egy alapesetünk, amely ellenőrzi, hogy n egyenlő-e 0 vagy 1. Ha a feltétel teljesül, a függvények 1-et adnak vissza. Emlékezzünk vissza, hogy 0! az 1, és az 1 is!.
    • Ha n nagyobb 1-nél, akkor n-t számítunk! n-t megszorozva n-1 faktoriálisával. Ezt n * faktoriális(n – 1) formában fejezzük ki.
    • A függvény folyamatosan rekurzív hívásokat hajt végre n csökkenő értékekkel, amíg el nem éri az alapesetet.

    #2. Fibonacci számok rekurzióval

    Probléma: Keresse meg a kifejezést az n-edik indexnél Fibonacci sorozat. A Fibonacci-sorozat a következőképpen definiálható: F(0) = 0, F(1) = 1 és F(n) = F(n-1) + F(n-2) n >= 2 esetén.

    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)

    Futtassuk a függvényt:

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

    Így működik a függvény:

    • Kezdjük az alapesetek megvitatásával. Ha n értéke 0, akkor 0-t ad vissza. Ha n értéke 1, akkor 1-et ad vissza. Emlékezzünk vissza F(0) = 0 és F(1) = 1.
    • Rekurzív esetben, ha n nagyobb, mint 1, a függvény az F(n-1) és az F(n-2) tagok összeadásával számítja ki az F(n)-t. Ezt a következőképpen fejezzük ki: fibonacciSeq(n – 1) + fibonacciSeq(n – 2).
    • A függvény folyamatosan rekurzív hívásokat hajt végre n csökkenő értékekkel, amíg el nem éri az alapeseteket.
      A 4 ok, amiért az OpenAI ChatGPT haldoklik

    Probléma: Valósítson meg egy bináris keresési algoritmust rekurzió segítségével, hogy megtalálja a célelem pozícióját egy rendezett listában.

    Íme a bináris keresés rekurzív megvalósítása:

    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)

    A binarySearch függvény minden rekurzív hívásnál felosztja a keresési intervallumot, amíg meg nem találja a célt, vagy meg nem állapítja, hogy a cél nem szerepel a listában.

    Íme a függvény mintafuttatása:

    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

    Nézzük meg, mit csinál a függvény:

    • A bináris keresés rekurzív megvalósításában két alapesetünk van. Először is, ha az alacsony érték nagyobb, mint a magas, az azt jelenti, hogy a célelem nincs a listában. Tehát -1-et adunk vissza, jelezve, hogy a cél nem található.
    • A másik alapeset azt ellenőrzi, hogy az aktuális keresési intervallum középső indexének közepén lévő elem egyenlő-e a céllal. Ha egyeznek, akkor a mid indexet adjuk vissza, jelezve, hogy megtaláltuk a célt.
    • Rekurzív esetben, ha a középső elem nagyobb, mint a cél, akkor rekurzívan keresünk a tömb bal felén a binarySearch(arr, target, low, mid – 1) meghívásával. Ha a középső elem kisebb, mint a cél, akkor a jobb felét a binarySearch(arr, target, mid + 1, high) hívásával keressük.
      6 webhely a Twitteren megosztott képek keresésére

    Rekurzív vs. Iteratív megközelítés

    Az iteratív megközelítés – hurkokat használva – a problémamegoldás másik gyakori megközelítése. Tehát miben különbözik a rekurziótól? Találjuk ki.

    Először is összehasonlítjuk a rekurzív és iteratív megoldásokat egy közös problémával: egy szám faktoriálisának kiszámításával.

    Íme a faktorszámítás rekurzív megvalósítása:

    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)

    Mivel tudjuk, hogy egy nem-negatív szám faktoriálisa 1-től n-ig minden szám szorzata, írhatunk iteratív implementációt ciklusok segítségével is.

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

    Mindkét megvalósítás azonos eredményt ad.

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

    De vajon az iteratív megközelítést részesítik előnyben a rekurzióval szemben? Mély rekurzió esetén – túl sok függvényhívás esetén – a rekurziós mélység túllépése miatt hibákba ütközhet. A loopolás jobb megoldás olyan problémák esetén, amelyek rekurzív megvalósítása túl sok függvényhívást igényel az alapeset eléréséhez.

    Foglaljuk össze az iteratív és rekurzív megvalósítások közötti különbségeket:

    FeatureRecursive ApproachIterative ApproachStructureRekurzív függvényhívásokat használ, és a hívásveremre támaszkodik.Curkokat használ az iterációhoz további függvényhívások nélkül.Alapesetek Explicit alapeseteket igényel a rekurzió leállításához.Általában ciklusfeltételeket használ a befejezéshez.A teljesítmény a hívásmemóriaverem miatt kevésbé hatékony . A mély rekurzió néha veremtúlcsordulási hibákhoz vezethet.Általában memóriahatékonyabb, és kevésbé hajlamos a veremtúlcsordulási hibákra.Hibakeresés A több funkcióhívás és a beágyazott végrehajtási kontextusok miatt nehéz lehet a hibakeresés.Általában könnyebb a hibakeresés az egyszerű lineáris végrehajtási folyamatnak köszönhetően .Iteratív vs rekurzív megközelítés

    Következtetés

    Ebben a cikkben azzal kezdtük, hogy megtanultuk, mi a rekurzió, és hogyan definiálhatunk rekurzív függvényeket alapesetekkel és ismétlődési relációkkal.

    Ezután írtunk néhány Python-kódot – általános programozási problémák rekurzív megvalósításait. Végül megismertük az iteratív és rekurzív megközelítések közötti különbségeket, valamint az egyes megközelítések előnyeit és hátrányait.

    Ezután nézze meg a Python interjúkérdések listáját.