Egyszerű szavakkal, a rekurzió a probléma megoldásának egyik módja azzal, hogy magát a függvényt hívja meg. rekurzív ”A latin igéből ered ismételje meg ”, Ami azt jelenti, hogy átdolgozzunk valamit. Ezt teszi a rekurzív függvény, újra és újra átdolgozza ugyanazt, vagyis felidézi önmagát. Ebben a cikkben megismerjük a rekurziót a pythonban. A következő témákkal foglalkozik ez a blog:
- Mi a rekurzió a Pythonban?
- Felmondási feltétel
- Python rekurziós korlátja
- Rekurziós listák ellapítása
- A rekurzió előnyei
- A rekurzió hátrányai
Mi a rekurzió a Pythonban?
A rekurzió az a folyamat, amikor valamit meghatározunk önmagában. Tudjuk, hogy a Pythonban bármely funkció bármely más függvényt meghívhat, egy függvény önmagát is hívhatja. Az ilyen típusú funkciókat, amelyek önmagukat hívják, amíg az adott feltétel nem teljesül, rekurzív függvényeknek nevezzük.
Vegyünk néhány példát, hogy lássuk, hogyan működik ez. Ha pozitív n egész számot kap, akkor a faktoriális lenne.
- n! = n * (n-1) * (n-2) és így tovább.
- 2! = 2 * (2-1)
- egy! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
A fenti értékek cseréje a következő kifejezést eredményezi
- 4! = 4 * 3 * 2 * 1
Meg kell határoznunk egy függvényt, amellyel mondjuk a tényt (n), amely pozitív egész számot vagy 0-t vesz paraméterül és az n-edik faktoriált adja vissza. Hogyan tudjuk ezt megtenni rekurzióval?
Lássuk, ehhez a rekurzió segítségével meg kell vizsgálnunk a következő egyenletet
n! = n. (n-1). (n-2) & hellip3.2.1
n! = n. (n-1)! # átírhatjuk a fenti állítást, mint ezen a vonalon
Most itt, ha 2-t adunk át paraméterként, megkapjuk:
2! = 2,1! = 2
Hasonlóképpen, ha 1-et elhaladunk, akkor kapunk:
hogyan kell használni a riasztást a javascriptben
egy! = 1,0! = 1
De ha 0-t adunk át, akkor megszakad
0! = 0. (- 1)! és itt nincs meghatározva a -1 tényezője, így ez csak> 0 értékek esetén működik
Tehát két esetet kell megírnunk
1. n! = n. (n-1)! ha n> = 1
2. 1, ha n = 0
Ez egy teljes megoldás az összes pozitív egész számra és 0-ra.
c ++ egy tömb rendezése
Felmondási feltétel
A rekurzív függvénynek meg kell felelnie a megszüntetés fontos feltételének. Olyan állapot felé haladva, ahol a probléma további rekurzió nélkül megoldható, a rekurzív függvény megszűnik, minimalizálva a problémát a kisebb részlépésekbe. A rekurzió végtelen hurokba kerülhet, ha a hívás során nem teljesül a befejezés feltétele.
Faktoriális feltételek:
- n = n * (n-1) tényezője, amíg n nagyobb, mint 1.
- 1, ha n = 0
A fenti tényezői feltételeket konvertáljuk python kódban:
def tény (n): ha n == 1: adja vissza n else: adja vissza n * tény (n-1)
Vegyünk egy példát, mondjuk szeretnénk megtalálni a 4 tényezőjét:
tény (4) #ez 4 * tényt (3) ad vissza, és így tovább, amíg n == 1.
Kimenet: 24.
Olyan gyakran használják rekurziós példaként az egyszerűség és az egyértelműség miatt. A probléma kisebb példányainak megoldása minden lépésben, amelyet rekurziónak neveztek a számítástechnikában.
Python rekurziós korlátja
Bizonyos nyelveken létrehozhatunk egy végtelen rekurzív ciklust, de a Pythonban rekurziós korlát van érvényben. A limit ellenőrzéséhez futtassa a következő függvényt a sys modulból. amely megadja a python számára beállított rekurzió határát.
import sys sys.getrecursionlimit ()
Kimenet: 1000
Megváltoztathatja a korlátot a sys modul függvényeivel a retecursionlimit () is az Ön igényei szerint. Most hozzunk létre egy olyan függvényt, amely rekurzívan hívja magát, amíg túllépi a határt, és ellenőrzi, mi történik:
def rekurzív (): rekurzív (), ha __név__ == '__main__': rekurzív ()
Ha futtatja a fenti kódot, akkor futásidejű kivételt kap: RuntimeError: a maximális rekurziós mélység túllépve. A Python megakadályozza, hogy olyan funkciót hozzon létre, amely véget nem érő rekurzív ciklusba kerül.
Rekurziós listák ellapítása
Egyéb dolgok, amelyeket a rekurzió használatával tehet meg, kivéve a tényleges elemeket, tegyük fel, hogy egy beágyazott listából szeretne egy egyedet létrehozni, ezt az alábbi kód segítségével teheti meg:
def flatten (a_list, flat_list = none): ha a flat_list nincs: flat_list = [] az a_list elemhez: if isinstance (item, list): lapos (item, flat_list) else: flat_list.append (item) return flat_list ha __name__ == '__main__': beágyazott = [1,2,3, [4,5], 6] x = lapos (beágyazott) nyomtatás (x)
Kimenet: [1,2,3,4,5,6]
A fenti kód futtatása egyetlen listát eredményez, ahelyett, hogy egész számot tartalmazna, az egész listát tartalmazza, amelyet inputként használtunk. Ugyanezt megteheti más módon is, a Pythonnak van egy itertools.chain () nevű neve. Ellenőrizheti a függvénylánc létrehozásához használt kódot (), más megközelítés ugyanazt csinálni, mint mi.
A rekurzió előnyei
A kód tiszta és elegáns rekurzív funkcióval.
Az összetett feladat a rekurzió segítségével egyszerűbb részproblémákra bontható.
Rekurzióval könnyebb generálni a szekvenciát, mint néhány beágyazott iterációt használni.
a java hatalmára
A rekurzió hátrányai
A rekurzív függvény logikájának követése néha nehéz lehet.
A rekurzív hívások drágák (nem hatékonyak), mivel sok memóriát és időt igényelnek.
A rekurzív funkciókat nehéz hibakeresni.
Ebben a cikkben azt láttuk, hogy mi a rekurzió, és hogyan fejleszthetünk rekurzív függvényeket a problémamegállapításból, hogy matematikailag hogyan lehet definiálni egy problémakört. Megoldottuk a faktoriál problémáját, és megtudtuk azokat a feltételeket, amelyek szükségesek ahhoz, hogy megtaláljuk azokat a faktoriálokat, amelyekből ezeket a feltételeket python kódokká konvertálhatjuk, ezáltal megértve a rekurzió működését. Szerintem szép, hogy a Python rendelkezik beépített korlátozással a rekurzióra, hogy megakadályozza a fejlesztőket a rosszul felépített rekurzív függvények létrehozásában. Egy fontos dolog, amit észre kell venni, hogy a rekurziót nehéz hibakeresni, mivel a függvény folyamatosan hívja magát.