将递归转换为'尾递归'

Question

我有一个关于如何将'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 

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

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

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

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

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

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都可以表示为尾调用.所以有可能(但不一定很漂亮)将任何递归重写为尾递归.

通常的机制是"延续传递风格",这是一种奇特的说法,每当你想调用一个函数时,你改为将当前函数的其余部分打包为一个新函数("延续"),并传递给它继续调用函数.由于每个函数都接收一个延续作为参数,它必须通过调用它所接收的延续来完成它创建的任何延续.

这可能足以使你的头旋转,所以我会用另一种方式:不是将参数和返回位置推入堆栈并调用函数(稍后将返回),而是将参数和延续位置推送到堆栈并转到一个函数,稍后将转到延续位置.简而言之,您只需将堆栈作为显式参数,然后您就不需要返回.这种编程风格在事件驱动的代码中很常见(参见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

Answer 2

使用谷歌,我发现这个页面描述了Tail Recursion.基本上,您需要将函数拆分为至少两个其他函数:一个执行工作,保持当前值的"累积",另一个是您的workhouse函数的驱动程序.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);
}