将递归转换为尾部递归

Question

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

这不是家庭作业，只是在我试图润色算法书籍中的递归定理时出现的一个问题。

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

我的代码如下（我使用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

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

有人能看一下代码并告诉我如何使其尾部递归吗？特别是我相信有一个转换这个树递归的例程（在返回之前多次调用递归函数），有人能解释一下吗？所以我以后可以用同样的逻辑来处理不同的问题。

Answer 1

@亚历克西·弗伦泽的回答是可以的，但并不完全正确。通过将任何程序转换为连续传递样式，确实可以将其转换为所有递归都是尾部递归的程序。

我现在没有时间，但如果我有几分钟的时间，我会尝试在CPS中重新实施您的程序。

Answer 2

使用google，我找到了这个描述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);
}

Answer 3

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

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都可以表示为尾调用。因此可以（但不一定漂亮）将任何递归重写为尾递归。

通常的机制是“continuation passing style”，这是一种奇特的方式，表示每次要调用函数时，都将当前函数的其余部分打包为一个新函数（“continuation”），并将该continuation传递给被调用的函数。由于每个函数随后都会收到一个作为参数的continuation，因此它必须通过调用所收到的continuation来完成它创建的任何continuation。

这可能足以让你头晕目眩，所以我将换一种说法：不是将参数和返回位置推到堆栈上并调用函数（稍后将返回），而是将参数和继续位置推到堆栈上并转到函数，函数稍后将转到继续位置。简而言之，只需将堆栈设为显式参数，然后就不需要返回。这种编程风格在事件驱动代码中很常见（请参见Python Twisted），编写（和读取）非常困难。因此，我强烈建议让编译器为您完成此转换，如果您能找到一个可以做到这一点的编译器的话。

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

我不知道这是否更清楚，但这是我能做的最好的了。看看斐波那契的例子，有一个稍微简单的例子。

@j\u random\u 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