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

StackOverflow https://stackoverflow.com/questions/610743

  •  03-07-2019
  •  | 
  •  

Вопрос

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

Это было полезно?

Решение

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

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

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

Другие советы

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

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

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

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

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

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

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

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

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

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

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

http: // blogs .msdn.com / Абхинаб / Архив / 2007/07/27 / хвост рекурсия-на-net.aspx

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top