将递归转换为“尾递归”
我有一个关于如何将'recursion'转换为'tail recursion'的问题。 这不是一项家庭作业，只是当我试图从算法书中抛光递归定理时弹出一个问题。 我熟悉使用递归的2个典型例子（factorial和Fibonacci序列），并且知道如何以递归方式和尾递归方式实现它们。 我的代码如下（我使用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;$k<10;$k++) {
print "*"x10,"n";
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
递归函数在返回前用不同的参数调用两次; 我尝试了几种方法将其转换为尾部递归方式，但都是错误的。
任何人都可以看看代码，并告诉我使它成为尾递归的正确方法吗？ 特别是我相信这个树递归转换有一个例程（在返回之前多次调用递归函数），任何人都可以对此有所了解吗？ 所以我可以用相同的逻辑来处理不同的问题。 提前致谢。
尽管经常将以下内容作为将factorial转换为tail-call的示例：
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都可以表示为tail-call。 所以有可能（但不一定非常漂亮）将任何递归重写为尾递归。
通常的机制是“继续传递风格”，这是一种奇特的方式，说每次你想调用一个函数时，你将当前函数的其余部分打包为一个新函数（“继续”），并通过延续到被调用函数。 由于每个函数都接收到一个延续作为参数，所以它必须通过调用它所接收的延续来完成它创建的任何延续。
这可能足以让你的头脑旋转，所以我会换个方式：不是将参数和返回位置推入堆栈并调用函数（稍后返回），而是将参数和延续位置推入堆栈并转到一个函数，它将在稍后转到延续位置。 简而言之，你只需将堆栈作为一个明确的参数，然后你永远不需要返回。 这种编程风格在事件驱动代码中很常见（请参阅Python Twisted），并且写入（和读取）是一种真正的痛苦。 所以我强烈建议让编译器为你做这个转换，如果你能找到一个能做到这一点的转换。
@xxmouse建议我将递归方程从一顶帽子中拉出来，并询问它是如何派生的。 它只是原始的递归，但是重新表达为一个元组的变换：
fn = fn-1*fn-3 + 1
=>
Fn = <Fn-11*Fn-13+1, Fn-11, Fn-12>
我不知道这是否更清楚，但这是我能做的最好的。 看看斐波纳契的例子，稍微简单些。
@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
使用谷歌，我发现这个页面描述尾递归。 基本上，您需要将该功能分成至少两个其他功能：一个执行工作，保留当前值的“累积”，另一个执行工作室功能的驱动程序。 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);
}
@Alexey Frunze的答案是好的，但不完全正确。 确实有可能将任何程序转换为所有递归都是尾递归的程序，方法是将其转换为Continuation Passing Style。
我现在没有时间，但是如果我有几分钟的时间，会尝试在CPS中重新实现您的程序。
链接地址: http://www.djcxy.com/p/80687.html