Правильный способ выхода из рекурсивного цикла

Question

Я пытаюсь написать программу, чтобы идентифицировать вхождения 3 последовательных целых чисел в заданном массиве из N чисел и заменить их средним значением, удалив два других.Например, Вход-> 55 99 99 100 101 101 34 35 36 5 28 7 50 50 51 52 52 24 13 14 15 5 6 7 37 31 37 38 39 36 40 Выход-> 55 100 35 5 28 7 51 24 14 6 3731 38 36 40

Для этого я написал этот метод, который принимает массив в качестве входных данных и возвращает измененный массив.

//input 
int[] original = new int[] { 1, 3, 4, 5, 5, 6, 8} ;

            List<int> lstoriginal = new List<int>(original);
            List<int> modified = Test(lstoriginal);

//method
    public static List<int> Test(List<int> arrayInput)
        {

            for (i = 0; i < arrayInput.Count; i++)
            {
                if (i + 2 < arrayInput.Count)
                {
                    if (arrayInput[i + 2] == arrayInput[i + 1] + 1
                    && arrayInput[i + 2] == arrayInput[i] + 2)
                    {
                        arrayInput.RemoveAt(i + 2);
                        arrayInput.RemoveAt(i);
                        List<int> temp = arrayInput;
                        Test(temp);
                    }
                }
            }

            return arrayInput;


        }

Следующие шаги / результаты выполнения, которые я проанализировал, -

1 - Первоначально, если тестовый вход 1, 3, 4, 5, 5, 6, 8

2-Когда i = 1 и он находит, что 3,4,5 находится в последовательности, он удаляет 3 и 5, и список становится 1,4,5,6,8

3-В следующий раз, когда я= 1, тогда он находит 4,5,6 и удаляет 4 и 6, а новый список 1,5,8

4-я ожидаю выхода из цикла, когда i + 2

Answer 1

На самом деле вам вообще не нужна рекурсия. Вы можете выполнить задачу значительно быстрее, просто переместив i после удаления последовательности. Вот функция, которая намного проще и делает то же самое. Я проверил это на десятках тысяч случайно сгенерированных неупорядоченных последовательностей.

public static List<int> Test2(List<int> arrayInput)
{

    for (int i = 0; i < arrayInput.Count - 2; i++)
    {
        if (arrayInput[i + 2] == arrayInput[i + 1] + 1
        && arrayInput[i + 2] == arrayInput[i] + 2)
        {
            arrayInput.RemoveAt(i + 2);
            arrayInput.RemoveAt(i);
            i = Math.Max(-1, i - 3); // -1 'cause i++ in loop will increment it
        }
    }

    return arrayInput;
}

Тем не менее, чтобы ответить на ваш конкретный вопрос, лучший способ выйти из рекурсивного цикла, такого как ваш оригинал, - это изменить сигнатуру вашей рекурсивной функции, чтобы вернуть bool, указывающий, действительно ли она внесла какие-либо изменения. Когда первый возвращается без изменений, все они могут существовать, поэтому ваш вызов Test может быть заключен в if (!Test(...)) { return; }.

Вот полные тестовые данные и тестовые данные, сравнивающие ваш оригинал с моей модифицированной версией:

public static void Main()
{
    const int COUNT = 10000;
    var r = new Random();
    int matchCount = 0;

    var stopwatch1 = new Stopwatch();
    var stopwatch2 = new Stopwatch();

    for (int j = 0; j < COUNT; j++)
    {
        var list = new List<int>(100) {1};

        for(int k=1; k<100; k++)
        {
            switch(r.Next(5))
            {
                case 0:
                case 1:
                case 2:
                    list.Add(list[k - 1] + 1);
                    break;

                case 3:
                    list.Add(list[k - 1] + r.Next(2));
                    break;

                case 4:
                    list.Add(list[k - 1] - r.Next(5));
                    break;
            }
        }

        stopwatch1.Start();
        List<int> copy1 = Test1(new List<int>(list));
        stopwatch1.Stop();

        stopwatch2.Start();
        List<int> copy2 = Test2(new List<int>(list));
        stopwatch2.Stop();


        string list1 = String.Join(",", copy1);
        string list2 = String.Join(",", copy2);

        if (list1 == list2)
        {
            if (copy1.Count == list.Count)
            {
                Console.WriteLine("No change:" + list1);
            }
            else
            {
                matchCount++;
            }
        }
        else
        {
            Console.WriteLine("MISMATCH:");
            Console.WriteLine("   Orig  : " + String.Join(",", list));
            Console.WriteLine("   Test1 : " + list1);
            Console.WriteLine("   Test2 : " + list2);
        }

    }
    Console.WriteLine("Matches: " + matchCount);
    Console.WriteLine("Elapsed 1: {0:#,##0} ms", stopwatch1.ElapsedMilliseconds);
    Console.WriteLine("Elapsed 2: {0:#,##0} ms", stopwatch2.ElapsedMilliseconds);
}



public static List<int> Test1(List<int> arrayInput)
{

    for (int i = 0; i < arrayInput.Count; i++)
    {
        if (i + 2 < arrayInput.Count)
        {
            if (arrayInput[i + 2] == arrayInput[i + 1] + 1
            && arrayInput[i + 2] == arrayInput[i] + 2)
            {
                arrayInput.RemoveAt(i + 2);
                arrayInput.RemoveAt(i);
                List<int> temp = arrayInput;
                Test1(temp);
            }
        }
        else
        {      // modified part: return the array
            return arrayInput;
        }
    }

    return arrayInput;
}

//method
public static List<int> Test2(List<int> arrayInput)
{

    for (int i = 0; i < arrayInput.Count - 2; i++)
    {
        if (arrayInput[i + 2] == arrayInput[i + 1] + 1
        && arrayInput[i + 2] == arrayInput[i] + 2)
        {
            arrayInput.RemoveAt(i + 2);
            arrayInput.RemoveAt(i);
            i = Math.Max(-1, i - 3); // -1 'cause i++ in loop will increment it
        }
    }

    return arrayInput;
}

Answer 2

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

Как это выглядит для меня:

Эта функция будет: Пройдите ввод, int от int. Проверяет, являются ли эти int и следующие 2 последовательными. Затем он удаляет этот и один за другим, а затем возвращает результат обратно в ту же функцию. Затем он игнорирует любое значение, которое это могло нам дать, и продолжает свой веселый путь.

У вас есть ввод 8,9,10 Он начинает шагать через: я = 0 и все такое. таким образом, он находит, что 8,9,10 являются последовательными, затем удаляет 8 и 9 и передает данные, которые приводят к этой же функции.

Итак, мы начнем снова:

У вас есть ввод 9 Он начинает шагать через: я снова = 0. он просматривает и обнаруживает, что в списке нет как минимум 3 значений, и возвращает оригинал.

Затем мы полностью игнорируем этот результат и продолжаем первоначальный цикл, описанный выше. Теперь я = 1, но в arrayInput есть только одна вещь, поэтому она должна заканчиваться.

Из того, что вы делаете, я не вижу причин делать рекурсивный вызов. Вы ничего не делаете с результатом, и даже если бы вы были, это помогло бы вам, если бы у вас была такая коллекция, как 8,9,10,10,11. Затем первый вызов обрезает его до 9,10,11, а рекурсивный вызов обрезает его до 10