小编xxm*_*use的帖子

我有一个关于如何将'recursion'转换为'tail recursion'的问题.这不是一个功课,只是当我试图从算法书中修改递归定理时弹出一个问题.我熟悉使用递归(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 

在返回之前,递归函数用不同的参数调用自己两次; 我尝试了几种方法将其转换为尾递归方式,但都错了.

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