将递归转换为尾递归

Question

将递归转换为尾递归

algorithmrecursiontail-recursion

18

我想请问如何将“递归”转换为“尾递归”。

这不是一道作业题，只是我在试图理解算法书中的递归定理时突然想到的一个问题。

我熟悉使用递归实现阶乘和斐波那契数列这两个典型例子，并且也知道如何用递归和尾递归方式来实现它们。

我的代码如下（我使用 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

这个递归函数在返回之前会用不同的参数调用自身两次。我试过几种方法将其转换为尾递归函数，但均不正确。

有人可以看一下代码，并向我展示正确的使其成为尾递归的方式吗？特别是我相信对于这种树形递归（在返回之前多次调用递归函数），应该有一个转换例程，有谁能为此提供一些提示吗？这样我就可以使用相同的逻辑来处理以后的不同问题。

- xxmouse

1

真正的尾递归需要你自己处理堆栈、用汇编语言编写，或者拥有编译器支持。我认为 Perl 目前不支持它。 - Dai

3

我认为@Dai你对尾递归“移除”这个编译器优化存在困惑。他只是要求将函数转换为尾递归函数，我认为。 - Gene

5个回答

6

使用谷歌，我找到了这个页面，介绍了尾递归。基本上，您需要将函数拆分为至少两个其他函数：一个执行工作，保持当前值的“累加”，另一个是工作函数的驱动程序。下面是 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);
}

- Tosi

1

这里的关键点是递归调用是驱动程序中发生的最后一件事，因此可以用跳转到函数入口点来替换该调用。 - 500 - Internal Server Error

C编译器会优化掉那个函数调用吗？我认为不会。在其他语言中，这是自动完成的，但在C中，您必须使用某种循环显式地自己完成它。 - comocomocomocomo

1

@comocomocomocomo：大多数C编译器都会进行尾递归优化，至少对于简单的尾递归是这样的。在我的经验中，gcc做得非常好。 - rici

3

@Alexey Frunze的回答还可以，但不够准确。将任何程序转换成尾递归程序是可能的，方法是将它转换成Continuation Passing Style。

我现在没有时间，如果有时间的话，会尝试使用CPS重新实现你的程序。

- Gene

1

你可以这样做：

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

那就是尾调用优化。

- Alexey Frunze

谢谢，Alexey，到目前为止这是我得到的最好的答案，至少你提供了可行、可验证的代码。 - xxmouse

1

rici 的回答更接近你所需要的，而且它也有效。我给了他 +1。 - Alexey Frunze

很抱歉，你第二段的说法是错误的——请看Tosi的回答，可以看到如何使用累加器参数将OP的非尾递归转换为尾递归的示例。 - j_random_hacker

1

@j_random_hacker 所有声明已删除。 - Alexey Frunze

我现在意识到Tosi的答案只涉及到更简单的阶乘问题，但正如你所说，rici非常好的回答也涉及到了斐波那契数列。 - j_random_hacker

1

问题在于最后一次操作不是递归调用之一，而是乘法加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包含一个滑动窗口序列：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];

- comocomocomocomo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

虽然你经常看到以下内容作为将阶乘转换为尾调用的示例：

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

这也可以作为Fibonacci变换的模型：

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建议我从帽子里拿出递归方程，并问它是如何推导出来的。它只是原始递归，但被重新构造为单个元组的变换：

f_n = f_n-1*f_n-3 + 1 => Fⁿ = <F^n-1₁*F^n-1₃+1, F^n-1₁, F^n-1₂>

我不知道这是否更清晰，但这是我所能做的最好的。查看斐波那契示例，以获得稍微简单一些的情况。

@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