Подтвердить что ты не робот

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

Ответ 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);
}

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

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

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

Ответ 6

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

Ответ 8

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

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

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

Ответ 9

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

Ответ 10

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

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

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