Pochopení rekurze a rekurzivního vzorce

Opakování

Iterace je opakování procesu. Student, který chodí do školy, opakuje proces chodit do školy každý den až do ukončení studia. Minimálně jednou nebo dvakrát za měsíc chodíme nakupovat do obchodů s potravinami. Tento postup opakujeme každý měsíc. V matematice sleduje Fibonacciho sekvence také vlastnosti opakování úkolu. Uvažujme Fibonacciho posloupnost, kde první dvě čísla jsou 0 a 1, všechna ostatní čísla jsou součtem předchozích dvou čísel.

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

Iterační kroky

Fibonacciho vzorec lze psát jako,

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ý níže vrací n-tý Fibonacciho číslo.

Rekurze

Pokaždé, když dostaneme nové Fibonacciho číslo (n-té číslo), toto n-té číslo je ve skutečnosti (n - 1) th číslo, když najdeme (n + 1) th Fibonacci jako náš další n-tý Fibonacci. Jak vidíme výše uvedené iterační kroky: if n = 2 then
Fibonacci (2) = Fibonacci (2 - 1) + Fibonacci (2 - 2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1

Nyní chceme generovat fibonacci (3), tedy n = 3.

Fibonacci (3) = Fibonacci (3 - 1) + Fibonacci (3 - 2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
To znamená, že pokaždé, když n zvyšuje hodnotu aktuálního (n - 1) th a (n - 2) th, zvyšuje se také fibonacci. Je ale únavné sledovat (n - 1) th a (n - 2) th fibonacci pro každé n. Co takhle napsat metodu, která si volá opakovat iterační úlohu sama?

Metoda, která se sama nazývá, je pojmenována jako rekurzivní metoda. Rekurzivní metoda musí mít základní případ, kdy se program přestane volat sám. Náš základní případ pro řadu Fibonacci je fibonacci (0) = 0 a fibonacci (1) = 1. Jinak se Fibonacciho metoda nazývá dvakrát - fibonacci (n - 1) a fibonacci (n - 2). Pak je přidá k získání fibonacci (n). Rekurzivní metodu pro nalezení n-tého Fibonacciho lze zapsat jako -

Podíváme-li se pečlivě, rekurze sleduje vlastnost zásobníku. Řeší menší dílčí problémy, aby získal řešení problému. Pro n> 1 provede poslední řádek. Pokud je tedy n = 6, funkce zavolá a přidá fibonacci (6 - 1) a fibonacci (6 - 2). fibonacci (6 - 1) nebo fibonacci (5) volá a přidává fibonacci (5 - 1) a fibonacci (5 - 2). Tato rekurze pokračuje, dokud 6 nedosáhne své základní hodnoty případu, což je fibonacci (0) = 0 nebo fibonacci (1) = 1. Jakmile narazí na základní případ, přidá dvě základní hodnoty a jde nahoru, dokud nezíská hodnotu fibonacci ( 6). Níže je stromová reprezentace rekurze.

rekurzivní strom

Jak vidíme, jak silná může být rekurze. Pouze jeden řádek kódu vytváří strom výše (poslední řádek kódu výše včetně základních případů). Rekurze udržuje zásobník a jde do hloubky, dokud nedosáhne základního případu. Dynamické programování (DP): Rekurze je snadno pochopitelná a kódovatelná, ale může být nákladná z hlediska času a paměti. Podívejte se níže na rekurzivní strom. Levý podstrom začínající fib (4) a pravý podstrom začínající fib (4) jsou přesně stejné. Generují stejný výsledek, který je 3, ale dělají stejný úkol dvakrát. Pokud n je velké číslo (příklad: 500000), může rekurze způsobit, že program bude velmi pomalý, protože by několikrát zavolal stejný dílčí úkol.

rekurze Strom kroužil

Aby se tomuto problému předešlo, lze použít dynamické programování. V dynamickém programování můžeme použít dříve vyřešený dílčí úkol k řešení budoucího úkolu stejného typu. Jedná se o způsob, jak snížit úlohu při řešení původního problému. Pojďme mít pole fib [], kde ukládáme dříve vyřešená řešení podúloh. Už víme, že fib [0] = 0 a fib [1] = 1. Uložme si tyto dvě hodnoty. Jaká je nyní hodnota fib [2]? Protože fib [0] = 0 a fib [1] = 1 již byly uloženy, musíme jen říct fib [2] = fib [1] + fib [0] a to je vše. Můžeme generovat fib [3], fib [4], fib [5], ……, fib [n] stejným způsobem. Dříve řešené dílčí úkoly jsou volány k získání dalšího dílčího úkolu, dokud nebude vyřešen původní úkol, čímž se sníží nadbytečný výpočet.