时间戳

首页 > 解决方案 > 将线性递归函数重写为尾递归函数

algorithm - 将线性递归函数重写为尾递归函数

问题描述

我想知道，在将“常规”递归函数重写为尾递归函数时，我该如何进行？有什么策略吗？

例如：我有一个简单的函数，我想把它变成一个尾递归函数：

int rec(int n) {
    if (n % 2 || n > 10) {
    return n;
    }
    return  rec(n+1) + rec(n+2);
}

任何帮助表示赞赏。

标签： algorithmrecursionpseudocodetail-recursion

解决方案

答案取决于您对“尾递归”函数和“重写”函数的定义，但我将假设主要是非正式的理解：

  • 没有原始版本中没有的迭代。
  • 没有明确的堆栈/数组/等。原始版本中没有。
  • 没有递归调用，除了尾递归调用（意思是，调用是语句中的整个表达式return）。
  • 辅助函数可以，但相互递归不行。
  • 由整数溢出、堆栈溢出、舍入误差等现实世界的考虑导致的不等价性无关紧要。

那不碍事。. . 您应该知道，并非总是可以以尾递归方式重写函数。您自己的示例具有在非基本情况下进行两次递归调用的函数，我们显然不能将它们都更改为语句中的整个表达式return，因此您的示例可以重写为尾递归的唯一原因是我们可以消除其中一个电话。

所以，让我们从你的功能开始：

int rec(int n) {
    if (n % 2 || n > 10) {
        return n;                 // line 3
    }
    return  rec(n+1) + rec(n+2);  // line 5
}

现在，如果n是奇数，那么我们n在第 3 行返回；所以如果我们到达了第 5 行，那么我们知道那n一定是偶数。这意味着如果我们已经到达第 5 行，则 thenn+1是奇数，rec(n+1)将是n+1。所以我们可以消除一个递归调用：

int rec(int n) {
    if (n % 2 || n > 10) {
        return n;
    }
    return (n+1) + rec(n+2);
}

接下来，它有助于扩展一个真实的例子，看看它是什么样子的：

rec(6) = 7 + rec(8)
       = 7 + (9 + rec(10))
       = 7 + (9 + (11 + rec(12)))
       = 7 + (9 + (11 + (12)))

一个重要的见解是，由于加法是关联的，我们可以以相反的方式对术语进行分组：

rec(6) = ((7 + 9) + 11) + 12

这很有用，因为这意味着我们可以在继续进行时计算结果的部分总和，并将其作为单独的参数传递：

int rec(int n, int sum_so_far) {
    if (n % 2 || n > 10) {
        return sum_so_far + n;
    }
    return rec(n+2, sum_so_far + (n+1));
}

. . . 现在我们有了一个尾递归函数，但它需要客户端传入一个额外的参数！为了解决这个问题，我们只需将其重命名为rec_helper并将其包装在一个函数中供客户调用：

int rec_helper(int n, int sum_so_far) {
    if (n % 2 || n > 10) {
        return sum_so_far + n;
    }
    return rec_helper(n+2, sum_so_far + (n+1));
}

int rec(int n) {
    return rec_helper(n, 0);
}

如您所见，没有通用策略。相反，我们需要分析函数，并利用有关整数的事实来消除一个递归调用，然后我们需要再次做同样的事情来将另一个递归调用转换为尾递归调用。

然而，我们所做的一个方面是一种非常常见的模式，即将递归移动到一个辅助函数中，该函数接受一个额外的参数，其中该参数包含到目前为止已计算的部分结果。我会说在构建尾递归函数时，我至少有 90% 的时间使用这种模式。

推荐阅读