Kordus
Iteratsioon on protsessi kordamine. Koolis käiv õpilane kordab koolis käimist kuni lõpetamiseni. Toidupoes käime vähemalt üks või kaks korda kuus tooteid ostmas. Kordame seda protsessi iga kuu. Matemaatikas järgib Fibonacci järjestus ka ülesande kordamise omadusi. Vaatleme Fibonacci järjestust, kus kaks esimest numbrit on 0 ja 1, kõik ülejäänud arvud on kahe eelmise numbri summa.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Kordusetapid
Fibonacci valemi võib kirjutada järgmiselt:
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
Allpool toodud algoritm tagastab n-nda Fibonacci numbri.
Rekursioon
Iga kord, kui saame uue Fibonacci numbri (n-nda numbri), on see n-nda number tegelikult (n - 1) number, kui leiame (n + 1) Fibonacci oma järgmise n-nda Fibonacci nime. Nagu näeme ülalnimetatud kordusetappe: kui n = 2 siis
Fibonacci (2) = Fibonacci (2 - 1) + Fibonacci (2 - 2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1
Nüüd tahame genereerida fibonacci (3), see tähendab n = 3.
Fibonacci (3) = Fibonacci (3 - 1) + Fibonacci (3 - 2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
See tähendab, et iga kord, kui n suurendab voolu (n - 1) väärtust, suureneb ka (n - 2) th fibonacci. Kuid on n-1) ja n-2-nda fibonacci jälgimine iga n puhul väsitav. Kuidas oleks kirjutada meetodit, mis kutsub ennast kordama iteratsiooni ülesannet ise?
Rekursiivseks meetodiks nimetatakse ennast kutsuvat meetodit. Rekursiivsel meetodil peab olema alusjuhtum, kus programm lõpetab enda helistamise. Meie Fibonacci seeria põhijuht on fibonacci (0) = 0 ja fibonacci (1) = 1. Vastasel juhul nimetab Fibonacci meetod end kaks korda - fibonacci (n - 1) ja fibonacci (n - 2). Siis lisab see need fibonacci (n) saamiseks. Rekursiivse meetodi n-nda Fibonacci leidmiseks võib kirjutada järgmiselt:
Kui me hoolikalt vaatame, järgib rekursioon virna omadust. See lahendab väiksemad alamprobleemid probleemi lahenduse saamiseks. Kui n> 1, täidab see viimase rea. Niisiis, kui n = 6, kutsub funktsioon üles ja lisab fibonacci (6 - 1) ja fibonacci (6 - 2). fibonacci (6 - 1) või fibonacci (5) kutsub ja lisab fibonacci (5 - 1) ja fibonacci (5 - 2). See rekursioon kestab seni, kuni 6 jõuab alla baasjuhtumi väärtuseni, mis on fibonacci (0) = 0 või fibonacci (1) = 1. Kui see jõuab baasjuhtumini, lisab see kaks baasväärtust ja tõuseb üles, kuni saab fibonacci väärtuse ( 6). Allpool on rekursiooni puu esitus.
rekursioonipuu
Nagu näeme, kui tugev võib olla rekursioon. Ainult üks koodirida teeb ülaltoodud puu (ülaltoodud koodi viimane rida koos põhijuhtudega). Rekursioon säilitab virna ja see läheb sügavamale, kuni jõuab alusjuhtumini. Dünaamiline programmeerimine (DP): rekursiooni on lihtne mõista ja kodeerida, kuid see võib olla kulukas nii aja kui ka mälu osas. Heitke pilk allpool olevale rekursioonipuule. Fibiga (4) algav vasak alampuu ja fibiga (4) algav parem alampuu on täpselt samad. Nad genereerivad sama tulemuse, mis on 3, kuid teevad sama ülesannet kaks korda. Kui n on suur arv (näide: 500000), võib rekursioon muuta programmi väga aeglaseks, kuna see kutsuks sama alamülesannet mitu korda.
rekursioon Puu ümber
Selle probleemi vältimiseks saab kasutada dünaamilist programmeerimist. Dünaamilises programmeerimises saame sama tüüpi tulevaste ülesannete lahendamiseks kasutada varem lahendatud alaülesannet. See on viis vähendada ülesannet algse probleemi lahendamiseks. Olgu massiiv fib [], kuhu salvestame varem lahendatud alaülesande lahendused. Teame juba, et fib [0] = 0 ja fib [1] = 1. Hoidkem need kaks väärtust. Mis on fib [2] väärtus? Kuna fib [0] = 0 ja fib [1] = 1 on juba salvestatud, peame lihtsalt ütlema fib [2] = fib [1] + fib [0] ja see on kõik. Samamoodi saame genereerida fib [3], fib [4], fib [5], ……, fib [n]. Varem lahendatud alamülesandeid kutsutakse järgmise alamülesande saamiseks seni, kuni algne ülesanne pole lahendatud, vähendades seega ülearust arvutust.
