algorithm - 将递归转换为尾递归

Question

我有一个关于如何将“递归”转换为“尾递归”的问题。

这不是作业，只是当我试图从一本关于算法的书中完善递归定理时出现的一个问题。

我熟悉使用递归（阶乘和斐波那契数列）的 2 个典型示例，也知道如何以递归方式和尾递归方式实现它们。

我的代码如下（我使用 Perl 只是为了简化，但可以轻松转换为 C/Java/C++）。

# This is the recursive function
sub recP {
    my ($n) = @_;
    if ($n == 0 or $n == 1 or $n == 2) {
        return 1;
    } else {
        return (recP($n-3) * recP($n-1)) + 1;
    }
}

for my $k (1 .. 10) {
    print "recP($k) = ", recP($k), "\n";
}

运行代码时，输出如下：

recP(1) = 1
recP(2) = 1
recP(3) = 2
recP(4) = 3
recP(5) = 4
recP(6) = 9
recP(7) = 28
recP(8) = 113
recP(9) = 1018

递归函数在返回之前使用不同的参数调用自己两次。我尝试了几种方法将其转换为尾递归函数，但结果都是错误的。

任何人都可以看一下代码并向我展示使其尾递归的正确方法吗？特别是我相信这个树递归的转换有一个例程（在返回之前多次调用递归函数），任何人都可以对此有所了解吗？所以我以后可以使用相同的逻辑来处理不同的问题。

score 23 · Accepted Answer

尽管您经常将以下示例视为将阶乘转换为尾调用的示例：

int factorial(int n, int acc=1) {
  if (n <= 1) return acc;
  else        return factorial(n-1, n*acc);
}

这不太正确，因为它要求乘法既是关联的又是可交换的。（乘法是关联的和可交换的，但以上不能作为不满足这些约束的其他操作的模型。）更好的解决方案可能是：

int factorial(int n, int k=1, int acc=1) {
  if (n == 0) return acc;
  else        return factorial(n-1, k+1, acc*k);
}

这也可以作为斐波那契变换的模型：

int fibonacci(int n, int a=1, int b=0) {
  if (n == 0) return a;
  else        return fibonacci(n-1, a+b, a);
}

请注意，这些计算从开头开始的序列，而不是在调用堆栈中排队挂起的延续。所以它们在结构上更像是迭代解决方案而不是递归解决方案。然而，与迭代程序不同的是，它们从不修改任何变量。所有绑定都是不变的。这是一个有趣且有用的属性；在这些简单的情况下，它并没有太大的区别，但是在不重新分配的情况下编写代码会使一些编译器优化更容易。

无论如何，最后一个确实为您的递归函数提供了模型；像斐波那契数列一样，我们需要保留相关的过去值，但我们需要三个而不是两个：

int mouse(int n, int a=1, int b=1, int c=1) {
  if (n <=2 ) return a;
  else        return mouse(n-1, a*c+1, a, b);
}

附加物

在评论中，提出了两个问题。我将尝试在这里回答他们（以及更多）。

首先，应该清楚（从没有函数调用概念的底层机器架构的考虑）任何函数调用都可以改写为 goto（可能使用无界中间存储）；此外，任何 goto 都可以表示为尾调用。所以有可能（但不一定漂亮）将任何递归重写为尾递归。

通常的机制是“延续传递风格”，这是一种奇特的说法，每次你想调用一个函数时，你将当前函数的其余部分打包为一个新函数（“延续”），然后传递继续调用的函数。由于每个函数都接收一个延续作为参数，它必须通过调用它收到的延续来完成它创建的任何延续。

这可能足以让你头晕目眩，所以我换一种说法：不是将参数和返回位置压入堆栈并调用函数（稍后将返回），而是将参数和延续位置压入堆栈并转到一个函数，该函数稍后将转到延续位置。简而言之，您只需将堆栈设置为显式参数，然后您就无需返回。这种编程风格在事件驱动代码中很常见（请参阅 Python Twisted），编写（和阅读）真的很痛苦。所以我强烈建议让编译器为你做这个转换，如果你能找到一个可以做到的。

@xxmouse建议我把递归方程从帽子里拿出来，然后问它是如何推导出来的。它只是原始的递归，但被重新表述为单个元组的转换：


       f_n = f_n-1*f_n-3 + 1

    =>

       Fⁿ = <F^n-1₁*F^n-1₃+1, F^n-1₁, F^n-1₂>

我不知道这是否更清楚，但这是我能做的最好的。查看斐波那契示例以了解稍微简单的情况。

@j_random_hacker询问这种转换的限制是什么。它适用于递归序列，其中每个元素都可以用前面k元素的某个公式表示，其中k是一个常数。还有其他方法可以产生尾调用递归。例如：

// For didactic purposes only
bool is_odd(int n) { return n%2 == 1; }

int power(int x, int n, int acc=1) {
  if (n == 0)         return acc;
  else if (is_odd(n)) return power(x, n-1, acc*x);
  else                return power(x*x, n/2, acc);
}

以上与通常的非尾调用递归不同，后者执行不同（但等效且同样长）的乘法序列。

int squared(n) { return n * n; }

int power(int x, int n) {
  if (n == 0)         return 1;
  else if (is_odd(n)) return x * power(x, n-1));
  else                return squared(power(x, n/2));
}

感谢 Alexey Frunze 进行以下测试：输出（ideone）：

mouse(0) = 1
mouse(1) = 1
mouse(2) = 1
mouse(3) = 2
mouse(4) = 3
mouse(5) = 4
mouse(6) = 9
mouse(7) = 28
mouse(8) = 113
mouse(9) = 1018

score 6 · Accepted Answer

使用谷歌，我发现这个页面描述了Tail Recursion。基本上，您需要将该函数拆分为至少两个其他函数：一个执行工作，保持当前值的“累积”，另一个是您的济贫院功能的驱动程序。C中的阶乘示例如下：

/* not tail recursive */
unsigned int
factorial1(unsigned int n)
{
    if(n == 0)
        return 1;
    return n * factorial1(n-1);
}

/* tail recursive version */
unsigned int 
factorial_driver(unsigned int n, unsigned int acc)
{
    if(n == 0)
        return acc;

    /* notice that the multiplication happens in the function call */
    return factorial_driver(n - 1, n * acc);
}

/* driver function for tail recursive factorial */
unsigned int
factorial2(unsigned int n)
{
    return factorial_driver(n, 1);
}

score 3 · Accepted Answer

@Alexey Frunze 的回答还可以，但并不完全正确。通过将任何程序转换为Continuation Passing Style，确实可以将任何程序转换为所有递归都是尾递归的程序。

我现在没有时间，但如果我有时间的话，我会尝试在 CPS 中重新实现你的程序。

score 1 · Accepted Answer

你可以这样做：

#include <stdio.h>

void fr(int n, int a[])
{
  int tmp;

  if (n == 0)
    return;

  tmp = a[0] * a[2] + 1;
  a[2] = a[1];
  a[1] = a[0];
  a[0] = tmp;

  fr(n - 1, a);
}

int f(int n)
{
  int a[3] = { 1, 1, 1 };

  if (n <= 2)
    return 1;

  fr(n - 2, a);

  return a[0];
}

int main(void)
{
  int k;
  for (k = 0; k < 10; k++)
    printf("f(%d) = %d\n", k, f(k));
  return 0;
}

输出（ideone）：

f(0) = 1
f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 3
f(5) = 4
f(6) = 9
f(7) = 28
f(8) = 113
f(9) = 1018

编译器可能会fr()变成这样的东西：

void fr(int n, int a[])
{
  int tmp;

label:    

  if (n == 0)
    return;

  tmp = a[0] * a[2] + 1;
  a[2] = a[1];
  a[1] = a[0];
  a[0] = tmp;

  n--;

  goto label;
}

那将是尾调用优化。

score 1 · Accepted Answer

问题是最后一个操作不是递归调用之一，而是乘法加 1。您在 C 中的功能：

unsigned faa (int n)  // Ordinary recursion
{
    return n<3 ? 1 :
                 faa(n-3)*faa(n-1) + 1;  // Call, call, multiply, add
}

如果您更改请求值的顺序，您可以将其中一个调用变成一个循环：

unsigned foo (int n)  // Similar to tail recursion
{                     // (reverse order)
    int i;
    unsigned f;

    for (i=3, f=1; i<=n; i++)
        f = f*foo(i-3) + 1;

    return f;
}

关键是考虑在原始函数中实际计算值的顺序，而不是请求它们的顺序。

请注意，我假设您要删除一个递归调用。如果您想在函数末尾编写递归调用，期望编译器为您优化它，请参阅其他答案。

虽然，这里要做的“正确的事情（TM）”是使用动态编程来避免多次计算相同的值：

unsigned fuu (int n)  // Dynamic programming
{
    int i;
    unsigned A[4]={1,1,1,1};

    for (i=3; i<=n; i++)
    {
        memmove (A+1, A, 3*sizeof(int));
        A[0] = A[1]*A[3] + 1;
    }

    return A[0];
}

数组A包含序列的滑动窗口：A[0]==f(i), A[1]==f(i-1), A[2]==f(i-2) 等等.

memmove可能写成：

        A[3] = A[2];
        A[2] = A[1];
        A[1] = A[0];

algorithm - 将递归转换为尾递归

5 回答 5

Related

Reference