Welche Methoden gibt es, um einen Stapelüberlauf in einem rekursiven Algorithmus zu vermeiden?

Frage

Wie kann ein durch einen rekursiven Algorithmus verursachter Stapelüberlauf behoben werden?

Beispiel

Ich versuche das Project Euler-Problem 14 zu lösen und habe beschlossen, es mit einem rekursiven Algorithmus zu versuchen. Das Programm stoppt jedoch mit einem java.lang.StackOverflowError. Verständlicherweise. Der Algorithmus hat den Stack tatsächlich überlaufen lassen, weil ich versucht habe, eine Collatz-Sequenz für eine sehr große Anzahl zu generieren.

Lösungen

Also habe ich mich gefragt: Welche Standardmethoden gibt es, um einen Stapelüberlauf zu lösen, wenn Ihr rekursiver Algorithmus korrekt geschrieben wurde und der Stapel immer überlaufen würde? Zwei Konzepte, die mir in den Sinn kamen, waren:

1. Schwanzrekursion
2. Wiederholung

Sind die Ideen (1) und (2) richtig? Gibt es noch andere Möglichkeiten?

Bearbeiten

Es wäre hilfreich, Code zu sehen, vorzugsweise in Java, C #, Groovy oder Scala.

Verwenden Sie das oben erwähnte Project Euler-Problem möglicherweise nicht, damit es nicht für andere verwöhnt wird, sondern verwenden Sie einen anderen Algorithmus. Factorial vielleicht oder so ähnlich.

Die Tail-Call-Optimierung ist in vielen Sprachen und Compilern vorhanden. In dieser Situation erkennt der Compiler eine Funktion der Form:

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

Hier kann die Sprache erkennen, dass das zurückgegebene Ergebnis das Ergebnis einer anderen Funktion ist, und einen Funktionsaufruf mit einem neuen Stapelrahmen in einen Sprung umwandeln.

Beachten Sie, dass die klassische Fakultätsmethode:

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

ist wegen der bei der rückgabe notwendigen inspektion nicht schwanzrufoptimierbar. ( Beispiel für Quellcode und kompilierte Ausgabe )

Um diesen Tail Call zu optimieren,

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);
}

Kompilieren Sie diesen Code mit gcc -O2 -S fact.c(-O2 ist erforderlich, um die Optimierung im Compiler zu ermöglichen, aber mit mehr Optimierungen von -O3 wird es für einen Menschen schwer zu lesen ...)

_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

( Beispiel für Quellcode und kompilierte Ausgabe )

Man kann in dem Segment sehen .L3, die jneeher als ein call(das macht einen Subroutinen - Aufruf mit einem neuen Stapelrahmen).

Beachten Sie, dass dies mit C durchgeführt wurde. Die Optimierung von Tail-Aufrufen in Java ist schwierig und hängt von der JVM-Implementierung ab (ich habe jedoch noch keine davon gesehen, da dies schwierig ist und Auswirkungen auf das erforderliche Java-Sicherheitsmodell hat, das Stack-Frames erfordert - was TCO vermeidet) - Tail-Recursion + Java und Tail-Recursion + Optimierung sind gute Tag-Sets zum Durchsuchen. Sie können andere JVM Sprachen sind in der Lage zu optimieren Endrekursion finden besser (try clojure (die die erfordert recur zu Endrekursion optimize) oder scala).

Das gesagt,

Es ist eine gewisse Freude zu wissen, dass Sie etwas richtig geschrieben haben - auf die ideale Art und Weise, wie es getan werden kann.
_{^{Und jetzt hole ich mir einen Scotch und ziehe eine deutsche Electronica an ...}}

Zur allgemeinen Frage "Methoden zur Vermeidung eines Stapelüberlaufs in einem rekursiven Algorithmus" ...

Ein anderer Ansatz besteht darin, einen Rekursionszähler einzuschließen. Dies dient eher zum Erkennen von Endlosschleifen, die durch Situationen verursacht werden, auf die man keinen Einfluss hat (und durch schlechte Codierung).

Der Rekursionszähler hat die Form von

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

Bei jedem Anruf erhöhen Sie den Zähler. Wenn der Zähler zu groß wird, tritt ein Fehler auf (hier nur eine Rückgabe von -1, in anderen Sprachen möchten Sie möglicherweise eine Ausnahme auslösen). Damit soll verhindert werden, dass bei einer Rekursion, die viel tiefer als erwartet ist und wahrscheinlich eine Endlosschleife darstellt, schlimmere Ereignisse (Speicherfehler) auftreten.

Theoretisch sollte man das nicht brauchen. In der Praxis habe ich schlecht geschriebenen Code gesehen, der dies aufgrund einer Vielzahl von kleinen Fehlern und schlechten Codierungspraktiken getroffen hat (Multithread-Probleme, bei denen etwas außerhalb der Methode geändert wird, wodurch ein anderer Thread in eine Endlosschleife rekursiver Aufrufe gerät).

Verwenden Sie den richtigen Algorithmus und lösen Sie das richtige Problem. Speziell für die Collatz-Vermutung scheint es , dass Sie versuchen, sie auf die xkcd- Weise zu lösen :

Du beginnst bei einer Zahl und machst eine Baumquerung. Dies führt schnell zu einem sehr großen Suchraum. Ein schneller Durchlauf zur Berechnung der Anzahl der Iterationen für die richtige Antwort führt zu etwa 500 Schritten. Dies sollte kein Problem für die Rekursion mit einem kleinen Stapelrahmen sein.

Das Wissen um die rekursive Lösung ist zwar keine schlechte Sache, man sollte jedoch auch erkennen, dass die iterative Lösung um ein Vielfaches besser ist . Eine Reihe von Möglichkeiten, einen rekursiven Algorithmus in einen iterativen zu konvertieren, finden Sie unter Stapelüberlauf auf dem Weg von der Rekursion zur Iteration .

Beachten Sie, dass die Sprachimplementierung die Optimierung der Schwanzrekursion unterstützen muss. Ich glaube nicht, dass es die großen Java-Compiler tun.

Memoisierung bedeutet, dass Sie sich an das Ergebnis einer Berechnung erinnern, anstatt es jedes Mal neu zu berechnen.

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]

Wenn Sie jede Sequenz mit weniger als einer Million berechnen, wird es am Ende der Sequenzen eine Menge Wiederholungen geben. Memoization macht es zu einer schnellen Suche in der Hash-Tabelle nach vorherigen Werten, anstatt den Stack immer tiefer und tiefer machen zu müssen.

Ich bin überrascht, dass noch niemand Trampolinspringen erwähnt hat. Ein Trampolin (in diesem Sinne) ist eine Schleife, die Thunk-Return-Funktionen (Continuation-Passing-Stil) iterativ aufruft und zum Implementieren von schwanzrekursiven Funktionsaufrufen in einer stapelorientierten Programmiersprache verwendet werden kann.

Diese Frage Stackoverflow geht in ziemlich viel ausführlicher über die verschiedenen Implementierungen von trampolining in Java: Umgang mit Stackoverflow in Java für Trampoline

Wenn Sie eine Sprache und einen Compiler verwenden, die rekursive Funktionen erkennen und ordnungsgemäß verarbeiten (dh "den Anrufer durch den Angerufenen ersetzen"), sollte der Stack nicht außer Kontrolle geraten. Diese Optimierung reduziert eine rekursive Methode im Wesentlichen auf eine iterative. Ich glaube nicht, dass Java dies tut, aber ich weiß, dass es Racket tut.

Wenn Sie sich für einen iterativen und nicht für einen rekursiven Ansatz entscheiden, müssen Sie sich nicht mehr lange daran erinnern, woher die Aufrufe stammen, und die Wahrscheinlichkeit eines Stapelüberlaufs (bei rekursiven Aufrufen ohnehin) praktisch ausschließen.

Memoization ist großartig und kann die Gesamtzahl der Methodenaufrufe reduzieren, indem zuvor berechnete Ergebnisse in einem Cache nachgeschlagen werden, da Ihre Gesamtberechnung viele kleinere, wiederholte Berechnungen erfordert. Diese Idee ist großartig - sie ist auch unabhängig davon, ob Sie einen iterativen oder einen rekursiven Ansatz verwenden.

Sie könnten eine Aufzählung erstellen, die die Rekursion ersetzt ... hier ist ein Beispiel für die Berechnung der Fakultät, die dies tut ... (funktioniert nicht für große Zahlen, da ich im Beispiel nur lange gebraucht habe :-))

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++;
        }
    }
}

Selbst wenn dies keine Speicherung ist, wird auf diese Weise ein Stapelüberlauf verhindert

BEARBEITEN

Es tut mir leid, wenn ich einige von Ihnen verärgert habe. Meine einzige Absicht war es, einen Weg aufzuzeigen, wie ein Stapelüberlauf vermieden werden kann. Ich hätte wahrscheinlich ein vollständiges Codebeispiel schreiben sollen, anstatt nur ein kleines Stück eines schnell geschriebenen und groben Codeauszugs.

Der folgende Code

• vermeidet Rekursion, da ich die benötigten Werte iterativ berechne.
• enthält die Speicherung als Bereits berechnete Werte werden gespeichert und abgerufen, wenn sie bereits berechnet wurden
• Enthält auch eine Stoppuhr, sodass Sie sehen können, dass die Speicherung ordnungsgemäß funktioniert

... ähm ... wenn Sie es ausführen, stellen Sie sicher, dass Ihr Kommando-Shell-Fenster einen Puffer von 9999 Zeilen hat ... die üblichen 300 reichen nicht aus, um die Ergebnisse des folgenden Programms durchzuarbeiten ...

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");
       }
    }

Ich deklariere * 1 statische Variable "instance" in der Faculty-Klasse, um einen Singleton zu speichern. Auf diese Weise erhalten Sie immer dann, wenn Sie "GetInstance ()" der Klasse ausführen, die Instanz, in der alle bereits berechneten Werte gespeichert sind. * 1 statische SortedList, die alle bereits berechneten Werte enthält

Im Konstruktor füge ich auch 2 Sonderwerte der Liste 1 für die Eingänge 0 und 1 hinzu.

    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;

        }
    }
}

Wie bei Scala können Sie die @tailrecAnmerkung zu einer rekursiven Methode hinzufügen . Auf diese Weise stellt der Compiler sicher, dass die Tail Call-Optimierung tatsächlich stattgefunden hat:

Das wird also nicht kompiliert (Fakultät):

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

Die Fehlermeldung lautet:

scala: @tailrec annotierte Methode konnte nicht optimiert werden fak1: Es enthält einen rekursiven Aufruf, der sich nicht in der Endposition befindet

Auf der anderen Seite:

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)
}

kompiliert und Tail-Call-Optimierung stattgefunden.

Eine Möglichkeit, die noch nicht erwähnt wurde, ist die Rekursion, jedoch ohne Verwendung eines Systemstacks. Natürlich können Sie Ihren Heap auch überlaufen lassen, aber wenn Ihr Algorithmus wirklich ein Backtracking in der einen oder anderen Form benötigt (warum überhaupt eine Rekursion verwenden?), Haben Sie keine andere Wahl.

Es gibt stapellose Implementierungen einiger Sprachen, z . B. stapelloses Python .

Eine andere Lösung wäre, Ihren eigenen Stack zu simulieren und sich nicht auf die Implementierung des Compilers + der Laufzeit zu verlassen. Dies ist keine einfache und auch keine schnelle Lösung, aber theoretisch erhalten Sie StackOverflow nur, wenn Sie nicht genügend Arbeitsspeicher haben.