mi a rekurzió?

a rekurzió az a folyamat, amely valamit önmagában határoz meg.

a fizikai világ példája az lenne, ha két párhuzamos tükröt helyeznénk egymás felé. A köztük lévő tárgyak rekurzív módon tükröződnek.

Python rekurzív funkció

Pythonban tudjuk, hogy egy függvény más funkciókat is hívhat. Még az is lehetséges, hogy a funkció hívja magát. Az ilyen típusú konstrukció nevezzük rekurzív függvények.

a következő kép a recurserekurzív függvény működését mutatja.

következő egy példa egy rekurzív függvényre, hogy megtalálja a faktoriális egész szám.

egy szám Faktoriálja az összes egész szám szorzata 1-től az adott számig. Például, a faktoriális 6 (jelöljük 6!) jelentése 1*2*3*4*5*6 = 720.

példa egy 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 = 3print("The factorial of", num, "is", factorial(num))

kimenet

The factorial of 3 is 6

a fenti példában factorial() egy rekurzív függvény, ahogy magát nevezi.

Ha ezt a funkciót pozitív egész számnak hívjuk, rekurzív módon hívja magát a szám csökkentésével.

minden függvény megsokszorozza a számot az alatta lévő szám faktoriálisával, amíg egyenlő. Ez a rekurzív hívás a következő lépésekben magyarázható.

factorial(3) # 1st call with 33 * factorial(2) # 2nd call with 23 * 2 * factorial(1) # 3rd call with 13 * 2 * 1 # return from 3rd call as number=13 * 2 # return from 2nd call6 # return from 1st call

nézzünk meg egy képet, amely lépésről lépésre bemutatja, hogy mi folyik itt:

a rekurzió akkor ér véget, amikor a szám 1-re csökken. Ezt nevezik az alapfeltételnek.

minden rekurzív függvénynek rendelkeznie kell egy alapfeltétellel, amely megállítja a rekurziót, vagy pedig a függvény végtelenül hívja magát.

a Python értelmező 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 a határértéket átlépi, akkor RecursionErrorértéket eredményez. Nézzünk meg egy ilyen feltételt.

def recursor(): recursor()recursor()

Output

Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a RecursionError: maximum recursion depth exceeded

A rekurzió előnyei

1. a rekurzív függvények miatt a kód tisztának és elegánsnak tűnik.
2. egy összetett feladat a rekurzió segítségével egyszerűbb alproblémákra bontható.
3. A sorozat generálása könnyebb a rekurzióval, mint néhány beágyazott iteráció használatával.

A rekurzió hátrányai

1. néha a rekurzió mögötti logikát nehéz követni.
2. a rekurzív hívások drágák (nem hatékonyak), mivel sok memóriát és időt vesznek igénybe.
3. a rekurzív függvényeket nehéz hibakeresni.