将递归转换为尾递归 [英] Convert recursion to tail recursion

问题描述

我有一个关于如何将递归"转换为尾递归"的问题.

I have a question about how to convert 'recursion' to 'tail recursion'.

这不是作业，只是当我试图从一本关于算法的书中完善递归定理时出现的一个问题.

This is not a homework, just a question that popped up when I tried to polish the recursion theorem from a book on algorithms.

熟悉使用递归的2个典型示例(阶乘和斐波那契数列)，也知道如何以递归方式和尾递归方式实现它们.

I am familiar with the 2 typical examples of using recursion (factorial and Fibonacci sequence), and also know how to implement them in a recursive way and tail-recursive way.

我的代码如下(我使用 Perl 只是为了简单起见，但可以很容易地转换为 C/Java/C++).

My code is as below (I use Perl just to make it simple, but can be easily converted to 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), "
";
}

运行代码时，输​​出如下:

When running the code, the output as below:

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

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

The recursive function invokes itself twice with different parameters before return. I've tried several ways to convert this to a tail recursive function but all turned out to be wrong.

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

Can anybody take a look at the code and show me the correct way to make it tail-recursive? Especially I believe there is a routine for the conversion for this tree recursion (invoke recursive function multiple times before return), can anyone shed some light on this? So I can use the same logic to handle different questions later.

推荐答案

尽管您经常看到以下将阶乘转换为尾调用的示例:

Although you often see the following as an example of converting factorial to tail-call:

int factorial(int n, int acc=1) {
  if (n <= 1) return acc;
  else        return factorial(n-1, n*acc);
}

它不太正确，因为它要求乘法既是结合又是可交换的.(乘法是关联和可交换的，但以上不能作为不满足这些约束的其他操作的模型.)更好的解决方案可能是:

it's not quite correct, since it requires multiplication to be both associative and commutative. (Multiplication is associative and commutative, but the above doesn't serve as a model for other operations which don't satisfy those constraints.) A better solution might be:

int factorial(int n, int k=1, int acc=1) {
  if (n == 0) return acc;
  else        return factorial(n-1, k+1, acc*k);
}

这也用作斐波那契变换的模型:

This also serves as a model for the fibonacci transform:

int fibonacci(int n, int a=1, int b=0) {
  if (n == 0) return a;
  else        return fibonacci(n-1, a+b, a);
}

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

Note that these compute the sequence starting at the beginning, as opposed to queueing pending continuations in a call stack. So they are structurally more like the iterative solution than the recursive solution. Unlike the iterative program, though, they never modify any variable; all bindings are constant. This is an interesting and useful property; in these simple cases it doesn't make much difference, but writing code without reassignments makes some compiler optimizations easier.

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

Anyway, the last one does provide a model for your recursive function; like the fibonacci sequence, we need to keep the relevant past values, but we need three of them instead of two:

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

附录

在评论中，提出了两个问题.我会试着在这里回答他们(还有一个).

In comments, two questions were raised. I'll try to answer them (and one more) here.

首先，应该清楚(从没有函数调用概念的底层机器架构的考虑)任何函数调用都可以重新表述为goto(可能具有无界中间存储)；此外，任何 goto 都可以表示为尾调用.因此，可以(但不一定漂亮)将任何递归重写为尾递归.

First, it should be clear (from a consideration of the underlying machine architecture which has no concept of function calling) that any function call can be rephrased as a goto (possibly with non-bounded intermediate storage); furthermore, any goto can be expressed as a tail-call. So it is possible (but not necessarily pretty) to rewrite any recursion as tail-recursion.

通常的机制是continuation-passing style"；这是一种奇特的说法，每次您想要调用一个函数时，您都将当前函数的其余部分打包为一个新函数(continuation")，并将该 continuation 传递给被调用的函数.由于每个函数都接收一个延续作为参数，它必须通过调用它接收到的延续来完成它创建的任何延续.

The usual mechanism is "continuation-passing style" which is a fancy way of saying that every time you want to call a function, you instead package the rest of the current function as a new function (the "continuation"), and pass that continuation to the called function. Since every function then receives a continuation as an argument, it has to finish any continuation it creates with a call to the continuation it received.

这可能足以让你头晕目眩，所以我换一种说法:不是将参数和返回位置推入堆栈并调用函数(稍后将返回)，而是推入参数和继续位置进入堆栈并转到一个函数，该函数稍后将转到继续位置.简而言之，您只需将堆栈设置为显式参数，然后就无需返回.这种编程风格在事件驱动代码中很常见(参见 Python Twisted)，编写(和阅读)真的很痛苦.所以我强烈建议让编译器为你做这个转换，如果你能找到一个可以做到的.

That's probably enough to make your head spin, so I'll put it another way: instead of pushing arguments and a return location onto the stack and calling a function (which will later return), you push arguments and a continuation location onto the stack and goto a function, which will later goto the continuation location. In short, you simply make the stack an explicit parameter, and then you never need to return. This style of programming is common in event-driven code (see Python Twisted), and it's a real pain to write (and read). So I strongly recommend letting compilers do this transformation for you, if you can find one which will do that.

@xxmouse 建议我从帽子里拿出递归方程，并询问它是如何推导出来的.它只是原始递归，但重新表述为单个元组的转换:

@xxmouse suggested that I pulled the recursion equation out of a hat, and asked how it was derived. It's simply the original recursion, but reformulated as a transformation of a single tuple:

我不知道这样是否更清楚，但这是我能做的最好的.查看斐波那契示例，了解稍微简单的情况.

I don't know if that's any clearer, but it's the best I can do. Look at the fibonacci example for a slightly simpler case.

@j_random_hacker 询问这种转换的限制是什么.它适用于递归序列，其中每个元素都可以用前面的 k 元素的某个公式表示，其中 k 是一个常数.还有其他方法可以产生尾调用递归.例如:

@j_random_hacker asks what the limits on this transformation are. It works for a recursive sequence where each element can be expressed by some formula of the previous k elements, where k is a constant. There are other ways to produce a tail-call recursion. For example:

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

以上与通常的非尾调用递归不同，后者执行不同(但等效且等长)的乘法序列.

The above is not the same as the usual non-tail-call recursion, which does a different (but equivalent and equally long) sequence of multiplications.

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

这篇关于将递归转换为尾递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！