将递归转换为尾递归
将递归转换为尾递归
提问于 2013-03-21 08:38:26
我有一个关于如何将“递归”转换为“尾递归”的问题。
这不是家庭作业，只是当我试图完善算法书中的递归定理时出现的一个问题。
我熟悉使用递归的两个典型示例(阶乘和斐波那契数列)，也知道如何以递归方式和尾递归方式实现它们。
我的代码如下所示(我使用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递归函数在返回之前使用不同的参数调用自身两次。我尝试了几种方法将其转换为尾递归函数，但都被证明是错误的。
有没有人可以看一下代码，告诉我让它尾递归的正确方法？特别是，我相信这个树递归的转换有一个例程(在返回之前多次调用递归函数)，有人能解释一下这一点吗？所以以后我可以使用相同的逻辑来处理不同的问题。
回答 4
Stack Overflow用户
发布于 2013-03-21 08:48:39
使用谷歌，我找到了这个描述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);
}Stack Overflow用户
发布于 2013-03-21 13:40:47
@Alexey Frunze的答案是好的，但并不完全正确。通过将其转换为Continuation Passing Style，确实可以将任何程序转换为所有递归都是尾递归的程序。
我现在没有时间，但如果我有几分钟的时间，我会尝试用CPS重新实现您的程序。
Stack Overflow用户
发布于 2013-03-21 08:55:15
你可以这样做：
#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;
}这将是尾部调用优化。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15537432
复制相关文章
相似问题
腾讯云开发者
