рекурсивный размер стека? - PullRequest
Новая
       23

рекурсивный размер стека?

2 голосов
/ 25 сентября 2011 
class Program  
{
    static void Main(string[] args)
    {
        Test(0);
    }

    static void Test(int i)
    {
        if (i > 30000)
        {
            return;
        }
        Test(i + 1);
    }
}

Зачем получать рекурсивную функцию и вызывать исключение StackOverflowException при вызове этого примера выше.

(потому что по сравнению с рекурсивным размером стека по умолчанию?)

но мне интересно, как решить эту проблему.

Спасибо.

Ответы [ 5 ]

5 голосов
/ 25 сентября 2011

Вы получаете исключение, потому что 30 000 кадров стека - это довольно большое число: -)

Вы решаете , используя рекурсию более осмотрительным образом.Идеальными задачами, которые необходимо решить рекурсивно, являются те, которые быстро сокращают «пространство поиска» (a) .

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

def find (searchkey, node):
    if node = NULL:
        return NULL
    if searchkey = node.key:
        return node
    if searchkey < node.key:
        return find (searchkey, node.left)
    return find (searchkey, node.right)

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

def add (a, b):
    if a = 0:
        return b
    return add (a-1, b+1)

(a) Пространство поиска можно определить как весь ваш набор возможных ответов.Вы хотите уменьшить его как можно быстрее.

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

  • та же или аналогичная проблема с «более простым» аргументом.
  • завершающее условие с «самым простым» аргументом.

(«простой» в этом смысле означает приближение к завершающему условию).

Теоретические / математические подходы не должны были бы учитывать пространство стека, но мы, как компьютерные специалисты, должны.Реальность устанавливает пределы: -)

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

5 голосов
/ 25 сентября 2011

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

Алгоритмы, которые будут работать с рекурсией, не используют один уровень рекурсии для каждого элемента.Обычно вы делите работу пополам для каждого уровня, поэтому для 30000 предметов потребуется только 15 уровней рекурсии.

2 голосов
/ 25 сентября 2011

Хотя вы могли бы указать размер стека для нового потока вручную, я бы использовал Stack<T> или цикл (это действительно все, что нужно для вашего упрощенного примера), поэтому вам не нужнорекурсия вообще, то есть: 

Stack<int> stack = new Stack<int>();
stack.Push(1);
while(stack.Count > 0)
{
    int someValue = stack.Pop();
    //some calculation based on someValue
    if(someValue < 30000)
        stack.Push(someValue +1);
}
2 голосов
/ 25 сентября 2011

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

for( int i = 0; i <= 30000; ++i )
{
    Test( i );
}

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

1 голос
/ 25 сентября 2011

Взгляните на этот вопрос: Путь от рекурсии к итерации

Если ваша рекурсия будет иметь глубину 30k + уровней ... вы, вероятно, хотите превратить ее витерационный алгоритм.Ответы на этот вопрос должны помочь.

...