Какие существуют методы, чтобы избежать переполнения стека в рекурсивном алгоритме?

Вопрос

Каковы возможные способы решения переполнения стека, вызванного рекурсивным алгоритмом?

пример

Я пытаюсь решить проблему Project Euler 14 и решил попробовать ее с помощью рекурсивного алгоритма. Тем не менее, программа останавливается с java.lang.StackOverflowError. Вполне понятно. Алгоритм действительно переполнял стек, потому что я пытался сгенерировать последовательность Коллатца для очень большого числа.

Решения

Поэтому мне было интересно: какие существуют стандартные способы решения проблемы переполнения стека, если ваш рекурсивный алгоритм был написан правильно и всегда заканчивался переполнением стека? В голову пришли две концепции:

1. хвостовая рекурсия
2. итерация

Являются ли идеи (1) и (2) правильными? Есть ли другие варианты?

редактировать

Было бы полезно увидеть некоторый код, желательно на Java, C #, Groovy или Scala.

Возможно, не используйте проблему Project Euler, упомянутую выше, чтобы она не испортилась для других, а используйте другой алгоритм. Факториал, может быть, или что-то подобное.

Оптимизация Tail Call присутствует во многих языках и компиляторах. В этой ситуации компилятор распознает функцию вида:

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

Здесь язык способен распознавать, что возвращаемый результат является результатом другой функции, и изменять вызов функции с новым кадром стека в переход.

Поймите, что классический метод факториала:

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

не является хвостовым вызовом, оптимизируемым из-за проверки, необходимой при возврате. ( Пример исходного кода и скомпилированного вывода )

Чтобы сделать этот хвостовой вызов оптимизируемым,

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

Компиляция этого кода с помощью gcc -O2 -S fact.c(-O2 необходима для включения оптимизации в компиляторе, но с большим количеством оптимизаций -O3 человеку становится трудно читать ...)

_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

( Пример исходного кода и скомпилированного вывода )

Можно увидеть в сегменте .L3, jneа не call(который выполняет вызов подпрограммы с новым кадром стека).

Пожалуйста, обратите внимание, что это было сделано с C. Оптимизация вызовов Tail в Java сложна и зависит от реализации JVM (при этом я не видел ни одного, кто это делает, потому что это сложно и подразумевает необходимость требуемой модели безопасности Java, требующей стековых фреймов - это то, чего избегает TCO) - хвостовая рекурсия + java и хвостовая рекурсия + оптимизация - это хорошие наборы тегов для просмотра. Вы можете найти другие языки JVM способны оптимизировать хвостовую рекурсию лучше (попытка Clojure (который требует повторялся для оптимизации хвостового вызова), или Скале).

Это сказало,

Существует определенная радость от осознания того, что вы написали что-то правильно - идеальным способом, которым это можно сделать.
_{^{А теперь я собираюсь взять скотч и надеть немецкую электронику ...}}

К общему вопросу о "методах, позволяющих избежать переполнения стека в рекурсивном алгоритме" ...

Другой подход - включить счетчик рекурсии. Это больше для обнаружения бесконечных циклов, вызванных не зависящими от вас ситуациями (и плохим кодированием).

Счетчик рекурсии принимает форму

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

Каждый раз, когда вы делаете звонок, вы увеличиваете счетчик. Если счетчик становится слишком большим, вы выдаете ошибку (здесь просто возвращается -1, хотя в других языках вы можете предпочесть исключение). Идея состоит в том, чтобы предотвратить худшие вещи (из-за ошибок памяти) при выполнении рекурсии, которая намного глубже, чем ожидалось, и, вероятно, представляет собой бесконечный цикл.

Теоретически вам это не нужно. На практике я видел плохо написанный код, который поразил это из-за множества мелких ошибок и плохих практик кодирования (многопоточные проблемы параллелизма, когда что-то изменяет что-то вне метода, что заставляет другой поток входить в бесконечный цикл рекурсивных вызовов).

Используйте правильный алгоритм и решите правильную проблему. Похоже, что специально для гипотезы Коллатца вы пытаетесь решить ее способом xkcd :

Вы начинаете с числа и делаете обход дерева. Это быстро приводит к очень большому пространству поиска. Быстрый прогон для вычисления количества итераций для правильного ответа дает около 500 шагов. Это не должно быть проблемой для рекурсии с небольшим кадром стека.

Хотя знание рекурсивного решения не является плохой вещью, следует также понимать, что многократно итеративное решение лучше . Несколько способов приблизить преобразование рекурсивного алгоритма к итерационному можно увидеть на Stack Overflow в Way, чтобы перейти от рекурсии к итерации .

Имейте в виду, что языковая реализация должна поддерживать оптимизацию хвостовой рекурсии. Я не думаю, что основные компиляторы Java делают.

Заметка означает, что вы запоминаете результат вычисления, а не пересчитываете его каждый раз, например:

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]

Когда вы вычисляете каждую последовательность менее миллиона, в конце последовательности будет много повторений. Мемоизация делает быстрый поиск в хэш-таблице предыдущих значений вместо того, чтобы делать стек глубже и глубже.

Я удивлен, что никто еще не упомянул прыжки на батуте . Батут (в этом смысле) - это цикл, который итеративно вызывает функции, возвращающие поток (стиль передачи продолжения), и может использоваться для реализации вызовов с хвостовой рекурсивностью в языке программирования, ориентированного на стек.

В этом вопросе StackOverflow более подробно рассматриваются различные реализации трамплининга в Java: обработка StackOverflow в Java для Trampoline

Если вы используете язык и компилятор, который распознает хвостовые рекурсивные функции и обрабатывает их должным образом (т. Е. «Заменяет вызывающего на месте вызываемого»), то да, стек не должен выходить из-под контроля. Эта оптимизация существенно сводит рекурсивный метод к итеративному. Я не думаю, что Java делает это, но я знаю, что Racket делает.

Если вы используете итеративный подход, а не рекурсивный, вы устраняете большую часть необходимости помнить, откуда поступают вызовы, и практически исключаете вероятность переполнения стека (в любом случае, из рекурсивных вызовов).

Мемоизация хороша и может сократить общее количество вызовов методов, просматривая ранее вычисленные результаты в кэше, учитывая, что ваши общие вычисления повлекут за собой много меньших повторных вычислений. Эта идея великолепна - она ​​также не зависит от того, используете ли вы итеративный или рекурсивный подход.

Вы могли бы создать Перечисление, которое заменит рекурсию ... вот пример для вычисления способности, делающей это ... (не будет работать для больших чисел, поскольку я использовал только long в примере :-))

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

даже если это не запоминание, таким образом вы избавитесь от переполнения стека

РЕДАКТИРОВАТЬ

Мне жаль, если я расстроил некоторых из вас. Моим единственным намерением было показать, как избежать переполнения стека. Я, вероятно, должен был написать полный пример кода вместо просто небольшого фрагмента быстро написанного и грубого фрагмента кода.

Следующий код

• избегает рекурсии, поскольку я использую вычислять требуемые значения итеративно.
• включает в себя памятку, так как уже рассчитанные значения сохраняются и извлекаются, если они уже рассчитаны
• также включает в себя секундомер, чтобы вы могли видеть, что памятка работает правильно

... ммм ... если вы запустите его, убедитесь, что вы установили в окне командной оболочки буфер из 9999 строк ... обычных 300 не хватит для запуска результатов приведенной ниже программы ...

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

Я объявляю * 1 статическую переменную "instance" в классе Faculty для хранения синглтона. Таким образом, пока ваша программа работает, всякий раз, когда вы «GetInstance ()» класса, вы получаете экземпляр, в котором хранятся все значения, уже рассчитанные. * 1 статический SortedList, который будет содержать все рассчитанные значения

В конструктор я также добавляю 2 специальных значения из списка 1 для входов 0 и 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;

        }
    }
}

Что касается Scala, вы можете добавить @tailrecаннотацию к рекурсивному методу. Таким образом, компилятор гарантирует, что оптимизация хвостовых вызовов действительно произошла:

Так что это не скомпилируется (факториал):

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

сообщение об ошибке:

scala: не удалось оптимизировать аннотированный метод @tailrec fak1: он содержит рекурсивный вызов не в хвостовой позиции

С другой стороны:

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

компилируется, и выполняется оптимизация хвостовых вызовов.

Одна из возможностей, которая еще не упоминалась, - это иметь рекурсию, но без использования системного стека. Конечно, вы также можете переполнить свою кучу, но если ваш алгоритм действительно нуждается в возврате в той или иной форме (зачем вообще использовать рекурсию?), У вас нет выбора.

Существуют реализации без стеков некоторых языков, например, Stackless Python .

Другим решением было бы моделировать ваш собственный стек, а не полагаться на реализацию компилятора + время выполнения. Это не простое и не быстрое решение, но теоретически вы получите StackOverflow только тогда, когда у вас недостаточно памяти.