Razumevanje rekurzije in rekurzivne formule

Ponavljanje

Ponavljanje je ponavljanje procesa. Učenec, ki gre v šolo, ponavlja postopek obiskovanja šole vsak dan do mature. Vsaj enkrat ali dvakrat mesečno gremo v trgovino po izdelke. Ta postopek ponovimo vsak mesec. V matematiki Fibonaccijevo zaporedje sledi tudi lastnostim ponavljanja nalog. Upoštevajmo Fibonaccijevo zaporedje, kjer sta prvi dve števili 0 in 1, vsa druga števila pa so vsota prejšnjih dveh števil.

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

Koraki ponovitve

Formulo Fibonacci lahko zapišemo kot,

F (n) = F (n - 1) + F (n - 2)
fibonači (0) = 0
fibonači (1) = 1
Fibonacci (2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1
fibonači (3) = fibonači (2) + fibonači (1) = 1 + 1 = 2
fibonači (4) = fibonači (3) + fibonači (2) = 2 + 1 = 3
fibonači (5) = fibonači (4) + fibonači (3) = 3 + 2 = 5
fibonači (6) = fibonači (5) + fibonači (4) = 5 + 3 = 8

Spodnji algoritem vrne n-to Fibonaccijevo število.

Rekurzija

Vsakič, ko dobimo novo Fibonaccijevo število (n-to število), je to n-to število dejansko (n - 1) -to število, ko najdemo (n + 1) -ti Fibonacci kot naslednjega n-tega Fibonaccija. Kot vidimo zgoraj omenjene iteracijske korake: če je n = 2, potem
Fibonacci (2) = Fibonacci (2 - 1) + Fibonacci (2 - 2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1

Zdaj želimo ustvariti fibonacci (3), to je n = 3.

Fibonacci (3) = Fibonacci (3 - 1) + Fibonacci (3 - 2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
To pomeni, da vsakič, ko n poveča vrednost trenutnega (n - 1) th in (n - 2) th fibonacija, se poveča. Toda utrujajoče je spremljati (n - 1) th in (n - 2) th fibonacije za vsak n. Kaj pa pisanje metode, ki sama zahteva, da nalogo ponovitve ponovi sama?

Metoda, ki se sama pokliče, je poimenovana kot rekurzivna metoda. Rekurzivna metoda mora imeti osnovni primer, ko se program neha klicati sam. Naš osnovni primer za Fibonaccijevo serijo je fibonacci (0) = 0 in fibonacci (1) = 1. V nasprotnem primeru se Fibonaccijeva metoda dvakrat pokliče - fibonacci (n - 1) in fibonacci (n - 2). Nato jih doda, da dobijo fibonacci (n). Rekurzivno metodo za iskanje n-tega Fibonaccija lahko zapišemo kot -

Če natančno pogledamo, rekurzija sledi lastnosti sklada. Rešuje manjše podprobleme, da bi dobili rešitev problema. Za n> 1 izvrši zadnjo vrstico. Torej, če je n = 6, funkcija pokliče in doda fibonacci (6 - 1) in fibonacci (6 - 2). fibonacci (6 - 1) ali fibonacci (5) pokliče in doda fibonacci (5 - 1) in fibonacci (5 - 2). Ta rekurzija se nadaljuje, dokler 6 ne doseže osnovne vrednosti, ki je fibonacci (0) = 0 ali fibonacci (1) = 1. Ko zadene osnovni primer, doda dve osnovni vrednosti in gre navzgor, dokler ne dobi vrednosti fibonacci ( 6). Spodaj je drevesna predstavitev rekurzije.

drevo rekurzije

Kot lahko vidimo, kako močna je lahko rekurzija. Le ena vrstica kode ustvarja drevo zgoraj (zadnja vrstica zgornje kode, vključno z osnovnimi primeri). Rekurzija ohranja sklad in gre globlje, dokler ne doseže osnovnega primera. Dinamično programiranje (DP): Rekurzijo je enostavno razumeti in kodirati, vendar je lahko časovno in pomnilniško drago. Oglejte si drevo rekurzije spodaj. Levo poddrevo, ki se začne s fib (4), in desno poddrevo, ki se začne s fib (4), sta popolnoma enaki. Ustvarijo enak rezultat, ki je 3, vendar dvakrat naredijo isto nalogo. Če je n veliko število (primer: 500000), lahko rekurzija program zelo počasi, saj bi večkrat poklicala isto podologo.

rekurzija Drevesno obkrožena

Da bi se temu izognili, lahko uporabimo dinamično programiranje. Pri dinamičnem programiranju lahko uporabimo predhodno rešeno podopravilo za reševanje prihodnjih istovrstnih nalog. To je način za zmanjšanje naloge za reševanje prvotnega problema. Imejmo matriko fib [], kamor shranimo predhodno rešene rešitve podopravil. Že vemo, da je fib [0] = 0 in fib [1] = 1. Shranimo ti dve vrednosti. Kolikšna je vrednost fib [2]? Ker sta bili fib [0] = 0 in fib [1] = 1 že shranjeni, moramo samo reči fib [2] = fib [1] + fib [0] in to je vse. Na enak način lahko ustvarimo fib [3], fib [4], fib [5], ……, fib [n]. Prej rešene podopravila se pokličejo, da dobijo naslednjo podopravilo, dokler prvotna naloga ni rešena, s čimer se zmanjša odvečni izračun.