Iteration
Iteration er gentagelse af en proces. En studerende, der går i skole, gentager processen med at gå i skole hver dag indtil eksamen. Vi går i en købmand mindst en eller to gange om måneden for at købe produkter. Vi gentager denne proces hver måned. I matematik følger en Fibonacci-sekvens også egenskaberne ved opgavegentagelse. Lad os overveje Fibonacci-sekvensen, hvor de første to tal er 0 og 1, alle andre tal er summen af de foregående to tal.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Iterationstrin
Fibonacci-formlen kan skrives 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 angivet nedenfor returnerer det femte Fibonacci-nummer.
Rekursion
Hver gang vi får et nyt Fibonacci-nummer (n-tal), er det n-tal faktisk (n - 1) th-tal, når vi finder (n + 1) Fibonacci som vores næste n'te Fibonacci. Som vi ser ovennævnte iterationstrin: hvis n = 2 så
Fibonacci (2) = Fibonacci (2 - 1) + Fibonacci (2 - 2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1
Nu vil vi generere retracement (3), det vil sige n = 3.
Fibonacci (3) = Fibonacci (3 - 1) + Fibonacci (3 - 2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
Det betyder, at hver gang n øger værdien af strømmen (n - 1) th og (n - 2) th øger også. Men det er trættende at holde styr på (n - 1) th og (n - 2) th Fibonacci for hver n. Hvad med at skrive en metode, der kalder sig selv til at gentage opgaven med iteration af sig selv?
En metode, der kalder sig selv, navngives som rekursiv metode. En rekursiv metode skal have en basissag, hvor programmet holder op med at kalde sig selv. Vores basissag for Fibonacci-serien er Fibonacci (0) = 0 og Fibonacci (1) = 1. Ellers kalder Fibonacci-metoden sig to gange - Fibonacci (n - 1) og Fibonacci (n - 2). Derefter tilføjer det dem for at få retracement (n). En rekursiv metode til at finde den niende Fibonacci kan skrives som -
Hvis vi ser nøje, følger rekursion stakens egenskab. Det løser mindre delproblemer for at få løsningen på et problem. For n> 1 udfører den sidste linje. Så hvis n = 6, kaldes og tilføjer funktionen Fibonacci (6 - 1) og Fibonacci (6 - 2). Fibonacci (6 - 1) eller Fibonacci (5) opkald og tilføjer Fibonacci (5 - 1) og Fibonacci (5 - 2). Denne rekursion fortsætter, indtil 6 når ned til sin base-sagsværdi, som er Fibonacci (0) = 0 eller Fibonacci (1) = 1. Når den først rammer basissagen, tilføjer den to basisværdier og går op, indtil den får værdien af Fibonacci ( 6). Nedenfor er en trærepræsentation af rekursion.
rekursionstræ
Som vi kan se, hvor kraftig en rekursion kan være. Kun en enkelt linje med kode opretter træet ovenfor (sidste linje i koden ovenfor inklusive basissager). Rekursion opretholder en stak, og den går dybere ned, indtil den når basissagen. Dynamisk programmering (DP): Rekursion er let at forstå og kode, men det kan være dyrt med hensyn til tid og hukommelse. Se på rekursionstræet nedenfor. Det venstre undertræ, der starter med fib (4) og det højre undertræ, der starter med fib (4), er nøjagtigt det samme. De genererer det samme resultat, som er 3, men laver den samme opgave to gange. Hvis n er et stort tal (eksempel: 500000), kan rekursion gøre et program meget langsomt, da det ville kalde den samme underopgave flere gange.
rekursion Træcirklet
For at undgå dette problem kan dynamisk programmering bruges. I dynamisk programmering kan vi bruge tidligere løst underopgave til at løse fremtidig opgave af samme type. Dette er en måde at reducere opgaven til at løse originale problemer på. Lad os have en matrixfib [], hvor vi gemmer tidligere løste delopgaveløsninger. Vi ved allerede, at fib [0] = 0 og fib [1] = 1. Lad os gemme disse to værdier. Hvad er værdien af fib [2] nu? Da fib [0] = 0 og fib [1] = 1 allerede er lagret, skal vi bare sige fib [2] = fib [1] + fib [0], og det er alt. Vi kan generere fib [3], fib [4], fib [5], ……, fib [n] på samme måde. Tidligere løste underopgaver kaldes for at få næste delopgave, indtil den oprindelige opgave ikke er løst, hvilket reducerer overflødig beregning.
