Înțelegerea recursivității și a formulei recursive

Repetare

Iterarea este repetarea unui proces. Un elev care merge la școală repetă procesul de a merge la școală în fiecare zi până la absolvire. Mergem la magazin alimentar cel puțin o dată sau de două ori pe lună pentru a cumpăra produse. Repetăm ​​acest proces în fiecare lună. În matematică, o secvență Fibonacci urmărește și proprietățile repetării sarcinilor. Să luăm în considerare secvența Fibonacci în care primele două numere sunt 0 și 1, toate celelalte numere sunt suma celor două numere anterioare.

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

Pași de iterație

Formula Fibonacci poate fi scrisă ca:

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

Algoritmul dat mai jos întoarce numărul Fibonacci.

Recursivitate

De fiecare dată când obținem un nou număr Fibonacci (al nouălea număr) acel al doilea număr este de fapt (n - 1) al treilea număr atunci când găsim (n + 1) al doilea Fibonacci ca al nouălea al nostru Fibonacci. După cum vedem pașii de iterație menționați mai sus: dacă n = 2 atunci
Fibonacci (2) = Fibonacci (2 - 1) + Fibonacci (2 - 2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1

Acum, vrem să generăm Fibonacci (3), adică n = 3.

Fibonacci (3) = Fibonacci (3 - 1) + Fibonacci (3 - 2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
Asta înseamnă că de fiecare dată când n crește valoarea curentului (n - 1) al treilea și (n - 2) al Fibonacci crește, de asemenea. Dar este obositor să țineți evidența (n - 1) a și (n - 2) a Fibonacci pentru fiecare n. Ce zici de scrierea unei metode care se cheamă să repete singură sarcina de iterație?

O metodă care se numește singură este denumită metodă recursivă. O metodă recursivă trebuie să aibă un caz de bază în care programul încetează să se apeleze singur. Cazul nostru de bază pentru seria Fibonacci este Fibonacci (0) = 0 și Fibonacci (1) = 1. În caz contrar, metoda Fibonacci se numește de două ori - Fibonacci (n - 1) și Fibonacci (n - 2). Apoi le adaugă pentru a obține fibonacci (n). O metodă recursivă pentru găsirea celui de-al nouălea Fibonacci poate fi scrisă ca -

Dacă privim cu atenție, recursivitatea urmează proprietatea stivei. Rezolvă subprobleme mai mici pentru a obține soluția unei probleme. Pentru n> 1, execută ultima linie. Deci, dacă n = 6, funcția apelează și adaugă fibonacci (6 - 1) și fibonacci (6 - 2). Fibonacci (6 - 1) sau Fibonacci (5) apelează și adaugă Fibonacci (5 - 1) și Fibonacci (5 - 2). Această recursivitate continuă până când 6 ajunge la valoarea cazului de bază, care este Fibonacci (0) = 0 sau Fibonacci (1) = 1. Odată ce atinge cazul de bază, adaugă două valori de bază și crește până când obține valoarea Fibonacci 6). Mai jos este o reprezentare în arbore a recursivității.

arborele recursiv

După cum putem vedea, cât de puternică poate fi o recursivitate. Doar o singură linie de cod face arborele de deasupra (ultima linie a codului de mai sus, inclusiv majuscule). Recursivitatea menține un teanc și merge mai adânc până ajunge la carcasa de bază. Programare dinamică (DP): recursivitatea este ușor de înțeles și codificat, dar poate fi costisitoare în ceea ce privește timpul și memoria. Aruncați o privire la arborele recursiv de mai jos. Subarborele stâng începând cu fib (4) și subarborele drept începând cu fib (4) sunt exact aceleași. Acestea generează același rezultat, care este 3, dar fac aceeași sarcină de două ori. Dacă n este un număr mare (exemplu: 500000), atunci recursivitatea poate face un program foarte lent, deoarece ar numi aceeași subactivitate de mai multe ori.

recursiune Arborele cercuit

Pentru a evita această problemă poate fi utilizată programarea dinamică. În programarea dinamică putem folosi o subtask rezolvată anterior pentru a rezolva sarcina viitoare de același tip. Acesta este un mod de a reduce sarcina pentru rezolvarea problemei originale. Să avem o matrice fib [] în care stocăm soluții de subtask rezolvate anterior. Știm deja că fib [0] = 0 și fib [1] = 1. Să stocăm aceste două valori. Acum, care este valoarea fib [2]? Deoarece fib [0] = 0 și fib [1] = 1 au fost deja stocate, trebuie doar să spunem fib [2] = fib [1] + fib [0] și atât. Putem genera fib [3], fib [4], fib [5], ……, fib [n] în același mod. Subtaskurile rezolvate anterior sunt apelate pentru a obține următoarea subtask până când sarcina originală nu a fost rezolvată, reducând astfel calculul redundant.