Analyse sur la prévention des erreurs de débordement de pile récursif en JavaScript

Il est vraiment une figure de niveau divin et doit être vénéré. Apprenez humblement

Récursion de la queue

Une fonction qui s'appelle elle-même est appelée récursivité. Si la queue s'appelle elle-même, on parle de récursion de la queue.

La récursion consomme beaucoup de mémoire, car des milliers ou des centaines de trames d'appel doivent être enregistrées en même temps, et des erreurs de « débordement de pile » peuvent facilement se produire. Mais pour la récursion de queue, puisqu'il n'y a qu'une seule trame d'appel, une erreur de « débordement de pile » ne se produira jamais.

Exemple 1

function factorial(n) {
  if (n === 1) return 1;  return n * factorial(n - 1);
}

factorial(5) // 120

Le code ci-dessus est une fonction factorielle pour calculer la factorielle de n, jusqu'à n enregistrements d'appels doivent être enregistrés et la complexité est O(n). .

Si réécrit en récursion de queue, un seul enregistrement d'appel est conservé, la complexité est O(1)

function factorial(n, total) {
  if (n === 1) return total;  return factorial(n - 1, n * total);
}

factorial(5, 1) // 120

Exemple 2

Il existe un autre exemple célèbre, celui Le calcul de la séquence de Fibonacci peut également illustrer pleinement l'importance de l'optimisation récursive de la queue.

La séquence de Fibonacci récursive sans queue est implémentée comme suit.

function Fibonacci (n) {
  if ( n <= 1 ) {return 1};  return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci(10) // 89Fibonacci(100) // 堆栈溢出, 亲测页面直接卡死, cpu: i7-4720Fibonacci(500) // 堆栈溢出

Après l'optimisation

function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
  if( n <= 1 ) {return ac2};  return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}

Fibonacci2(100) // 573147844013817200000Fibonacci2(1000) // 7.0330367711422765e+208 非一般的速度Fibonacci2(10000) // Infinity

Optimisation de la récursion de queue

L'optimisation de la récursion de queue ne prend effet qu'en mode strict, puis en mode normal, ou ceux qui ne le prennent pas en charge feature Dans cet environnement, existe-t-il un moyen d'utiliser également l'optimisation de la récursion de queue ? La réponse est oui, il vous suffit d'implémenter vous-même l'optimisation de la récursion de queue.

Son principe est très simple. La raison pour laquelle la récursion de queue doit être optimisée est que trop de piles d'appels provoquent un débordement. Ainsi, tant que la pile d'appels est réduite, il n'y aura pas de débordement. Que peut-on faire pour réduire la pile d’appels ? Utilisez simplement "boucle" au lieu de "récursion".

Ce qui suit est une fonction récursive normale.

function sum(x, y) {
  if (y > 0) {    return sum(x + 1, y - 1);
  } else {    return x;
  }
}sum(1, 100000)// Uncaught RangeError: Maximum call stack size exceeded(…)

Dans le code ci-dessus, sum est une fonction récursive, le paramètre x est la valeur qui doit être accumulée et le paramètre y contrôle le nombre de récursions. Une fois que la somme est spécifiée pour être récursive 100 000 fois, une erreur sera signalée, indiquant que le nombre maximum de piles d'appels a été dépassé.

La fonction trampoline peut convertir une exécution récursive en exécution cyclique.

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }  return f;
}

Ce qui précède est une implémentation de la fonction trampoline, qui accepte une fonction f comme paramètre. Tant que f renvoie une fonction après l'exécution, l'exécution continue. Notez qu'ici, nous renvoyons une fonction, puis exécutons la fonction au lieu d'appeler la fonction à l'intérieur de la fonction. Cela évite l'exécution récursive et élimine le problème d'une pile d'appels trop volumineuse.

Ensuite, il ne vous reste plus qu'à réécrire la fonction récursive d'origine pour renvoyer une autre fonction à chaque étape.

function sum(x, y) {
  if (y > 0) {    return sum.bind(null, x + 1, y - 1);
  } else {    return x;
  }
}

Dans le code ci-dessus, chaque exécution de la fonction somme renverra une autre version d'elle-même.

Désormais, en utilisant la fonction trampoline pour exécuter sum, aucun débordement de pile d'appels ne se produira.

trampoline(sum(1, 100000))// 100001

La fonction trampoline n'est pas une véritable optimisation récursive de queue, l'implémentation suivante est .

Voici le point important, vétérans

function tco(f) {
  var value;  var active = false;  var accumulated = [];  return function accumulator() {
    accumulated.push(arguments);//每次将参数传入. 例如, 1 100000
    if (!active) {
      active = true;      
      while (accumulated.length) {//出循环条件, 当最后一次返回一个数字而不是一个函数时, accmulated已经被shift(), 所以出循环
        value = f.apply(this, accumulated.shift());//调用累加函数, 传入每次更改后的参数, 并执行
      }
      active = false;      
      return value;
    }
  };
}var sum = tco(function(x, y) {
  if (y > 0) {    
  return sum(x + 1, y - 1)//重点在这里, 每次递归返回真正函数其实还是accumulator函数
  }  
  else {    
  return x
  }
});

sum(1, 100000);//实际上现在sum函数就是accumulator函数// 100001

Dans le code ci-dessus, la fonction tco est l'implémentation de l'optimisation récursive de queue, et son secret réside dans la variable d'état actif. Par défaut, cette variable est inactive. Une fois le processus d’optimisation récursive de queue entré, cette variable est activée. Ensuite, chaque tour de somme récursive renvoie un résultat indéfini, donc l'exécution récursive est évitée ; et le tableau accumulé stocke les paramètres de chaque tour d'exécution de somme et est toujours précieux, ce qui garantit que la boucle while à l'intérieur de la fonction d'accumulateur sera toujours exécutée. De cette façon, « récursivité » est intelligemment changé en « boucle », et les paramètres du tour suivant remplaceront les paramètres du tour précédent, garantissant qu'il n'y a qu'une seule couche de la pile d'appels.

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!