Les fonctions récursives, Stack Débordements, et Y Combinators

Question

J'ai une fonction récursive (en C #) que je dois appeler à environ 800 millions de fois; cela entraînerait évidemment normalement dans un débordement de pile après sur l'appel 900e. J'ai botté ceci à plusieurs boucles, mais le motif récurrent est tellement plus facile et plus propre à maintenir.

Je cherche à mettre en œuvre la fonction récursive à l'aide d'un y-Combinator, à partir de ce que je lis et vu, cela devrait résoudre le problème de débordement de la pile, et fixer les multiples boucles imbriquées.

Est-ce que quelqu'un a une expérience utilisant l'y combinateur? Est-ce que je serai toujours coincé dans un débordement de pile?

Prenons l'exemple simple d'un factoriel. Un factoriel sur la plupart des nombres supérieurs à 5000 comme provoquera un débordement de pile. Si je un y combinateur correctement dans ce scénario, serait-il corriger le débordement de la pile?

Il ne semble pas trivial à mettre en œuvre, alors je veux le confirmer avant que je passe l'effort de développement des ressources / mise en œuvre et l'apprentissage de la y-Combinator.

Answer 1

Non, en utilisant le Y-Combinator ne va pas aider votre situation. Si vous avez besoin de faire quelque chose de 800 millions de fois, vous pouvez (a) récursion, ou (b) boucle (ou je suppose que (c) écrire 800 millions d'appels à votre fonction). Étant donné que le Y-Combinator ne boucle pas, il faut donc récursion.

Une boucle est ce que vous cherchez, à moins que vous utilisez un environnement d'exécution qui offre récursion queue appropriée (comme schéma).

Cela dit, la mise en œuvre du Y-Combinator à partir de zéro dans la langue de votre choix est un excellent exercice.

Answer 2

Y Combinator sont utiles, mais je pense que vous voulez vraiment la queue récursion optimisation qui élimine l'utilisation de la pile pour les fonctions récursives de la queue. récursion Tail est possible uniquement lorsque le résultat de chaque appel récursif est immédiatement renvoyée par l'appelant et jamais calcul supplémentaire après l'appel. Malheureusement C # ne prend pas en charge l'optimisation de récursion de queue mais vous pouvez émuler avec un trampoline qui permet une simple conversion de méthode récursive de la queue à une méthode gainés de trampoline.

// Tail
int factorial( int n ) { return factorialTail( n, 1, 1 ); }
int factorialTail( int n, int i, int acc ) {
  if ( n < i ) return acc;
  else return factorialTail( n, i + 1, acc * i );
}

// Trampoline
int factorialTramp( int n ) { 
   var bounce = new Tuple<bool,int,int>(true,1,1);
   while( bounce.Item1 ) bounce = factorialOline( n, bounce.Item2, bounce.Item3 );
   return bounce.Item3;
}
Tuple<bool,int,int> factorialOline( int n, int i, int acc ) {
  if ( n < i ) return new Tuple<bool,int,int>(false,i,acc);
  else return new Tuple<bool,int,int>(true,i + 1,acc * i);
}

Answer 3

Vous pouvez utiliser le trampoline comme il est utilisé dans Reactive Extension, j'ai essayé de l'expliquer sur mon blog http://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/

Answer 4

Une solution consiste à convertir votre fonction (s) d'utiliser une boucle et un explicite contexte structure de données. Le contexte représente ce que les gens pensent généralement que la pile d'appel. Vous trouverez peut-être ma réponse à une autre question sur la conversion de la récursion arrière utile. Les étapes correspondantes sont de 1 à 5; 6 et 7 sont spécifiques à cette fonction particulière, alors que les sons de vôtre plus compliqué.

L'alternative « facile », cependant, est d'ajouter un compteur de profondeur à chacune de vos fonctions; quand il frappe une certaine limite (déterminée par l'expérimentation), frayer un nouveau thread pour continuer la récursion avec une nouvelle pile. Les anciens blocs de fil d'attente pour le nouveau thread pour envoyer un résultat (ou si vous voulez être de fantaisie, un résultat ou une exception à re-raise). Le compteur de profondeur remonte à 0 pour le nouveau fil; quand il frappe la limite, créer un troisième fil, et ainsi de suite. Si vous mettez en cache des fils pour éviter de payer le coût de la création de fil plus souvent que nécessaire, nous espérons que vous aurez des performances acceptables sans avoir à restructurer radicalement votre programme.