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

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

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

Answer 1

虽然你经常看到下面是将阶乘转换为尾调用的例子:

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);
}

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

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

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”)，并将该延续传递给被调用函数。由于每个函数随后都接收一个延续作为参数，因此它必须通过调用它接收到的延续来完成它创建的任何延续。

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

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


f<sub>n</sub> = f<sub>n-1</sub>*f<sub>n-3</sub> + 1<br/>
=><br/>
F<sup>n</sup> = <F<sup>n-1</sup><sub>1</sub>*F<sup>n-1</sup><sub>3</sub>+1, F<sup>n-1</sup><sub>1</sub>, F<sup>n-1</sup><sub>2</sub>>

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

@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