递归和尾递归的实现逻辑

Question

我已经编写了代码来总结一个数组的元素

递归

 static int sum(int[] array)
        {

            if (array.Length == 1)
                return array[0];

            else
            {
                int[] newArr = new int[array.Length - 1];
                for (int i = 1; i < array.Length; i++)
                {
                    newArr[i - 1] = array[i];
                }

                return array[0] + sum(newArr);
            }
        }

并与

尾递归

 static int sumTR(int[] array, int sum)
        {
            //base case
            if (array.Length == 1)
                return array[0] + sum;
            else
            {
                  //tail recursive case
                int[] newArr = new int[array.Length - 1];

                for (int i = 1; i < array.Length; i++)
                    newArr[i - 1] = array[i];

               
                return sumTR(newArr, array[0] + sum);
            }
        }

据我了解，在 尾递归 中，基本方法不应该等待递归方法完成执行，也不应该依赖于它的输出。此实施是否是实现该目标的正确方法？

Answer 1

As I understood, in the tail recursion the base method shouldn't be waiting for the recursive method to finish executing and shouldn't be dependent on its output

这不太正确。尾递归主要使编译器能够应用 tail call optimization（如果支持），即将递归重写为常规循环。这具有减少堆栈中内存使用的优点。与'not waiting'.

无关

在第一个示例中，它必须为列表中的每个项目保留一个堆栈帧，如果您的列表很长，您可能会运行超出堆栈内存并获得计算器溢出。

在尾递归的情况下，当到达尾调用时不再需要当前堆栈帧，因此每次调用都可以重复使用相同的堆栈帧，这应该导致代码类似于常规循环。

Is this implementation the right way to achieve that?

我觉得不错。但这并不一定意味着会应用优化，它似乎取决于编译器版本，并且可能有其他要求。请参阅 Why doesn't .NET/C# optimize for tail-call recursion? 一般来说，我建议依靠语言规范而不是编译器优化来确保程序的正确功能。

请注意，递归通常不是 c# 中的理想方法。对于求和这样简单的事情，使用常规循环更容易、更快速、更易读。对于更复杂的情况，比如遍历树，递归可能是合适的，但尾调用优化在这种情况下不会有太大帮助。

Answer 2

递归是一个函数调用自身。尾递归是一种函数调用自身的方式，使得对自身的调用是它执行的最后一个操作。这很重要，因为支持尾递归的编译器可以在递归调用之前消除堆栈帧，甚至可以将其转换为循环。在任何一种情况下，都可以防止由于重复调用而导致堆栈帧的累积，从而消除堆栈溢出的可能性。

就是说，您的递归 sum() 函数有效但效率很低：它为每一步创建新数组。有一种更简单的递归计算总和的方法：

static int sum(int[] array)
{
    return sum(array, array.Length - 1);
}

static int sum(int[] array, int index)
{
    return array[index] + (index == 0 ? 0 :
        sum(array, index - 1));
}

第一个sum()函数以适当的参数调用辅助函数，辅助函数只需要调整提供的索引即可。为简洁起见，这里使用三元表达式来完成：它使函数本质上保持单行，并且清楚地说明递归调用不是返回前的最后一个操作（加法是）。

要将此计算转换为尾递归计算，我们需要为中间结果添加一个参数：

static int sum(int[] array)
{
    return sum(array, array.Length - 1, 0);
}

static int sum(int[] array, int index, int res)
{
    return index < 0 ? res :
        sum(array, index - 1, res + array[index]);
}

这里将加法移到递归调用之前，调用显然是最后一个操作，使函数尾递归。

Answer 3

您可以在递归到数组末尾时使用 Span. You can then slice 来防止复制数组。

int sum(Span<int> span, int subtotal)
{
    return span.Length > 0
        ? sum(span.Slice(1), subtotal + span[0])
        : subtotal;
}

Span 是不久前添加的，我相信是在 .NET Core 中，它带来了相当多的性能改进。它允许将更多代码从 C++ 核心转移到 C#。 Here 是我阅读的一篇关于该主题的文章。

递归和尾递归的实现逻辑

Logic of implementing Recursion and Tail Recursion

c#

algorithm

sorting

recursion

tail-recursion