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

class Program  
{
    static void Main(string[] args)
    {
        Test(0);
    }

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

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

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

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

Благодарю.

Источник

5 ответов

Решение

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

Вы решаете это, используя рекурсию более осмотрительным образом. Идеальные проблемы, которые нужно решать рекурсивно, это те, которые быстро сокращают "пространство поиска" (а).

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

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)

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

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

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

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

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

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

Источник

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

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

Источник

Хотя вы можете указать размер стека для нового потока вручную, я бы использовал 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);
}
Источник

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

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

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

Источник

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

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

Источник
Другие вопросы по тегам