Ebben az oktatóanyagban megtanul egy rekurzív függvényt létrehozni (egy olyan funkciót, amely önmagát hívja).
Mi a rekurzió?
A rekurzió az a folyamat, amikor valamit önmagában meghatározunk.
A fizikai világ példája az lenne, ha két párhuzamos tükröt egymással szemben helyeznének el. A köztük lévő bármely objektum rekurzív módon tükröződik.
Python rekurzív függvény
A Pythonban tudjuk, hogy egy függvény más függvényeket is meghívhat. Még az is lehetséges, hogy a függvény hívja magát. Az ilyen típusú konstrukciókat rekurzív függvényeknek nevezzük.
A következő kép az úgynevezett rekurzív függvény működését mutatja be recurse.
Rekurzív függvény a Pythonban
Az alábbiakban bemutatunk egy rekurzív függvényt egy egész szám faktoriáljának megkeresésére.
A szám tényezője az összes egész szám szorzata 1-től számig. Például a 6 tényezője (amelyet 6-nak jelölünk!) 1 * 2 * 3 * 4 * 5 * 6 = 720.
Példa rekurzív függvényre
def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))
Kimenet
A 3 tényezője 6
A fenti példában factorial()rekurzív függvény, ahogy önmagát hívja.
Ha ezt a függvényt pozitív egész számmal hívjuk meg, akkor a szám csökkentésével rekurzívan hívja magát.
Minden függvény megszorozza a számot az alatta lévő szám faktoriáljával, amíg meg nem egyezik. Ez a rekurzív hívás a következő lépésekben magyarázható.
faktoriális (3) # 1. hívás 3 3 * faktoriálissal (2) # 2. hívás 2-vel 3 * 2 * faktoriális (1) # 3. hívás 1 3 * 2 * 1 # visszatéréssel a 3. hívásból számként = 1 3 * 2 # visszatérés a 2. hívásból 6 # visszatérés az 1. hívásból
Nézzünk meg egy képet, amely lépésről lépésre mutatja be a folyamatot:
Rekurzív faktoriális függvény működése
Rekurziónk akkor ér véget, amikor a szám 1-re csökken. Ezt nevezzük alapfeltételnek.
Minden rekurzív függvénynek rendelkeznie kell olyan alapfeltétellel, amely megállítja a rekurziót, különben a függvény végtelenül hívja magát.
A Python tolmács korlátozza a rekurzió mélységét, hogy elkerülje a végtelen rekurziókat, ami verem túlcsordulást eredményez.
Alapértelmezés szerint a rekurzió maximális mélysége 1000. Ha átlépik a határt, az azt eredményezi RecursionError. Nézzünk meg egy ilyen feltételt.
def recursor(): recursor() recursor()
Kimenet
Traceback (a legutóbbi hívás utoljára): "" fájl, 3. sor, a "" fájlban, 2. sor, egy "" fájlban, 2. sor, egy "" fájlban, 2. sor, "" fájlban, 2. sor, egy (az előző sor még 996-szor megismétlődik) ) RecursionError: a maximális rekurziós mélység túllépve
A rekurzió előnyei
- A rekurzív funkciók segítségével a kód tiszta és elegáns lesz.
- A komplex feladat rekurzióval egyszerűbb részproblémákra bontható.
- A szekvencia generálása könnyebb a rekurzióval, mint néhány beágyazott iteráció használata.
A rekurzió hátrányai
- Néha a rekurzió mögött rejlő logikát nehéz követni.
- 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.
