Pochopenie rekurzie a rekurzívnej formuly

Iterácia

Iterácia je opakovanie procesu. Študent, ktorý chodí do školy, opakuje proces chodenia do školy každý deň až do ukončenia štúdia. Aspoň raz alebo dvakrát mesačne chodíme nakupovať do potravín. Tento postup opakujeme každý mesiac. V matematike sleduje Fibonacciho postupnosť aj vlastnosti opakovania úloh. Uvažujme Fibonacciho postupnosť, kde prvé dve čísla sú 0 a 1, všetky ostatné čísla sú súčtom predchádzajúcich dvoch čísel.

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

Iteračné kroky

Fibonacciho vzorec možno napísať ako,

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

Algoritmus uvedený nižšie vráti n-té Fibonacciho číslo.

Rekurzia

Zakaždým, keď dostaneme nové Fibonacciho číslo (n-té číslo), toto n-té číslo je v skutočnosti (n - 1) th číslo, keď nájdeme (n + 1) th Fibonacci ako náš ďalší n-tý Fibonacci. Ako vidíme vyššie uvedené iteračné kroky: if n = 2 then
Fibonacci (2) = Fibonacci (2 - 1) + Fibonacci (2 - 2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1

Teraz chceme generovať fibonacci (3), teda n = 3.

Fibonacci (3) = Fibonacci (3 - 1) + Fibonacci (3 - 2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
To znamená, že zakaždým, keď n zvýši hodnotu aktuálneho (n - 1) th, (n - 2) th, fibonacci sa tiež zvýši. Je však namáhavé sledovať (n - 1) a (n - 2) th fibonacci pre každé n. Čo tak napísať metódu, ktorá si hovorí, že opakuje úlohu iterácie sama?

Metóda, ktorá si hovorí, sa nazýva rekurzívna metóda. Rekurzívna metóda musí mať základný prípad, keď sa program prestane volať sám. Náš základný prípad pre sériu Fibonacci je fibonacci (0) = 0 a fibonacci (1) = 1. Inak si Fibonacciho metóda hovorí dvakrát - fibonacci (n - 1) a fibonacci (n - 2). Potom ich pridáva, aby dostali fibonacci (n). Rekurzívnu metódu na nájdenie n-tého Fibonacciho možno napísať ako -

Ak sa pozrieme pozorne, rekurzia sleduje vlastnosť zásobníka. Rieši menšie podproblémy, aby získal riešenie problému. Pre n> 1 vykoná posledný riadok. Ak je teda n = 6, funkcia zavolá a pridá fibonacci (6 - 1) a fibonacci (6 - 2). fibonacci (6 - 1) alebo fibonacci (5) volá a pridáva fibonacci (5 - 1) a fibonacci (5 - 2). Táto rekurzia pokračuje, kým 6 nedosiahne svoju základnú hodnotu prípadu, ktorá je fibonacci (0) = 0 alebo fibonacci (1) = 1. Akonáhle zasiahne základný prípad, pridá dve základné hodnoty a bude stúpať, kým nezíska hodnotu fibonacci ( 6). Nižšie je uvedené stromové zastúpenie rekurzie.

rekurzívny strom

Ako vidíme, aká silná môže byť rekurzia. Iba jeden riadok kódu vytvára strom vyššie (posledný riadok kódu vyššie vrátane základných prípadov). Rekurzia udržuje zásobník a ide do hlbšej, kým nedosiahne základný prípad. Dynamické programovanie (DP): Rekurzia je ľahko pochopiteľná a programovateľná, ale môže byť drahá z hľadiska času a pamäte. Zoznámte sa s rekurzívnym stromom nižšie. Ľavý podstrom začínajúci s fib (4) a pravý podstrom začínajúci s fib (4) sú úplne rovnaké. Generujú rovnaký výsledok, ktorý je 3, ale robia rovnakú úlohu dvakrát. Ak je n veľké číslo (príklad: 500000), potom môže rekurzia spôsobiť, že program bude veľmi pomalý, pretože by viackrát vyvolal tú istú podúlohu.

rekurzia Strom krúžil

Aby sa zabránilo tomuto problému, je možné použiť dynamické programovanie. V dynamickom programovaní môžeme na riešenie budúcich úloh rovnakého typu použiť predtým vyriešenú podúlohu. Toto je spôsob, ako znížiť úlohu pri riešení pôvodného problému. Poďme mať pole fib [], kde ukladáme predtým vyriešené riešenia podúloh. Už vieme, že fib [0] = 0 a fib [1] = 1. Uložme si tieto dve hodnoty. Aká je teraz hodnota fib [2]? Pretože fib [0] = 0 a fib [1] = 1 už boli uložené, musíme povedať iba fib [2] = fib [1] + fib [0] a to je všetko. Rovnakým spôsobom môžeme generovať fib [3], fib [4], fib [5], ……, fib [n]. Predtým vyriešené podúlohy sa volajú, aby získali ďalšiu podúlohu, kým sa nevyrieši pôvodná úloha, čím sa redukuje nadbytočný výpočet.