A rekurzió és a rekurzív képlet megértése

Ismétlés

Az iteráció egy folyamat megismétlése. Az iskolába járó diák megismétli az iskolába járás folyamatát mindennap az érettségiig. Legalább havonta egyszer vagy kétszer járunk élelmiszerboltba termékeket vásárolni. Ezt a folyamatot havonta megismételjük. A matematikában egy Fibonacci-szekvencia követi a feladatismétlés tulajdonságait is. Vegyük figyelembe a Fibonacci szekvenciát, ahol az első két szám 0 és 1, az összes többi szám az előző két szám összege.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

Iterációs lépések

A Fibonacci képlet így írható:

F (n) = F (n - 1) + F (n - 2)
fibonacci (0) = 0
fibonacci (1) = 1
Fibonacci (2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1
fibonacci (3) = fibonacci (2) + fibonacci (1) = 1 + 1 = 2
fibonacci (4) = fibonacci (3) + fibonacci (2) = 2 + 1 = 3
fibonacci (5) = fibonacci (4) + fibonacci (3) = 3 + 2 = 5
fibonacci (6) = fibonacci (5) + fibonacci (4) = 5 + 3 = 8

Az alább megadott algoritmus az n-edik Fibonacci-számot adja vissza.

Rekurzió

Valahányszor kapunk egy új Fibonacci-számot (n-edik szám), amely az n-edik szám valójában (n - 1). Szám, amikor (n + 1) -es Fibonaccit találjuk a következő n-edik Fibonaccinak. Amint látjuk a fent említett iterációs lépéseket: ha n = 2 akkor
Fibonacci (2) = Fibonacci (2 - 1) + Fibonacci (2 - 2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1

Most fibonaccit (3) szeretnénk előállítani, azaz n = 3.

Fibonacci (3) = Fibonacci (3 - 1) + Fibonacci (3 - 2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
Ez azt jelenti, hogy minden egyes alkalommal, amikor n megnöveli az áram értékét (n - 1), és (n - 2) th fibonacci is növekszik. De fárasztó nyomon követni mindegyik n (n - 1) és (n - 2) th fibonaccit. Mit szólnál egy olyan módszer megírásához, amely önmagát hívja az ismétlés feladatának megismételésére?

Az önmagát hívó módszert rekurzív módszernek nevezik. A rekurzív metódusnak rendelkeznie kell olyan alapesettel, amikor a program nem hívja fel önmagát. A Fibonacci-sorozat alapesete a fibonacci (0) = 0 és a fibonacci (1) = 1. Ellenkező esetben a Fibonacci-módszer kétszer nevezi magát - fibonacci (n - 1) és fibonacci (n - 2). Ezután hozzáadja őket, hogy fibonaccit (n) kapjanak. Rekurzív módszer az n-edik Fibonacci megtalálásához így írható:

Ha alaposan megnézzük, a rekurzió követi a verem tulajdonságát. Kisebb részproblémákat old meg, hogy megoldást találjon egy problémára. N> 1 esetén az utolsó sort hajtja végre. Tehát, ha n = 6, akkor a függvény meghívja és összeadja a fibonaccit (6 - 1) és a fibonaccit (6 - 2). a fibonacci (6 - 1) vagy a fibonacci (5) hív, és hozzáteszi a fibonaccit (5 - 1) és a fibonaccit (5 - 2). Ez a rekurzió addig folytatódik, amíg a 6 el nem éri az alapeset értékét, amely a fibonacci (0) = 0 vagy a fibonacci (1) = 1. Amint eléri az alap esetet, két alapértéket ad hozzá, és addig emelkedik, amíg meg nem kapja a fibonacci ( 6). Az alábbiakban a rekurzió fa ábrázolása látható.

rekurziós fa

Mint láthatjuk, milyen nagy lehet a rekurzió. Csak egy kódsor teszi a fenti fát (a fenti kód utolsó sora, beleértve az alapeseteket is). A rekurzió fenntartja a verem és mélyebbre megy, amíg el nem éri az alap esetet. Dinamikus programozás (DP): A rekurzió könnyen érthető és kódolható, de idő és memória szempontjából drága lehet. Vessen egy pillantást az alábbi rekurziós fára. A fib (4) -vel kezdődő bal és a fib (4) -el kezdődő jobb részfa teljesen megegyezik. Ugyanazt az eredményt kapják, amely 3, de kétszer ugyanazt a feladatot látják el. Ha n nagy szám (példa: 500000), akkor a rekurzió nagyon lassúvá teheti a programot, mivel ugyanazon részfeladatot többször is meghívná.

rekurzió Fa körözött

A probléma elkerülése érdekében dinamikus programozás használható. A dinamikus programozás során korábban megoldott részfeladatot használhatunk a jövőbeli azonos típusú feladatok megoldására. Ezáltal csökkenthető az eredeti probléma megoldásának feladata. Legyen egy tömb fib [], ahol tároljuk a korábban megoldott részfeladat-megoldásokat. Azt már tudjuk, hogy a fib [0] = 0 és a fib [1] = 1. Tároljuk ezt a két értéket. Most mi a fib [2] értéke? Mivel a fib [0] = 0 és a fib [1] = 1 már tárolásra került, csak azt kell mondanunk, hogy fib [2] = fib [1] + fib [0], és ez minden. Ugyanígy generálhatunk fib [3], fib [4], fib [5], ……, fib [n]. Korábban megoldott részfeladatokat hívunk a következő részfeladatok megszerzésére, amíg az eredeti feladatot nem oldották meg, ezáltal csökkentve a redundáns számítást.