Analyse du code de comparaison des performances de récursivité et de boucle JavaScript

En termes de performances, la récursivité n'a aucun avantage sur les boucles. En plus de la surcharge liée aux appels de fonctions multiples, la récursivité peut également conduire à des calculs répétés inutiles dans certains cas. Prenons, par exemple, un programme récursif qui calcule la séquence de Fibonacci. Lors de la recherche du nième élément A(n), à partir du n-2ème élément, chaque élément est calculé à plusieurs reprises. Plus le nombre d’éléments est petit, plus il est répété plusieurs fois. Soit B(i) le nombre de fois où le i-ème élément est calculé, alors il y a

B(i)=1 ; i=n, ​​​​n-1

B; (i)=B(i +1)+B(i+2); i
De cette façon, B(i) forme une séquence de Fibonacci inverse intéressante. En trouvant A(n), nous avons :

B(i)=A(n+1-i)

En le regardant sous un autre angle, soit C(i) pour trouver A(i) Le nombre d'ajouts requis est :

C(i)=0; i=0, 1 -1

Soit D(i)=C(); i)+1, il y a

D(i)=1; i=0, 1

D(i)=D(i-1)+D(i-1)

Donc D(i) forme une autre séquence de Fibonacci. Et on peut conclure :

C(n)=A(n+1)-1

Et A(n) grandit dans une série géométrique, cette répétition redondante dans n Cela devient tout à fait étonnant quand il est plus grand. Le programme correspondant utilisant des boucles a

B(n)=1; n est n'importe quelle valeur

C(n)=0; n=0, 1

C(n )=n-1; n>1

Par conséquent, lorsque n est grand, le programme utilisant les boucles donné ci-dessus sera beaucoup plus rapide que le programme utilisant la récursion.

Comme les boucles, ce défaut de récursion peut aussi être comblé. Il suffit de se souvenir des termes qui ont été calculés et, lorsque nous trouvons des termes plus élevés, nous pouvons lire directement les termes précédents. Cette technique est courante en récursion et s'appelle la mémorisation.

Ce qui suit est un algorithme récursif pour trouver la séquence de Fibonacci à l'aide de la technologie de stockage.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!