Atkārtojums
Iterācija ir procesa atkārtošanās. Skolēns, kurš dodas uz skolu, ikdienā līdz skolas beigšanai atkārto procesu. Vismaz vienu vai divas reizes mēnesī dodamies uz pārtikas preču veikalu, lai iegādātos produktus. Mēs atkārtojam šo procesu katru mēnesi. Matemātikā Fibonači secība seko arī uzdevumu atkārtošanas īpašībām. Apskatīsim Fibonači secību, kur pirmie divi skaitļi ir 0 un 1, visi pārējie skaitļi ir iepriekšējo divu skaitļu summa.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Iterācijas soļi
Fibonači formulu var uzrakstīt šādi:
F (n) = F (n - 1) + F (n - 2)
fibonacci (0) = 0
fibonacci (1) = 1
Fibonači (2) = Fibonači (1) + Fibonači (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
Zemāk sniegtais algoritms atgriež n-to Fibonači skaitli.
Rekursija
Katru reizi, kad mēs iegūstam jaunu Fibonači numuru (n-to numuru), šis n-tais skaitlis faktiski ir (n - 1) trešais skaitlis, kad mēs atrodam (n + 1) trešo Fibonači kā nākamo n-to Fibonači. Kā redzam iepriekš minētās iterācijas darbības: ja n = 2, tad
Fibonači (2) = Fibonači (2 - 1) + Fibonači (2 - 2) = Fibonači (1) + Fibonači (0) = 1 + 0 = 1
Tagad mēs vēlamies ģenerēt fibonacci (3), tas ir, n = 3.
Fibonači (3) = Fibonači (3 - 1) + Fibonači (3 - 2) = Fibonači (2) + Fibonači (1) = 1 + 1 = 2
Tas nozīmē, ka katru reizi, kad n palielina strāvas (n - 1) vērtību, palielinās arī (n - 2) th fibonači. Bet ir nogurdinoši sekot (n - 1) un (n - 2) th fibonacci katram n. Kā būtu ar tādas metodes uzrakstīšanu, kas pati sevi atkārto iterācijas uzdevumu?
Metode, kas sevi sauc, tiek nosaukta par rekursīvo metodi. Rekursīvai metodei ir jābūt bāzes gadījumam, kad programma pārstāj sevi saukt. Mūsu Fibonači sērijas pamata gadījums ir fibonači (0) = 0 un fibonači (1) = 1. Pretējā gadījumā Fibonači metode sevi dēvē divreiz - fibonači (n - 1) un fibonači (n - 2). Tad tas tos pievieno, lai iegūtu fibonacci (n). Rekursīvo metodi n-tā Fibonači atrašanai var uzrakstīt kā -
Ja mēs uzmanīgi skatāmies, rekursija seko kaudzes īpašībai. Tas atrisina mazākas apakšproblēmas, lai iegūtu problēmas risinājumu. Ja n> 1, tā izpilda pēdējo rindu. Tātad, ja n = 6, funkcija izsauc un pievieno fibonacci (6 - 1) un fibonacci (6 - 2). fibonacci (6 - 1) vai fibonacci (5) zvana un pievieno fibonacci (5 - 1) un fibonacci (5 - 2). Šī rekursija turpinās, līdz 6 sasniedz leju līdz tās pamata gadījuma vērtībai, kas ir fibonacci (0) = 0 vai fibonacci (1) = 1. Pēc tam, kad tas sasniedz bāzes gadījumu, tas pievieno divas bāzes vērtības un iet uz augšu, līdz iegūst fibonacci ( 6). Zemāk ir rekursijas koku attēlojums.
rekursijas koks
Kā redzam, cik spēcīga var būt rekursija. Augšdaļā esošo koku veido tikai viena koda rindiņa (augšējā koda pēdējā rindiņa, ieskaitot bāzes gadījumus). Rekursija saglabā kaudzi, un tā nonāk dziļāk, līdz tā sasniedz pamata lietu. Dinamiskā programmēšana (DP): rekursija ir viegli saprotama un kodējama, taču tā var būt dārga laika un atmiņas ziņā. Apskatiet zemāk esošo rekursijas koku. Kreisais apakškoks, kas sākas ar fib (4), un labais apakškoks, kas sākas ar fib (4), ir tieši tāds pats. Viņi ģenerē to pašu rezultātu, kas ir 3, bet to pašu uzdevumu veic divas reizes. Ja n ir liels skaitlis (piemērs: 500000), tad rekursija var padarīt programmu ļoti lēnu, jo tā vairākas reizes izsauktu vienu un to pašu apakšuzdevumu.
rekursija Kokā riņķota
Lai izvairītos no šīs problēmas, var izmantot dinamisko programmēšanu. Dinamiskā programmēšanā mēs varam izmantot iepriekš atrisinātu apakšuzdevumu tāda paša veida nākotnes uzdevuma risināšanai. Tas ir veids, kā samazināt uzdevumu sākotnējās problēmas risināšanai. Pieņemsim masīvu fib [], kur mēs glabājam iepriekš atrisinātus apakšuzdevumu risinājumus. Mēs jau zinām, ka fib [0] = 0 un fib [1] = 1. Saglabāsim šīs divas vērtības. Kāda ir fib [2] vērtība? Tā kā fib [0] = 0 un fib [1] = 1 jau ir saglabāti, mums vienkārši jāsaka fib [2] = fib [1] + fib [0], un tas ir viss. Tādā pašā veidā mēs varam ģenerēt fib [3], fib [4], fib [5], ……, fib [n]. Lai atrisinātu nākamo apakšuzdevumu, tiek izsaukti iepriekš atrisināti apakšuzdevumi, līdz sākotnējais uzdevums nav atrisināts, tādējādi samazinot lieko aprēķinu.
