Jakie są metody uniknięcia przepełnienia stosu w algorytmie rekurencyjnym?

Pytanie

Jakie są możliwe sposoby rozwiązania problemu przepełnienia stosu spowodowanego przez algorytm rekurencyjny?

Przykład

Próbuję rozwiązać problem Project Euler 14 i postanowiłem spróbować z algorytmem rekurencyjnym. Jednak program zatrzymuje się z java.lang.StackOverflowError. Zrozumiały. Algorytm rzeczywiście przepełnił stos, ponieważ próbowałem wygenerować sekwencję Collatz dla bardzo dużej liczby.

Rozwiązania

Zastanawiałem się więc: jakie są standardowe sposoby rozwiązania problemu przepełnienia stosu, zakładając, że algorytm rekurencyjny został napisany poprawnie i zawsze kończy się przepełnieniem stosu? Dwie koncepcje, które przyszły mi do głowy:

1. rekurencja ogona
2. iteracja

Czy pomysły (1) i (2) są prawidłowe? Czy są inne opcje?

Edytować

Pomoże to zobaczyć kod, najlepiej w Javie, C #, Groovy lub Scala.

Być może nie używaj wspomnianego powyżej problemu Project Euler, aby nie zepsuć się innym, ale weź inny algorytm. Może silnia lub coś podobnego.

Optymalizacja wywołania ogona jest obecna w wielu językach i kompilatorach. W tej sytuacji kompilator rozpoznaje funkcję formularza:

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

Tutaj język jest w stanie rozpoznać, że zwracany wynik jest wynikiem innej funkcji i zmienić wywołanie funkcji z nową ramką stosu na skok.

Zrozum, że klasyczna metoda czynnikowa:

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

nie jest optymalizowany na podstawie ogona z powodu koniecznej kontroli po powrocie. ( Przykładowy kod źródłowy i skompilowane dane wyjściowe )

Aby zoptymalizować to połączenie z ogonem,

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

Kompilowanie tego kodu za pomocą gcc -O2 -S fact.c(-O2 jest konieczne, aby umożliwić optymalizację w kompilatorze, ale przy większej optymalizacji -O3 trudno jest odczytać człowiekowi ...)

_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

( Przykładowy kod źródłowy i skompilowane dane wyjściowe )

Widać w segmencie .L3, jnea nie w call(który wywołuje podprogram z nową ramką stosu).

Należy pamiętać, że zostało to zrobione przy użyciu C. Optymalizacja wywołania Tail w Javie jest trudna i zależy od implementacji JVM (co powiedziawszy, nie widziałem tego, ponieważ to jest trudne i implikacje wymaganego modelu bezpieczeństwa Java wymagającego ramek stosu - czego unika całkowity koszt posiadania) - rekursja ogona + Java i rekursja ogona + optymalizacja to dobre zestawy znaczników do przeglądania. Można znaleźć inne języki JVM są w stanie optymalizować rekursji ogonowej lepiej (Clojure try (co wymaga ponownie wystąpi zadzwonić ogon Optimize) lub Scala).

To mówi,

Jest pewna radość, wiedząc, że napisałeś coś dobrze - w idealny sposób, aby to zrobić.
_{^{A teraz wezmę trochę szkockiej i założę niemiecką elektronikę ...}}

Do ogólnego pytania dotyczącego „metod unikania przepełnienia stosu w algorytmie rekurencyjnym” ...

Innym podejściem jest włączenie licznika rekurencji. Jest to bardziej przydatne do wykrywania nieskończonych pętli spowodowanych sytuacjami, na które nie ma się wpływu (i słabym kodowaniem).

Licznik rekurencji ma postać

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

Za każdym razem, gdy wykonujesz połączenie, zwiększasz licznik. Jeśli licznik staje się zbyt duży, popełniasz błąd (w tym przypadku jest to tylko zwrot -1, chociaż w innych językach możesz preferować wyjątek). Chodzi o to, aby zapobiec wystąpieniu gorszych rzeczy (błędów pamięci) podczas wykonywania rekurencji, która jest znacznie głębsza niż oczekiwano i prawdopodobnie nieskończonej pętli.

Teoretycznie nie powinieneś tego potrzebować. W praktyce widziałem źle napisany kod, który go dotknął z powodu mnóstwa drobnych błędów i złych praktyk kodowania (problemy z wielowątkową współbieżnością, w których coś zmienia coś poza metodą, która powoduje, że kolejny wątek przechodzi w nieskończoną pętlę wywołań rekurencyjnych).

Użyj właściwego algorytmu i rozwiąż właściwy problem. Wydaje się, że specjalnie dla Collatz Conjecture próbujesz rozwiązać to w sposób xkcd :

Zaczynasz od liczby i przechodzisz przez drzewo. To szybko prowadzi do bardzo dużej przestrzeni wyszukiwania. Szybki bieg w celu obliczenia liczby iteracji dla poprawnej odpowiedzi daje około 500 kroków. Nie powinno to stanowić problemu w przypadku rekurencji z ramką o małym stosie.

Chociaż znajomość rozwiązania rekurencyjnego nie jest złą rzeczą, należy również zdać sobie sprawę, że wielokrotnie rozwiązanie iteracyjne jest lepsze . Wiele sposobów podejścia do konwertowania algorytmu rekurencyjnego na iteracyjny można znaleźć na stronie Przepełnienie stosu w Way, aby przejść od rekurencji do iteracji .

Należy pamiętać, że implementacja języka musi obsługiwać optymalizację rekurencji ogona. Nie sądzę, że robią to główne kompilatory Java.

Zapamiętywanie oznacza, że ​​pamiętasz wynik obliczenia, a nie przeliczasz go za każdym razem, na przykład:

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]

Gdy obliczasz każdą sekwencję mniejszą niż milion, na końcu sekwencji będzie dużo powtórzeń. Zapamiętywanie sprawia, że ​​jest to szybkie wyszukiwanie tabeli skrótów dla poprzednich wartości zamiast konieczności zwiększania stosu.

Dziwi mnie, że nikt jeszcze nie wspomniał o trampolinie . Trampolina (w tym sensie) to pętla, która iteracyjnie wywołuje funkcje zwracania zagęszczeń (styl przekazywania kontynuacji) i może być używana do implementacji wywołań funkcji rekurencyjnych w języku programowania stosowego.

To pytanie StackOverflow zawiera nieco więcej szczegółów na temat różnych implementacji trampolinowania w Javie: Obsługa StackOverflow w Javie dla Trampoline

Jeśli używasz języka i kompilatora, który rozpoznaje funkcje rekurencyjne taila i odpowiednio je obsługuje (tj. „Zastępuje dzwoniącego na miejscu przez odbiorcę”), to tak, stos nie powinien wymknąć się spod kontroli. Ta optymalizacja zasadniczo redukuje metodę rekurencyjną do iteracyjnej. Nie sądzę, że Java to robi, ale wiem, że robi to Racket.

Jeśli wybierzesz podejście iteracyjne, a nie rekurencyjne, eliminujesz większość potrzeby pamiętania, skąd pochodzą połączenia, i praktycznie eliminujesz ryzyko przepełnienia stosu (w każdym razie połączeń rekurencyjnych).

Zapamiętywanie jest świetne i może zmniejszyć ogólną liczbę wywołań metod, sprawdzając wcześniej obliczone wyniki w pamięci podręcznej, biorąc pod uwagę, że ogólne obliczenia pociągną za sobą wiele mniejszych, powtarzanych obliczeń. Ten pomysł jest świetny - jest również niezależny od tego, czy używasz podejścia iteracyjnego, czy rekurencyjnego.

możesz utworzyć Wyliczenie, które zastąpi rekurencję ... oto przykład obliczania zdolności robienia tego ... (nie będzie działać dla dużych liczb, ponieważ użyłem tylko długo w przykładzie :-))

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

nawet jeśli nie jest to zapamiętywanie, w ten sposób unieważnisz przepełnienie stosu

EDYTOWAĆ

Przepraszam, jeśli zdenerwowałem niektórych z was. Moim jedynym zamiarem było pokazanie sposobu uniknięcia przepełnienia stosu. Prawdopodobnie powinienem był napisać pełny przykład kodu zamiast tylko małego fragmentu szybko napisanego i szorstkiego fragmentu kodu.

Poniższy kod

• unika rekurencji, gdy używam iteracyjnie obliczać wymagane wartości.
• obejmuje zapamiętywanie, ponieważ wartości już obliczone są przechowywane i pobierane, jeśli zostały już obliczone
• zawiera również stoper, dzięki czemu można zobaczyć, że zapamiętywanie działa poprawnie

... umm ... jeśli go uruchomisz, upewnij się, że ustawiłeś okno powłoki poleceń tak, aby miało bufor 9999 linii ... zwykłe 300 nie wystarczy, aby przejść przez wyniki poniższego programu ...

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

Deklaruję * 1 zmienną statyczną „instancja” w klasie Wydziału do sklepu jako singleton. W ten sposób, dopóki twój program działa, za każdym razem, gdy „GetInstance ()” klasy otrzymujesz instancję, która zachowała wszystkie wartości już obliczone. * 1 static SortedList, która będzie przechowywać wszystkie wartości już obliczone

W konstruktorze dodaję również 2 wartości specjalne z listy 1 dla wejść 0 i 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;

        }
    }
}

Jeśli chodzi o Scalę, możesz dodać @tailrecadnotację do metody rekurencyjnej. W ten sposób kompilator zapewnia faktyczną optymalizację wywołania ogona:

Więc to się nie skompiluje (silnia):

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

komunikat o błędzie to:

scala: nie można zoptymalizować metody adnotacji @tailrec fak1: zawiera wywołanie rekurencyjne nie w pozycji ogona

Z drugiej strony:

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

kompilacje i przeprowadzono optymalizację wywołania ogona.

Jedną z możliwości, o której jeszcze nie wspomniano, jest rekurencja, ale bez użycia stosu systemowego. Oczywiście możesz również przepełnić swoją stertę, ale jeśli twój algorytm naprawdę potrzebuje powrotu do poprzedniej wersji w takiej czy innej formie (po co w ogóle używać rekurencji?), Nie masz wyboru.

Istnieją implementacje niektórych języków bez stosów , np . Python bez stosów .

Innym rozwiązaniem byłoby symulowanie własnego stosu i nie poleganie na implementacji kompilatora + środowiska wykonawczego. To nie jest proste ani szybkie rozwiązanie, ale teoretycznie otrzymasz StackOverflow tylko wtedy, gdy brakuje Ci pamięci.