Как избежать переполнения стека? - PullRequest
Новая
       9

Как избежать переполнения стека?

5 голосов
/ 21 сентября 2009

Я компилирую свой код, используя CSharpCodeProvider, и динамически создаю экземпляр некоторого класса в результате сборки. Чем я называю какой-то метод. Если метод имеет рекурсию, я получаю StackOverflowException, и мое приложение завершается.

Как мне избежать этого? 

using System;
using System.Runtime.Remoting;
namespace TestStackOverflow
{
    class Program
    {
        class StackOver : MarshalByRefObject
        {
            public void Run()
            {
                Run();
            }
        }

        static void Main(string[] args)
        {
        AppDomain domain = AppDomain.CreateDomain("new");

        ObjectHandle handle = domain.CreateInstance(typeof (StackOver).Assembly.FullName, typeof (StackOver).FullName);
        if (handle != null)
        {
            StackOver stack = (StackOver) handle.Unwrap();
            stack.Run();
        }

    }
}
}

Связанный:

Что такое переполнение стека?

Ответы [ 7 ]

10 голосов
/ 21 сентября 2009

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

public class StackOver
{
    public void Run() 
    { 
        Run(); 
    }
}

Это приведет к переполнению стека, так как StackOver :: Run () будет вызываться снова и снова, пока не останется памяти.

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

Если вы пытаетесь сохранить работоспособность приложения, попробуйте: 

namespace TestStackOverflow
{
    class Program
    {
        class StackOver : MarshalByRefObject
        {
            public bool Run()
            {
                return true; // Keep the application running. (Return false to quit)
            }
        }

        static void Main(string[] args)
        {
            // Other code...

            while (stack.Run());
        }

    }
}
8 голосов
/ 21 сентября 2009

Run - это вызов Run. Это бесконечная рекурсия. 

    class StackOver : MarshalByRefObject
    {
        public void Run()
        {
            Run(); // Recursive call with no termination
        }
    }
1 голос
/ 21 сентября 2009

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

1 голос
/ 21 сентября 2009

Если рекурсия вызывает переполнение стека, то проблема не связана с компиляцией класса - рекурсивной функции требуется условие завершения, потому что C # (обычно) не оптимизирует хвостовые вызовы .

0 голосов
/ 21 сентября 2009

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

Следующая рекурсивная функция 

int Factorial(int n) {
    if (n == 0) { return 1; }
    return n * Factorial(n - 1);
}

после нескольких рекурсий вызова Factorial (5) стек вызовов будет выглядеть следующим образом: 

Factorial(5) -> Factorial(4) -> Factorial(3) -> Factorial(2) -> Factorial(1)

В этот момент n равно 1, и поэтому функция прекращает вызывать рекурсивный регистр и вместо этого возвращает 1. Затем программа начинает свернуть стек вызовов, и все возвращается 120.

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

Теперь предположим, что базового варианта там не было, и он выглядел так: 

int Factorial(int n) {
    return n * Factorial(n - 1);
}

После нескольких рекурсий вызова Factorial (5) стек вызовов будет выглядеть следующим образом: 

Factorial(5) -> Factorial(4) -> Factorial(3) -> Factorial(2) -> Factorial(1) -> Factorial(0) -> Factorial(-1) -> Factorial(-2) -> Factorial(-3) -> Factorial(-4) -> Factorial(-5) -> Factorial(-6) -> Factorial(-7) -> Factorial(-8) -> Factorial(-9) -> Factorial(-10) -> Factorial(-11) -> Factorial(-12) -> Factorial(-13) -> Factorial(-14) -> Factorial(-15) etc…

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

Есть 2 способа предотвратить это, лучший из них зависит от ситуации.

1 Укажите базовый вариант. Убедитесь, что есть какое-то условие, которое в конечном итоге достигается, что останавливает функцию от вызова самой себя. В факториальном случае это n == 1, но может случиться так, что определенное количество времени прошло, что оно повторялось определенное количество раз, что некоторый результат некоторых вычислений находится в определенных границах, что угодно. До тех пор, пока он перестает повторять, пока стек не станет слишком большим.

2 Удалить рекурсию и переписать ее без. Любой рекурсивный алгоритм может быть переписан как нерекурсивный алгоритм. Это может быть не так чисто и элегантно, но это можно сделать. В аргументе факториала это может быть что-то вроде: 

int Factorial(int n) {
    int result = 1;

    for (int i = 0; i < n; i += 1) {
        result *= n;
    }

    return result;
}

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

void Foo() {
    // Some code
    Foo();
}

в 

void Foo() {
    while (true) { // Some code }
}
0 голосов
/ 21 сентября 2009

Хорошо. Неважно, использовать CSharpCodeProvider или нет. Я загружаю сборку, используя Reflection в другом домене. Я думаю, что домены были созданы по соображениям безопасности. Как я могу защитить приложение от завершения ??? 

using System;
using System.Runtime.Remoting;
namespace TestStackOverflow
{
    class Program
    {
        class StackOver : MarshalByRefObject
        {
            public void Run()
            {
                Run();
            }
        }

        static void Main(string[] args)
        {
        AppDomain domain = AppDomain.CreateDomain("new");

        ObjectHandle handle = domain.CreateInstance(typeof (StackOver).Assembly.FullName, typeof (StackOver).FullName);
        if (handle != null)
        {
            StackOver stack = (StackOver) handle.Unwrap();
            stack.Run();
        }

    }
}
}
0 голосов
/ 21 сентября 2009

У меня нет хорошего фона CSharpCodeProvider, но я знаю, что рекурсивно реализованный алгоритм может быть реализован с помощью цикла

...