Рекурсивный метод вызывает StackOverflowException

Question

Я - новый ученик C# из Гонконга.

Кто-то задает мне вопрос, обычно известный как проблема сбрасывания яиц, с ссылкой ниже на YouTube: -

https://youtu.be/o_AJ3VWQMzA

В попытке решить такую ​​проблему я написал приведенный ниже скрипт C# и запустил его в коде Visual Studio, но столкнулся с ошибкой «Переполнение стека». Где T - это количество этажей гипотетического здания, N - это количество Яиц в руке, а M - это количество раз испытаний.

Я потратил много времени, пытаясь отладить, но тщетно. Спасибо за любую помощь, пожалуйста.

Код:

using System;

namespace Double_Egg
{
    class Program
    {
        static int k=1, v1=0, v2=0, v3=0, minv=0, mink;

        static int DE(int T, int N)
        {
            if(T==1)
                return(1);
            else if(N==1)
                return(T);
            else
            {   
                minv=Math.Max(DE(1,N-1),DE(T-1,N));
                mink=1;

                for(k=2; k<=T; k++)
                {  
                    v1= DE(k,N-1);
                    v2=DE(T-k,N);
                    v3=Math.Max(v1,v2);

                    if(v3<minv)
                    {
                        minv=v3;
                        mink=k;
                    }
                }

                return(Math.Max(DE(mink, N-1),DE(T-mink,N))+1);
            }
        }

        static void Main(string[] args)
        {
            int T=1, N=1, M=1;

            Console.Write("Please enter number of Floors(T):");
            T=int.Parse(Console.ReadLine());
            Console.Write("Please enter numer of eggs(N):");
            N=int.Parse(Console.ReadLine());
            M=DE(T,N);
            Console.WriteLine("The minimum number of throwing test(M) is: " + M);
        }
    }
}

Answer 1

Шаг 1: Домашнее хозяйство

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

using System;

namespace Double_Egg
{
    class Program
    {
        static int floor             = 1;
        static int changeFloorResult = 0;
        static int changeEggResult   = 0;
        static int bestChangeResult  = 0;
        static int bestResult        = 0;
        static int minFloor;

        static int RunDropEggAlgorithm( int numberOfFloors, int numberOfEggs )
        {
            if( numberOfFloors == 1)
            {
                return 1;
            }
            else
            {
                if( numberOfEggs == 1 )
                {
                    return numberOfFloors;
                }
                else
                {   
                    bestResult = Math.Max( RunDropEggAlgorithm( 1, numberOfEggs - 1 ), RunDropEggAlgorithm( numberOfFloors - 1, numberOfEggs ) );
                    minFloor = 1;
                    for( floor = 2; floor <= numberOfFloors; floor++ )
                    {  
                        changeFloorResult = RunDropEggAlgorithm( floor, numberOfEggs - 1 );
                        changeEggResult   = RunDropEggAlgorithm( numberOfFloors - floor, numberOfEggs );
                        bestChangeResult = Math.Max( changeFloorResult, changeEggResult );
                        if( bestChangeResult < bestResult )
                        {
                            bestResult = bestChangeResult;
                            minFloor = floor;
                        }
                    }

                    return Math.Max(
                        RunDropEggAlgorithm( minFloor, numberOfEggs - 1 ),
                        RunDropEggAlgorithm( numberOfFloors - minFloor, numberOfEggs )
                    ) + 1;
                }
            }
        }

        static void Main( string[] args )
        {
            int numberOfFloors = 1;
            int numberOfEggs   = 1;
            int result         = 1;

            Console.Write("Please enter number of Floors:");
            numberOfFloors = int.Parse( Console.ReadLine() );

            Console.Write("Please enter numer of eggs:");
            numberOfEggs   = int.Parse( Console.ReadLine() );

            result = RunDropEggAlgorithm( numberOfFloors, numberOfEggs );
            Console.WriteLine("The minimum number of throwing test is:" + result);
        }
    }
}

Шаг 2: Отладка

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

При работе с рекурсивными алгоритмами переполнение стека происходит, когда не проверяется какой-либо базовый случай или граничное условие (например, не учитываются оба n == 0 и n == 1 при реализации генератора серии Фибоначчи.

Когда я вставляю код в DotNetFiddle , запускаю его и поставляю floors: 2, eggs: 2 Я получаю исключение тайм-аута (это потому, что DotNetFiddle завершает работу программы до того, как StackOverflowException может произойти) - но этого все же достаточно, чтобы выявить проблему с помощью визуального осмотра (у меня в любом случае на моем текущем компьютере нет пошагового отладчика C#).

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

[...]
static int RunDropEggAlgorithm( int numberOfFloors, int numberOfEggs )
{
    Console.WriteLine( nameof(RunDropEggAlgorithm) + " numberOfFloors: {0}, numberOfEggs: {1}. Press [Enter] to continue...", numberOfFloors, numberOfEggs );
    Console.ReadLine();

    if( numberOfFloors == 1)
[...]

Таким образом, мы получаем этот вывод, когда запускаем его с тем же входом:

Please enter number of Floors:2
Please enter numer of eggs:2
RunDropEggAlgorithm numberOfFloors: 2, numberOfEggs: 2 
RunDropEggAlgorithm numberOfFloors: 1, numberOfEggs: 1 
RunDropEggAlgorithm numberOfFloors: 1, numberOfEggs: 2 
RunDropEggAlgorithm numberOfFloors: 2, numberOfEggs: 1 
RunDropEggAlgorithm numberOfFloors: 0, numberOfEggs: 2 
RunDropEggAlgorithm numberOfFloors: 1, numberOfEggs: 1 
RunDropEggAlgorithm numberOfFloors: -1, numberOfEggs: 2 
RunDropEggAlgorithm numberOfFloors: 1, numberOfEggs: 1
> 

Даже без просмотра видео, на которое вы ссылались, я подозреваю, что numberOfFloors НЕ должно быть -1 , так что если изменить первые два if оператора RunDropEggAlgorithm с == 1 на <= 1 примерно так ...:

[...]
static int RunDropEggAlgorithm( int numberOfFloors, int numberOfEggs )
{
    Console.WriteLine( nameof(RunDropEggAlgorithm) + " numberOfFloors: {0}, numberOfEggs: {1} Press [Enter] to continue...", numberOfFloors, numberOfEggs );
    Console.ReadLine();

    if( numberOfFloors <= 1)
    {
        return 1;
    }
    else
    {
        if( numberOfEggs <= 1 )
        {
            return numberOfFloors;
        }
[...]

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

Please enter number of Floors:2
Please enter numer of eggs:2
RunDropEggAlgorithm numberOfFloors: 2, numberOfEggs: 2 
RunDropEggAlgorithm numberOfFloors: 1, numberOfEggs: 1 
RunDropEggAlgorithm numberOfFloors: 1, numberOfEggs: 2 
RunDropEggAlgorithm numberOfFloors: 2, numberOfEggs: 1 
RunDropEggAlgorithm numberOfFloors: 0, numberOfEggs: 2 
RunDropEggAlgorithm numberOfFloors: 1, numberOfEggs: 1 
RunDropEggAlgorithm numberOfFloors: 1, numberOfEggs: 2 

The minimum number of throwing test is:2