退出递归循环的正确方法

Question

我正试图编写一个程序来识别给定N个数字数组中3个连续整数的出现，并通过删除其他两个来将它们替换为中间值。例如输入->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 37 31 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-下一次当i=1时，它会找到4,5,6，并删除4和6，新的列表是1,5,8

4-i预计退出循环时，我+ 2 <arrayInput。Count返回false，并试图立即返回修改后的数组，这里执行return语句，但不是返回结果，而是再次调用Test(temp);语句再重复几次，然后退出。请建议>

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

请定义"不能退出"。你是说for会无限循环吗?在这段代码中，我没有看到这种情况发生。

我的样子:

此函数将:整型逐个整型地遍历输入。检查这个int和后面的2是否是连续的。然后它删除这个和下一个，然后将结果反馈给同一个函数。然后，它会忽略这个可能给我们的任何值，并继续它的快乐之路。

输入为8,9,10它开始逐步通过i = 0等等。因此，它发现8、9、10是连续的，然后它删除8和9，并将结果提供给同一个函数。

所以我们重新开始:

你的输入是9它又开始步进:i = 0。它遍历并发现列表中不至少有3个值，并返回原始值。

然后，我们完全忽略该结果并继续上面的原始循环。现在i = 1，但是arrayInput中只有一个东西了，所以它应该结束了。

从你所做的，我看没有理由做一个递归调用。你没有对结果做任何事情，即使你做了，它也只有在你有一个像8 9 10 10 11这样的集合时才会对你有帮助。然后第一次调用会将其缩减为9 10 11递归调用会将其缩减为10