Comprensió de la recursivitat i la fórmula recursiva

Iteració

La iteració és la repetició d’un procés. Un estudiant que va a l'escola repeteix el procés d'anar a l'escola cada dia fins a la graduació. Anem a una botiga de queviures almenys una o dues vegades al mes per comprar productes. Repetim aquest procés cada mes. En matemàtiques, una seqüència de Fibonacci també segueix les propietats de la repetició de tasques. Considerem la seqüència de Fibonacci on els dos primers números són 0 i 1, la resta de números són la suma dels dos números anteriors.

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

Passos d’iteració

La fórmula de Fibonacci es pot escriure com:

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

L'algoritme que es mostra a continuació retorna l'enèsim número de Fibonacci.

Recursivitat

Cada vegada que obtenim un nou número de Fibonacci (enèsim número), aquest enèsim número és en realitat (n - 1) número número quan trobem (n + 1) número Fibonacci com el nostre proper enèsim Fibonacci. Com veiem els passos d’iteració esmentats anteriorment: si n = 2 llavors
Fibonacci (2) = Fibonacci (2 - 1) + Fibonacci (2 - 2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1

Ara volem generar Fibonacci (3), és a dir, n = 3.

Fibonacci (3) = Fibonacci (3 - 1) + Fibonacci (3 - 2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
Això significa que cada vegada que n augmenta el valor del corrent (n - 1) th i (n - 2) th Fibonacci també augmenta. Però és cansat fer un seguiment de (n - 1) i (n - 2) de Fibonacci per a cada n. Què tal escriure un mètode que es diu a si mateix per repetir la tasca de la iteració per si mateix?

Un mètode que s’autodenomina s’anomena mètode recursiu. Un mètode recursiu ha de tenir un cas bàsic en què el programa deixi de cridar-se. El nostre cas bàsic per a la sèrie de Fibonacci és Fibonacci (0) = 0 i Fibonacci (1) = 1. En cas contrari, el mètode Fibonacci s’anomena a si mateix dues vegades: Fibonacci (n - 1) i Fibonacci (n - 2). Després els afegeix per obtenir fibonacci (n). Un mètode recursiu per trobar l'enèsim Fibonacci es pot escriure com -

Si observem detingudament, la recursió segueix la propietat de la pila. Resol subproblemes més petits per obtenir la solució d’un problema. Per a n> 1, executa l'última línia. Per tant, si n = 6, la funció crida i afegeix fibonacci (6 - 1) i fibonacci (6 - 2). Fibonacci (6 - 1) o Fibonacci (5) crida i afegeix Fibonacci (5 - 1) i Fibonacci (5 - 2). Aquesta recursió continua fins que el 6 arriba fins al seu valor de cas base que és Fibonacci (0) = 0 o Fibonacci (1) = 1. Un cop toca el cas base, afegeix dos valors base i puja fins a obtenir el valor de Fibonacci ( 6). A continuació es mostra una representació en arbre de la recursió.

arbre de recursió

Com podem veure, fins a quin punt pot ser una recursió. Només una sola línia de codi crea l'arbre superior (última línia del codi anterior, inclosos els casos bàsics). La recursió manté una pila i va més a fons fins que arriba a la caixa base. Programació dinàmica (DP): la recursió és fàcil d’entendre i codificar, però pot ser costós en termes de temps i memòria. Feu un cop d'ull a l'arbre de recursió que hi ha a continuació. El subarbre esquerre que comença per fib (4) i el subarbre dret que comença per fib (4) són exactament iguals. Generen el mateix resultat, que és 3, però estan fent la mateixa tasca dues vegades. Si n és un nombre gran (exemple: 500000), la recursió pot fer que un programa sigui molt lent, ja que anomenaria la mateixa sub tasca diverses vegades.

recursió Cercle arbre

Per evitar aquest problema es pot utilitzar programació dinàmica. En la programació dinàmica podem utilitzar subtasks resolts prèviament per resoldre futures tasques del mateix tipus. Aquesta és una manera de reduir la tasca per resoldre el problema original. Tenim una matriu fib [] on emmagatzemem solucions de subtasques resoltes prèviament. Ja sabem que fib [0] = 0 i fib [1] = 1. Emmagatzemem aquests dos valors. Ara, quin és el valor de fib [2]? Com que fib [0] = 0 i fib [1] = 1 ja s'han emmagatzemat, només hem de dir fib [2] = fib [1] + fib [0] i això és tot. Podem generar fib [3], fib [4], fib [5], ……, fib [n] de la mateixa manera. S’està cridant subtasques resoltes prèviament per obtenir la següent subtasca fins que la tasca original no s’hagi resolt, de manera que es redueix el càlcul redundant.