Iteracija
Iteracija je ponavljanje procesa. Učenik koji ide u školu ponavlja postupak odlaska u školu svaki dan do mature. Idemo u trgovinu barem jednom ili dva puta mjesečno kako bismo kupili proizvode. Taj postupak ponavljamo svaki mjesec. U matematici Fibonaccijev niz slijedi i svojstva ponavljanja zadatka. Razmotrimo Fibonaccijev niz gdje su prva dva broja 0 i 1, svi ostali brojevi su zbroj prethodna dva broja.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Koraci ponavljanja
Fibonaccijevu formulu možemo zapisati kao,
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
Dolje dani algoritam vraća n-ti Fibonaccijev broj.
Rekurzija
Svaki put kad dobijemo novi Fibonaccijev broj (n-ti broj) taj je n-ti broj zapravo (n - 1) -ti broj kada pronađemo (n + 1) -ti Fibonacci kao sljedeći n-ti Fibonacci. Kao što vidimo gore spomenute iteracijske korake: ako je n = 2 tada
Fibonacci (2) = Fibonacci (2 - 1) + Fibonacci (2 - 2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1
Sada želimo generirati fibonacci (3), to jest n = 3.
Fibonacci (3) = Fibonacci (3 - 1) + Fibonacci (3 - 2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
To znači da se svaki put kada n povećava vrijednost struje (n - 1) th i (n - 2) th fibonacci također povećava. Ali zamorno je pratiti (n - 1) i i (n - 2) th fibonacije za svaki n. Što kažete na to da napišete metodu koja sebe poziva da sama ponovi zadatak iteracije?
Metoda koja sebe poziva naziva se rekurzivnom metodom. Rekurzivna metoda mora imati osnovni slučaj kada program prestaje sam sebe pozivati. Naš osnovni slučaj za Fibonaccijevu seriju je fibonacci (0) = 0 i fibonacci (1) = 1. Inače, Fibonaccijeva metoda sebe naziva dva puta - fibonacci (n - 1) i fibonacci (n - 2). Zatim ih dodaje da dobiju fibonacci (n). Rekurzivna metoda za pronalaženje n-tog Fibonaccija može se zapisati kao -
Ako pažljivo pogledamo, rekurzija slijedi svojstvo stoga. Rješava manje potprobleme da bi se dobilo rješenje problema. Za n> 1 izvršava posljednji redak. Dakle, ako je n = 6, funkcija poziva i dodaje fibonacci (6 - 1) i fibonacci (6 - 2). fibonacci (6 - 1) ili fibonacci (5) poziva i dodaje fibonacci (5 - 1) i fibonacci (5 - 2). Ova se rekurzija nastavlja sve dok 6 ne dosegne svoju osnovnu vrijednost slučaja koja je fibonacci (0) = 0 ili fibonacci (1) = 1. Jednom kada pogodi osnovni slučaj dodaje dvije osnovne vrijednosti i ide prema gore dok ne dobije vrijednost fibonacci ( 6). Ispod je prikaz stabla rekurzije.
Drvo rekurzije
Kao što vidimo, koliko rekurzija može biti moćna. Samo jedan redak koda izrađuje stablo gore (zadnji redak gornjeg koda, uključujući osnovne slučajeve). Rekurzija održava hrpu i ide dublje dok ne dođe do osnovnog kućišta. Dinamičko programiranje (DP): Rekurziju je lako razumjeti i kodirati, ali može biti skupo u smislu vremena i memorije. Pogledajte dolje drvo rekurzije. Lijevo podstablo koje počinje s fib (4) i desno poddrvo koje počinje s fib (4) potpuno su jednake. Oni generiraju isti rezultat koji je 3, ali dva puta rade isti zadatak. Ako je n velik broj (primjer: 500000), tada rekurzija može program učiniti vrlo sporim jer bi isti podzadatak pozivao više puta.
rekurzija Okružen stablom
Da bi se izbjegao ovaj problem, može se koristiti dinamičko programiranje. U dinamičkom programiranju možemo koristiti prethodno riješeni podzadatak za rješavanje budućih zadataka iste vrste. Ovo je način za smanjenje zadatka za rješavanje izvornog problema. Imajmo niz fib [] gdje pohranjujemo prethodno riješena rješenja podzadataka. Već znamo da je fib [0] = 0 i fib [1] = 1. Pohranimo ove dvije vrijednosti. Sad, kolika je vrijednost fib [2]? Kako su fib [0] = 0 i fib [1] = 1 već pohranjeni, samo moramo reći fib [2] = fib [1] + fib [0] i to je sve. Na isti način možemo generirati fib [3], fib [4], fib [5], ……, fib [n]. Prethodno riješene podzadaće pozivaju se da bi se dobio sljedeći podzadatak dok izvorni zadatak ne bude riješen, što smanjuje suvišni izračun.
