将递归转换为'tail递归'

Question

我有一个关于如何将'递归'转换为'尾递归'的问题。 这不是一个家庭作业，只是当我试图抛光算法书递归定理时弹出一个问题。 我熟悉使用递归（factorial和Fibonacci序列）的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;$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都可以表示为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)); 
} 

---

感谢阿列克谢伏龙以下测试： 输出（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。基本上，您需要将该功能分成至少两个其他功能：一个执行工作，保留当前值的“累积”，另一个执行工作室功能的驱动程序。 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); 
} 

Answer 3

你可以做这样的事情：

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

这就是尾巴呼叫优化。

Answer 4

@Alexey伏龙芝的答案是好的，但不是精确的权利。确实有可能将任何程序转换成所有递归都是尾递归的程序，将其转换为Continuation Passing Style。

我现在没有时间了，但如果我有几分钟的时间，会尝试在CPS中重新实现您的程序。

Answer 5

问题是最后的操作不是递归调用之一，而是乘法1的加法。你在C函数：

unsigned faa (int n) // Ordinary recursion 
{ 
    return n<3 ? 1 : 
       faa(n-3)*faa(n-1) + 1; // Call, call, multiply, add 
} 

如果更改这些请求的值的顺序，你可以把电话接入环路之一：

unsigned foo (int n) // Similar to tail recursion 
{      // (reverse order) 
    int i; 
    unsigned f; 

    for (i=3, f=1; i<=n; i++) 
     f = f*foo(i-3) + 1; 

    return f; 
} 

的关键是在思考的顺序这些值实际上是在原始函数中计算的，而不是它们被请求的顺序。

请注意，我假设您要删除一个递归调用。如果您希望在函数末尾编写递归调用，希望编译器为您优化它，请参阅其他答案。

虽然，“正确的事情（TM）”在这里做是使用动态规划来避免计算相同的值多次：

unsigned fuu (int n) // Dynamic programming 
{ 
    int i; 
    unsigned A[4]={1,1,1,1}; 

    for (i=3; i<=n; i++) 
    { 
     memmove (A+1, A, 3*sizeof(int)); 
     A[0] = A[1]*A[3] + 1; 
    } 

    return A[0]; 
} 

阵列A包含所述序列的一个滑动窗口：甲[0] == f（i），A [1] == f（i-1），A [2] == f（i-2）等等。

的memmove可能已经写为：

 A[3] = A[2]; 
     A[2] = A[1]; 
     A[1] = A[0];