Quelles sont les méthodes pour éviter un débordement de pile dans un algorithme récursif?

Question

Quels sont les moyens possibles pour résoudre un débordement de pile causé par un algorithme récursif?

Exemple

J'essaie de résoudre le problème 14 du projet Euler et j'ai décidé de l'essayer avec un algorithme récursif. Toutefois, le programme s’arrête avec une erreur java.lang.StackOverflowError. Naturellement. L'algorithme a en effet débordé de la pile car j'ai essayé de générer une séquence de Collatz pour un très grand nombre.

Solutions

Je me demandais donc: de quelle manière standard existe-t-il pour résoudre un débordement de pile en supposant que votre algorithme récursif a été écrit correctement et finirait toujours par déborder de la pile? Deux concepts qui me sont venus à l’esprit étaient:

1. récursion de la queue
2. itération

Les idées (1) et (2) sont-elles correctes? Y a-t-il d'autres options?

modifier

Il serait utile de voir du code, de préférence en Java, C #, Groovy ou Scala.

N'utilisez peut-être pas le problème de Project Euler mentionné ci-dessus pour ne pas gâcher d'autres, mais utilisez un autre algorithme. Factorielle peut-être, ou quelque chose de similaire.

L'optimisation des appels en queue est présente dans de nombreux langages et compilateurs. Dans cette situation, le compilateur reconnaît une fonction de la forme:

int foo(n) {
  ...
  return bar(n);
}

Ici, le langage peut reconnaître que le résultat renvoyé est le résultat d'une autre fonction et transformer un appel de fonction avec un nouveau cadre de pile en saut.

Sachez que la méthode factorielle classique:

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

n’est pas optimisable en raison de l’inspection nécessaire lors du retour. ( Exemple de code source et de sortie compilée )

Pour rendre cet appel de queue optimisable,

int _fact(int n, int acc) {
    if(n == 1) return acc;
    return _fact(n - 1, acc * n);
}

int factorial(int n) {
    if(n == 0) return 1;
    return _fact(n, 1);
}

Compiler ce code avec gcc -O2 -S fact.c(le -O2 est nécessaire pour permettre l'optimisation dans le compilateur, mais avec plus d'optimisations de -O3, il devient difficile pour un humain de lire ...)

_fact(int, int):
    cmpl    $1, %edi
    movl    %esi, %eax
    je  .L2
.L3:
    imull   %edi, %eax
    subl    $1, %edi
    cmpl    $1, %edi
    jne .L3
.L2:
    rep ret

( Exemple de code source et de sortie compilée )

On peut voir dans segment .L3, le jneplutôt que a call(qui appelle un sous-programme avec un nouveau cadre de pile).

Veuillez noter que cela a été fait avec C. L’optimisation des appels en Java est difficile et dépend de l’implémentation de la JVM (cela dit, je n’en ai pas vu qui le fasse, car c’est difficile et les implications du modèle de sécurité Java requis nécessitant des cadres de pile - ce que TCO évite) - tail-récursion + java et tail-récursion + optimisation sont de bons ensembles de balises à parcourir. Vous constaterez peut-être que d'autres langages de la machine virtuelle Java sont en mesure d'optimiser davantage la récursion de la queue (essayez clojure (ce qui nécessite l' optimisation de l'appel récurrent à la queue) ou scala).

Cela dit,

Il y a une certaine joie à savoir que vous avez écrit quelque chose de juste - de la manière idéale.
_{^{Et maintenant, je vais chercher du scotch et mettre de la musique électronique allemande ...}}

A la question générale de "méthodes pour éviter un débordement de pile dans un algorithme récursif" ...

Une autre approche consiste à inclure un compteur de récursivité. C’est davantage pour détecter des boucles infinies causées par des situations indépendantes de la volonté (et un mauvais codage).

Le compteur de récurrence prend la forme de

int foo(arg, counter) {
  if(counter > RECURSION_MAX) { return -1; }
  ...
  return foo(arg, counter + 1);
}

Chaque fois que vous passez un appel, vous incrémentez le compteur. Si le compteur devient trop gros, vous obtenez une erreur (ici, un retour de -1, mais dans d'autres langues, vous préférerez peut-être une exception). L'idée est d'empêcher que des choses pires se produisent (erreurs de mémoire insuffisante) lors d'une récursion beaucoup plus profonde que prévu et probablement une boucle infinie.

En théorie, vous ne devriez pas avoir besoin de ça. En pratique, j'ai vu du code mal écrit qui a heurté ce problème en raison d'une pléthore de petites erreurs et de mauvaises pratiques de codage (problèmes de concurrence multithread où quelque chose change quelque chose en dehors de la méthode qui fait passer un autre thread à une boucle infinie d'appels récursifs).

Utilisez le bon algorithme et résolvez le bon problème. Spécifiquement pour la conjecture de Collatz, il apparaît que vous essayez de la résoudre de la manière xkcd :

Vous commencez à un numéro et faites une traversée d’arbres. Cela conduit rapidement à un très grand espace de recherche. Une exécution rapide pour calculer le nombre d'itérations pour la réponse correcte aboutit à environ 500 étapes. Cela ne devrait pas poser de problème pour la récursivité avec un petit cadre de pile.

Bien que connaître la solution récursive ne soit pas une mauvaise chose, il faut également savoir que la solution itérative est souvent préférable . Un certain nombre de façons d’aborder la conversion d’un algorithme récursif en un algorithme itératif s’observe sur Stack Overflow at Way pour passer de la récursion à l’itération .

Gardez à l'esprit que l'implémentation du langage doit prendre en charge l'optimisation de la récursion de la queue. Je ne pense pas que les principaux compilateurs Java le fassent.

La mémorisation signifie que vous vous souvenez du résultat d'un calcul plutôt que de le recalculer à chaque fois, comme ceci:

collatz(i):
    if i in memoized:
        return memoized[i]

    if i == 1:
        memoized[i] = 1
    else if odd(i):
        memoized[i] = 1 + collatz(3*i + 1)
    else
        memoized[i] = 1 + collatz(i / 2)

    return memoized[i]

Lorsque vous calculez chaque séquence de moins d'un million, il y aura beaucoup de répétition à la fin des séquences. La mémoisation en fait une table de hachage rapide pour les valeurs précédentes au lieu de rendre la pile de plus en plus profonde.

Je suis surpris que personne n'ait encore mentionné le trampoline . Un trampoline (en ce sens) est une boucle qui appelle de manière itérative des fonctions renvoyant des thunk (style de continuation continuation) et peut être utilisée pour implémenter des appels de fonction récursifs dans une langue de programmation orientée pile.

Cette question de StackOverflow donne plus de détails sur diverses implémentations du trampoline en Java: Gestion de StackOverflow en Java pour Trampoline

Si vous utilisez un langage et un compilateur qui reconnaissent les fonctions récursives et les gèrent correctement (c.-à-d. "Remplace l'appelant en place avec l'appelé"), la pile ne devrait pas devenir incontrôlable. Cette optimisation réduit essentiellement une méthode récursive à une méthode itérative. Je ne pense pas que Java le fasse, mais je sais que Racket le fait.

Si vous optez pour une approche itérative plutôt que récursive, vous évacuez en grande partie le besoin de se souvenir d'où proviennent les appels et éliminez pratiquement le risque de débordement de pile (des appels récursifs de toute façon).

La mémorisation est excellente et peut réduire le nombre total d'appels de méthode en recherchant les résultats calculés précédemment dans une mémoire cache, étant donné que votre calcul global impliquera de nombreux calculs plus petits et répétés. Cette idée est géniale - elle est également indépendante du fait que vous utilisiez ou non une approche itérative ou récursive.

vous pouvez créer une énumération qui remplacera la récursivité ... voici un exemple pour calculer le nombre de professeurs qui font cela ...

public class Faculty
{

    public static IEnumerable<long> Faculties(long n)
    {
        long stopat = n;

        long x = 1;
        long result = 1;

        while (x <= n)
        {
            result = result * x;
            yield return result;
            x++;
        }
    }
}

même s'il ne s'agit pas d'une mémoisation, vous éviterez ainsi un débordement de pile

MODIFIER

Je suis désolé si j'ai contrarié certains d'entre vous. Ma seule intention était de montrer comment éviter un débordement de pile. J'aurais probablement dû écrire un exemple de code complet au lieu d'un simple extrait de code brut rapidement écrit.

Le code suivant

• évite la récursivité pendant que j'utilise calcule les valeurs requises de manière itérative.
• inclut la mémorisation car les valeurs déjà calculées sont stockées et récupérées si elles sont déjà calculées
• comprend également un chronomètre, de sorte que vous pouvez voir que la mémorisation fonctionne correctement

... euh ... si vous l'exécutez, assurez-vous de configurer votre fenêtre d'interpréteur de commande pour avoir un tampon de 9999 lignes ... les 300 habituelles ne suffiront pas pour passer en revue les résultats du programme ci-dessous ...

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.Timers;

namespace ConsoleApplication1
{
    class Program
    {
        static Stopwatch w = new Stopwatch();
        static Faculty f = Faculty.GetInstance();

        static void Main(string[] args)
        {
            Out(5);
            Out(10);
            Out(-5);
            Out(0);
            Out(1);
            Out(4);
            Out(29);
            Out(30);
            Out(20);
            Out(10000);
            Out(20000);
            Out(19999);
            Console.ReadKey();
        }

        static void Out(BigInteger n)
        {
             try
            {
                w.Reset();
                w.Start();
                var x = f.Calculate(n);
                w.Stop();
                var time = w.ElapsedMilliseconds;
                Console.WriteLine(String.Format("{0} ({2}ms): {1}", n, x, time));
            }
            catch (ArgumentException e)
            {
                Console.WriteLine(e.Message);
            }

            Console.WriteLine("\n\n");
       }
    }

Je déclare * 1 variable statique "instance" dans la classe Faculty à un magasin en singleton. De cette façon, tant que votre programme est en cours d'exécution, chaque fois que vous "GetInstance ()" de la classe, vous obtenez l'instance qui a stocké toutes les valeurs déjà calculées. * 1 SortedList statique qui contiendra toutes les valeurs déjà calculées

Dans le constructeur, j'ajoute également 2 valeurs spéciales de la liste 1 pour les entrées 0 et 1.

    public class Faculty
    {
        private static SortedList<BigInteger, BigInteger> _values; 
        private static Faculty _faculty {get; set;}

        private Faculty ()
        {
            _values = new SortedList<BigInteger, BigInteger>();
            _values.Add(0, 1);
            _values.Add(1, 1);
        }

        public static Faculty GetInstance() {
            _faculty = _faculty ?? new Faculty();
            return _faculty;
        }

        public BigInteger Calculate(BigInteger n) 
        {
            // check if input is smaller 0
            if (n < 0)
                throw new ArgumentException(" !!! Faculty is not defined for values < 0 !!!");

            // if value is not already calculated => do so
            if(!_values.ContainsKey(n))
                Faculties(n);

            // retrieve n! from Sorted List
            return _values[n];
        }

        private static void Faculties(BigInteger n)
        {
            // get the last calculated values and continue calculating if the calculation for a bigger n is required
            BigInteger i = _values.Max(x => x.Key),
                           result = _values[i];

            while (++i <= n)
            {
                CalculateNext(ref result, i);
                // add value to the SortedList if not already done
                if (!_values.ContainsKey(i))
                    _values.Add(i, result);
            }
        }

        private static void CalculateNext(ref BigInteger lastresult, BigInteger i) {

            // put in whatever iterative calculation step you want to do
            lastresult = lastresult * i;

        }
    }
}

Comme pour Scala, vous pouvez ajouter l’ @tailrecannotation à une méthode récursive. De cette façon, le compilateur s'assure que l'optimisation de l'appel final a bien eu lieu:

Donc, cela ne compilera pas (factoriel):

@tailrec
def fak1(n: Int): Int = {
  n match {
    case 0 => 1
    case _ => n * fak1(n - 1)
  }
}

le message d'erreur est:

scala: impossible d'optimiser la méthode annotée @tailrec fak1: elle contient un appel récursif qui n'est pas en position de queue

D'autre part:

def fak3(n: Int): Int = {
  @tailrec
  def fak3(n: Int, result: Int): Int = {
    n match {
      case 0 => result
      case _ => fak3(n - 1, n * result)
    }
  }

  fak3(n, 1)
}

compile, et l'optimisation des appels de queue a eu lieu.

Une possibilité qui n’a pas encore été mentionnée est d’avoir une récursivité, mais sans utiliser de pile système. Bien sûr, vous pouvez également saturer votre segment de mémoire, mais si votre algorithme a vraiment besoin de revenir en arrière sous une forme ou une autre (pourquoi utiliser la récursion autrement?), Vous n'avez pas le choix.

Il existe des implémentations sans pile de certains langages, par exemple Stackless Python .

Une autre solution serait de simuler votre propre pile et de ne pas compter sur l'implémentation du compilateur + runtime. Ce n'est pas une solution simple ni rapide, mais théoriquement, StackOverflow n'est disponible que lorsque vous manquez de mémoire.