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!
Tartalomjegyzék
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.
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:
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.
#3. A bináris keresés rekurzív megvalósítása
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.
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.