Использование рекурсии в C #

Question

Существуют ли общие правила при использовании рекурсии о том, как избежать переполнения стека?

Answer 1

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

• Размер стека (который обычно составляет 1 МБ IIRC, но двоичный файл можно редактировать вручную; я бы не рекомендовал это делать)
• Сколько стека использует каждый уровень рекурсии (метод с 10 незаписанными Guid локальными переменными будет занимать больше стека, чем метод, который не имеет локальных переменных, например)
• Используемый вами JIT - иногда JIT будет использовать хвостовую рекурсию, в других случаях - нет. Правила сложные, и я не могу их запомнить. (Есть сообщение в блоге Дэвида Бромана от 2007 года и страница MSDN от того же автора / даты , но они могут быть устаревшими.)

Как избежать переполнения стека? Не повторяйте слишком далеко :) Если вы не можете быть достаточно уверены, что ваша рекурсия закончится, не пройдя слишком далеко (я бы побеспокоился о «более 10», хотя это очень безопасно), то перепишите его, чтобы избежать рекурсии. 1018 *

Answer 2

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

public int CalculateSomethingRecursively(int someNumber)
{
    return doSomethingRecursively(someNumber, 0);
}

private int doSomethingRecursively(int someNumber, int level)
{
    if (level >= MAX_LEVEL || !shouldKeepCalculating(someNumber))
        return someNumber;
    return doSomethingRecursively(someNumber, level + 1);
}

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

Answer 3

Я не знаю ни одного жесткого набора , чтобы избежать переполнения стека. Я лично стараюсь обеспечить -
1. У меня правильные базовые случаи.
2. Код достигает базового случая в какой-то момент.

Answer 4

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

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

Answer 5

Нормальный предел, если в стеке между последовательными вызовами осталось немного, составляет около 15000-25000 уровней. 25% от этого, если вы используете IIS 6+.

Большинство рекурсивных алгоритмов можно выразить итеративно.

Существуют различные способы увеличения выделенного стекового пространства, но я скорее позволю вам сначала найти итерационную версию. :)

Answer 6

Я написал небольшую статью об этом здесь . По сути, я передаю необязательный параметр с именем deep, добавляя к нему 1 каждый раз, когда углубляюсь в него. В рамках рекурсивного метода я проверяю значение глубины. Если оно превышает значение, которое я установил, я выбрасываю исключение. Значение (порог) будет зависеть от потребностей ваших приложений.

Answer 7

Размер стека по умолчанию для потока составляет 1 МБ, если вы работаете с CLR по умолчанию. Однако другие хосты могут изменить это. Например, хост ASP меняет значение по умолчанию на 256 КБ. Это означает, что у вас может быть код, который отлично работает под VS, но ломается при развертывании его в реальной среде хостинга.

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

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

Answer 8

Я только что подумал о хвостовой рекурсии, но оказалось, что C # его не поддерживает. Однако .Net-Framework, кажется, поддерживает это:

http://blogs.msdn.com/abhinaba/archive/2007/07/27/tail-recursion-on-net.aspx

Answer 9

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

Answer 10

Помните, если вам нужно спросить о системных ограничениях, то вы, вероятно, делаете что-то ужасно неправильное.

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

Нетрудно преобразовать рекурсивную функцию в итеративную, тем более что в C # имеется коллекция Generic :: Stack. Использование типа Stack перемещает используемую память в кучу программы, а не в стек. Это дает вам полный диапазон адресов для хранения рекурсивных данных. Если этого недостаточно, то не так уж сложно перенести данные на диск. Но я бы серьезно рассмотрел другие решения, если вы дойдете до этой стадии.