Förstå rekursion och rekursiv formel

Iteration

Iteration är upprepning av en process. En student som går i skolan upprepar processen att gå till skolan varje dag fram till examen. Vi går till mataffären minst en eller två gånger i månaden för att köpa produkter. Vi upprepar denna process varje månad. I matematik följer också en Fibonacci-sekvens egenskaperna för upprepningsupprepning. Låt oss överväga Fibonacci-sekvensen där de två första siffrorna är 0 och 1, alla andra siffror är summan av de två föregående siffrorna.

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

Iterationssteg

Fibonacci-formeln kan skrivas som,

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

Algoritmen som anges nedan returnerar det nionde Fibonacci-numret.

Rekursion

Varje gång vi får ett nytt Fibonacci-nummer (n: te nummer) är det n: e numret faktiskt (n - 1): e nummer när vi hittar (n + 1): e Fibonacci som vår nästa n: e Fibonacci. Som vi ser ovan nämnda iterationssteg: om n = 2 då
Fibonacci (2) = Fibonacci (2 - 1) + Fibonacci (2 - 2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1

Nu vill vi generera Fibonacci (3), det vill säga n = 3.

Fibonacci (3) = Fibonacci (3 - 1) + Fibonacci (3 - 2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
Det betyder att varje gång n ökar ökar också värdet på strömmen (n - 1) och (n - 2). Men det är tröttsamt att hålla reda på (n - 1) och (n - 2) femte för varje n. Vad sägs om att skriva en metod som kallar sig själv att upprepa uppgiften med iteration av sig själv?

En metod som kallar sig själv heter som rekursiv metod. En rekursiv metod måste ha ett basfall där programmet slutar ringa sig själv. Vårt basfall för Fibonacci-serien är Fibonacci (0) = 0 och Fibonacci (1) = 1. Annars kallar Fibonacci-metoden sig två gånger - Fibonacci (n - 1) och Fibonacci (n - 2). Sedan lägger det till dem för att få retracement (n). En rekursiv metod för att hitta nionde Fibonacci kan skrivas som -

Om vi ​​tittar noga följer rekursion stackens egenskap. Det löser mindre delproblem för att få lösningen på ett problem. För n> 1 kör den sista raden. Så om n = 6, Funktionen ringer och lägger till Fibonacci (6 - 1) och Fibonacci (6 - 2). Fibonacci (6 - 1) eller Fibonacci (5) samtal och lägger till Fibonacci (5 - 1) och Fibonacci (5 - 2). Denna rekursion fortsätter tills 6 når ner till sitt basfallsvärde som är Fibonacci (0) = 0 eller Fibonacci (1) = 1. När det når basfallet lägger det till två basvärden och går upp tills det får värdet av Fibonacci 6). Nedan är en trädrepresentation av rekursion.

rekursionsträd

Som vi kan se, hur kraftfull en rekursion kan vara. Endast en enda kodrad skapar trädet ovan (sista raden i koden ovan inklusive basfall). Rekursion upprätthåller en stack och den går djupare tills den når basfodralet. Dynamisk programmering (DP): Rekursion är lätt att förstå och koda men kan vara dyrt när det gäller tid och minne. Ta en titt på rekursionsträdet nedan. Det vänstra underträdet som börjar med fib (4) och det högra underträdet som börjar med fib (4) är exakt samma. De genererar samma resultat som är 3 men gör samma uppgift två gånger. Om n är ett stort nummer (exempel: 500000) kan rekursion göra ett program mycket långsamt eftersom det skulle kalla samma underuppgift flera gånger.

rekursion Trädcirklat

För att undvika detta problem kan dynamisk programmering användas. I dynamisk programmering kan vi använda tidigare lösta underuppgifter för att lösa framtida uppgifter av samma typ. Detta är ett sätt att minska uppgiften för att lösa originalproblem. Låt oss ha en array fib [] där vi lagrar tidigare lösta underuppgiftslösningar. Vi vet redan att fib [0] = 0 och fib [1] = 1. Låt oss lagra dessa två värden. Vad är värdet på fib [2] nu? Eftersom fib [0] = 0 och fib [1] = 1 redan har lagrats måste vi bara säga fib [2] = fib [1] + fib [0] och det är allt. Vi kan generera fib [3], fib [4], fib [5], ……, fib [n] på samma sätt. Tidigare lösta underuppgifter kallas för att få nästa deluppgift tills den ursprungliga uppgiften inte har lösts, vilket minskar redundant beräkning.