Mi a rekurzív funkció?
A funkció újra és újra felhívja magát, amíg nem teljesíti a rekurzív feltételt. Egy rekurziós függvény kisebb problémákra bontja a problémát, és meghívja a saját logikáját a kisebb probléma megoldására. Ezt a technikát nevezzük el és oszd meg. A matematikában és a számítástechnikában használják.
A rekurzív funkció tartalmaz egy alapesetet (vagy terminál eset) és egy rekurzív esetet. Az alapelvben megfontolhatja a megoldandó fő problémát, és a rekurzív eset kisebb részekre osztja a problémát, amíg el nem éri azt a szintet, ahol könnyen megoldható. Egy rekurzív eset eredményt hozhat, vagy újrahívhatja magát a probléma további megosztása érdekében. Minden alkalommal, amikor a probléma kisebb problémává bontódik, a rekurzívan meghívott funkció megmenti a hívás állapotát, és a probléma lebontása után elvárja az eredményt önmagától.
Rekurzív funkció a Pythonban
A rekurzió fogalma változatlan marad Pythonban. A függvény felhívja magát arra, hogy a problémát kisebb problémákra bontja. A legegyszerűbb példa, amire gondolhatunk a rekurzióról, egy szám tényezőjének megtalálása.
Tegyük fel, hogy meg kell találnunk az 5 => 5 számú tényezőt! (A problémánk)
Találni 5! a probléma kisebbre bontható 5! => 5 x 4!
Tehát, hogy kap 5! Meg kell találnunk 4-et! és szorozzuk meg 5-szel.
Osszuk tovább a problémát
5! = 4! x 5
4! = 3! x 4
3! = 3 x 2!
2! = 2 x 1!
1! = 1
Amikor eléri a legkisebb darabot, azaz ha az 1-es tényezőt kapjuk, akkor az eredményt így adhatjuk meg
Vegyünk egy álkódos példát: -
Faktorialgoritmus
Nézzük meg a faktorial algoritmust:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Funkcióhívások
Tegyük fel, hogy 5-es tényezőt találunk.
get_factorial(5) 5 * get_factorial(4) = returns 120 #1st call
get_factorial(4) 4 * get_factorial(3) = returns 24 #2nd call
get_factorial(3) 3 * get_factorial(2) = returns 6 #3rd call
get_factorial(2) 2 * get_factorial(1) = returns 2 #4th call
get_factorial(1) returns 1 #5th call
A végeredmény 120 lesz, ahol megkezdtük a függvény végrehajtását. A rekurziós funkció leáll, ha a szám annyira csökken, hogy az eredmény elérhető legyen.
- Az első hívás, amely az 5-ös tényezőt kapja, egy rekurzív állapotot eredményez, ahol hozzáadódik a veremhez, és egy másik hívás indul, miután a számot 4-re csökkentette.
- Ez a rekuráció tovább folytatja a hívást és a probléma apróbb részekre bontását, amíg az el nem éri az alapállapotot.
- Az alapfeltétel itt az, ha a szám 1.
- Minden rekurzív függvénynek megvan a saját rekurzív állapota és egy alapfeltétele.
A Python rekurzív funkció előnyei és hátrányai
- A rekurzió végrehajtása úgy történik, hogy nem végez számításokat, amíg el nem éri az alapfeltételt.
- Az alapfeltételek elérésekor elfogyhat a memória.
- Egy nagy probléma esetén, ahol lehet egymillió lépés vagy elmondhatjuk a program végrehajtásának egymillió rekurzusát, memóriahiba vagy szegmentálási hiba okozhat.
- 1000000! = 1000000 * 999999! =?
- A rekurzió nem az iteráció, hanem egy iterációs módszer.
- A különböző nyelveknek a rekurzió optimalizálása eltérő.
- Sok nyelven az iteratív módszer jobb lenne, mint a rekurzió.
- Minden nyelv rendelkezik bizonyos korlátozásokkal a rekurzió mélységében, amelyekkel szembesülhet nagy problémák megoldásakor.
- Néha nehéz megérteni a rekurzió komplex problémáit, míg az iteráció nagyon egyszerű.
Néhány előnye
- Bizonyos esetekben a rekurzió kényelmes és gyorsabb felhasználási mód.
- Nagyon hasznos a fa mozgatásában és a bináris keresésben.
Python kód - rekurzió vs iteráció
Megértettük, mi a rekurzió és hogyan működik a Pythonban, mivel tudjuk, hogy minden nyelv eltérően alkalmazza a rekurziót a memória és a számítási optimalizálás szempontjából. Előfordulhat, hogy az iteráció gyorsabb, mint a rekurzió.
Itt összehasonlíthatjuk mind a rekurziós, mind az iterációs módszert, hogy megtudjuk, hogyan teljesít Python mindkét esetben.
1. Faktorialis rekurziós kód
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2: #base condition
return 1
else:
return n * get_recursive_factorial(n -1) #recursion condition
2. Faktorprobléma iterációval (hurkolás)
def get_iterative_factorial(n):
if n < 0:
return -1
else:
fact = 1
for i in range( 1, n+1 ):
fact *= i
return fact
3. Eredmények nyomtatása
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
Kimenet:
Mint láthatjuk, hogy mindkettő ugyanazt a kimenetet adja, mint ugyanazt a logikát írtuk. Itt nem látunk különbséget a végrehajtásban.
Adjunk hozzá néhány időkódot, hogy további információt kapjunk a Python rekurziójának és iterációjának végrehajtásáról.
Importáljuk az „idő” könyvtárat, és ellenőrizzük, hogy az eredmény visszatérítéséhez milyen idő rekurzáció és iteráció szükséges.
4. Kód időszámítással
import time
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2:
return 1
else:
return n * get_recursive_factorial(n-1)
def get_iterative_factorial(n):
if n < 0 :
return -1
else:
fact = 1
for i in range(1, n+1):
fact *= i
return fact
start_time = time.time()
get_recursive_factorial(100)
print("Recursion--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
get_iterative_factorial(100)
print("Iteration--- %s seconds ---" % (time.time() - start_time))
Megismételjük a tényező eltérő értékét, és megnézjük az eredményeket. Az alábbi eredmények gépenként változhatnak. A MacBook Pro 16 GB RAM i7-et használtuk.
A végrehajtáshoz Python 3.7-et használunk
1. eset: - A 6. tényező:
2. eset: Az 50. tényező:
3. eset: A 100-as tényező:
4. eset: 500-as tényező:
5. eset: Az 1000-es tényező:
Mindkét módszert különféle problémákban elemeztük. Sőt, mindkettő hasonló módon teljesített, kivéve a 4. esetet.
Az 5. esetben hibát kaptunk, miközben rekurzióval végeztük.
A Python korlátozta a rekurzióval megengedett maximális mélységet, de ugyanezt a problémát tudtam megoldani iterációval.
A Python korlátozásokkal rendelkezik a túlcsordulás problémája ellen. A Python nincs optimalizálva a farok rekurziójára, és az ellenőrizetlen rekurzió verem túlcsordulást okoz.
A „sys.getrecursionlimit ()” funkció megmutatja a rekurzió korlátját.
A rekurziós határ megváltoztatható, de nem javasoljuk, hogy veszélyes lehet.
Következtetés - Python rekurzív funkció
- A rekurzió praktikus megoldást kínál bizonyos problémákra, például a fa áthaladására és más problémákra.
- A Python nem funkcionális programozási nyelv, és láthatjuk, hogy a rekurziós verem nem olyan optimalizált, mint az iteráció.
- Az algoritmusunkban iterációt kell használnunk, mivel a Pythonban optimalizáltabb és jobb sebességet nyújt.
Ajánlott cikkek
Ez egy útmutató a Python rekurzív funkciójához. Itt megvitatjuk, mi a rekurzív funkció, a Python rekurzív funkciója, a faktorialgoritmus stb.
- Faktérium a Pythonban
- Spark Shell parancsok
- Legjobb C fordító
- Algoritmusok típusai
- Faktorialis program a JavaScript-ben
- Útmutató az Unix Shell parancsok listájához
- A nyomtatványtípusok reagálva a példákkal