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

Question

我想知道，当将 "regular" 递归函数重写为尾递归函数时，我该如何进行？有什么攻略吗？

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

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

感谢任何帮助。

Answer 1

答案取决于您对 "tail recursive" 函数和 "rewriting" 函数的定义，但我将假定对这些方面的理解大多是非正式的：

没有原始版本中没有的迭代。
没有明确的 stacks/arrays/etc。原始版本中没有。
除尾递归调用外没有递归调用（意思是，调用是 return 语句中的整个表达式）。
辅助函数可以，但相互递归不行。
由于诸如整数溢出、堆栈溢出、舍入错误等现实世界的考虑而导致的非等价性无需关注。

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

那么，让我们从您的函数开始：

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

现在，如果 n 是奇数，那么我们在第 3 行 return n；所以如果我们到达第 5 行，那么我们知道 n 必须是偶数。这意味着如果我们已经到达第 5 行，那么 n+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% 的时间使用这种模式。

Answer 2

您需要从基本情况开始，然后查看最接近基本情况的默认情况的模式。在您的情况下，所有基本情况都会计数，直到 n 为 11，因此最接近基本情况的默认情况是 9。下一个是 7 它包括 9 所以我们有这个模式：

n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ... 
r 0 | 2 | 4 | 6 | 8 |  10 11 12 13
    |   |   |   |  10+11
    |   |   |   8+10+11
    |   |   6+8+10+11
    |   4+6+8+10+11     
    2+4+6+8+10+11

由此可见，11以下的所有奇数成为后继和10以内的所有偶数加11的和。

我建议这样的迭代尾递归版本：

int rec_helper(int n, int acc) {
    if (n == 12) {
        return 11+acc;
    }
    return rec_helper(n+2, acc+n);
}

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

在这种情况下，虽然这是矫枉过正。请注意，除了 11 之外的系列是 Arithmetic progression 并且总和定义明确。结果根本不需要递归：

int rec(int n) {
    if (n % 2 || n > 10) {
        return n;
    }
    return (121-n*n)/4;
}

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

Rewrite linear recursive function as tail-recursive function

algorithm

recursion

pseudocode

tail-recursion