Исключение во время выполнения, слишком глубокая рекурсия

Question

Я преобразовал псевдокод здесь в C # и рекурсивно повторил его 10000 раз.Но я получаю ошибку во время выполнения C #, StackOverflow Exception после 9217 раз.Как я могу предотвратить это?

РЕДАКТИРОВАТЬ Если это кому-нибудь поможет, вот код:

    private double CalculatePi(int maxRecursion)
    {
        return 2 * CalculatePi(maxRecursion, 1);
    }

    private double CalculatePi(int maxRecursion, int i)
    {
        if (i >= maxRecursion)
            return 1;
        return 1 + i / (2.0 * i + 1) * CalculatePi(maxRecursion, i + 1);
    }

    double pi = CalculatePi(10000); // 10,000 recursions

РЕДАКТИРОВАТЬ2 Так что, кажется, все согласны с тем, чтомне нужно преобразовать это в итеративный ... кто-нибудь может дать код?Я не могу написать какой-либо итеративный код, который работает ...

EDIT Спасибо Полу Рику за этот ответ, который я протестировал, и он работает:

    private static double CalculatePi(int maxRecursion)
    {
        double result = 1;
        for (int i = maxRecursion; i >= 1; i-- )
        {
            result = 1 + i / (2.0 * i + 1) * result;
        }
        return result * 2;
    }

Answer 1

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

Вы просите рыбу или учите, как ее ловить?Если цель этого упражнения состоит в том, чтобы научиться преобразовывать рекурсивный код в итеративный код, то вам не достаточно просто получить ответ.

Чтобы преобразовать рекурсивный код в итеративный код, существует множество возможных способовсделай это.Самый простой способ в этом случае - просто разработать шаблон.Что делает код?Он вычисляет:

(1 + 1 / (2.0 * 1 + 1)) * 
(1 + 2 / (2.0 * 2 + 1)) * 
(1 + 3 / (2.0 * 3 + 1)) * 
(1 + 4 / (2.0 * 4 + 1)) * 
(1 + 5 / (2.0 * 5 + 1)) * 
(1 + 6 / (2.0 * 6 + 1)) * 
(1 + 7 / (2.0 * 7 + 1)) * 
...
(1 + 9999/ (2.0 * 9999+ 1)) *
1

Теперь вы можете написать цикл, который вычисляет это?Конечно.

double product = 1.0;
for (int i = 9999; i >= 0; --i)
    product *= (1 + i / (2.0 * i + 1));

Это самый простой способ сделать это.Но есть много способов решить эту проблему.

Вы можете использовать агрегатор .Рассмотрим «общую» операцию;это пример агрегатора.У вас есть последовательность вещей, и вы сохраняете их промежуточный итог, накапливая результат в накопителе.Для стандартных операторов запросов предусмотрена операция агрегирования:

double seed = 1.0;
Enumerable.Range(0, 10000).Aggregate(seed, 
    (product, i) => product * (1 + i / (2.0 * i + 1))

Или вы можете сохранить свой алгоритм рекурсивным, но устранить переполнение стека путем:

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

Объяснение этих методов занимает слишком много времени для одного ответа.У меня есть серия из шести статей о том, как использовать эти методы для превращения рекурсивных программ в программы, которые не потребляют много стека;начните читать здесь:

http://blogs.msdn.com/b/ericlippert/archive/2005/07/25/recursion-part-zero.aspx

Answer 2

Компилятор "c #" скомпилирует это нормально. Однако во время выполнения вы можете получить исключение StackOverflow (на моем компьютере 10000 работает нормально, но умирает позже).

Это не «исключение бесконечной рекурсии» - переполнение стека - именно то, что оно говорит; Вызов метода означает помещение информации в стек и удаление ее при возврате вызова. У вас есть 10 000 вызовов, и ни один не вернулся, поэтому стек заполнен, и выдается исключение.

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

Вот быстрый прямой перевод в итеративный стиль:

private static double CalculatePi(int maxRecursion)
        {
            double result = 1;
            for (int i = maxRecursion -1; i >= 1; i-- )
            {
                result = 1 + i / (2.0 * i + 1) * result;
            }
            return result * 2;
        }

Answer 3

Не используйте рекурсию. Это хороший пример случая, когда вы не должны выполнять рекурсию, так как это вызовет переполнение стека вызовов.

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

Answer 4

Чтобы заглянуть в то, что все остальные говорят здесь - это переполнение стека (вот! Вопрос о переполнении стека в StackOverflow. Это может вызвать стек ...)

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

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

Answer 5

Вы не можете предотвратить это, функция вызывает себя слишком много раз;есть предел того, насколько глубоким может быть стек вызовов, и ваша функция достигает его.

Answer 6

Рекурсивный вызов не является хвостово-рекурсивным, и даже если бы это было так, это не помогло бы, поскольку компилятор C # в настоящее время не оптимизирует хвост-рекурсивные вызовы.РЕДАКТИРОВАТЬ: Как указали Эрик Липперт и Гейб, CLR может выбрать генерацию хвостовых вызовов, даже если явных инструкций хвостового вызова нет в выданном IL.Можно было бы превратить это рекурсивное решение в итеративное.

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

Пожалуйстане делай этого. Только для удовольствия:

static void Main()
{
    Console.WriteLine(SafeCalculatePi(10000));
}

// Calculates PI on a separate thread with enough stack-space 
// to complete the computation
public static double SafeCalculatePi(int maxRecursion)
{
    // We 'know' that you can reach a depth of 9217 for a 1MB stack.
    // This lets us calculate the required stack-size, with a safety factor
    double requiredStackSize = (maxRecursion / 9217D) * 1.5 * 1024 * 1024 ; 

    double pi = 0;
    ThreadStart ts = delegate { pi = CalculatePi(maxRecursion); };
    Thread t = new Thread(ts, (int)requiredStackSize);
    t.Start();
    t.Join();
    return pi;
}

Answer 7

Итерационная версия:

public static double CalculatePi(int maxRecursion)
{
    double result=1;
    for(int i=maxRecursion-1;i>=1;i--)
    {
        result=1+i/(2.0*i+1)*result;  
    }
    return result*2;
}

Answer 8

Это будет нерекурсивный вариант:

        private double CalculatePi(int maxRecursion)
    {
        return 2 * CalculatePi2(maxRecursion, 1);
    }

    private double CalculatePi2(int maxRecursion, int i)
    {
        double product = 1;
        while (i < maxRecursion)
        {
            product = product * (1f + i / (2.0f * i + 1f));
            i++;
        }
        return product;
    }

Answer 9

Итерационный код для этого просто:

private double CalculatePi(int iterations) {
  double pi = 1.0;
  for (int i = iterations - 1; i >= 1; i--) {
    pi = 1 + i / (2.0 * i + 1) * pi;
  }
  return pi * 2.0;
}

Использование:

double pi = CalculatePi(51);

Answer 10

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