递归转换为“尾递归” [英] convert recursion to 'tail recursion'

问题描述

我有一个关于如何递归转换为尾递归的问题。 这不是一门功课，只是一个问题，弹出时，我试图擦亮从算法书递归定理。 我熟悉使用递归（阶乘和斐波那契序列）的2个典型的例子，也知道如何实现它们以递归的方式和尾递归的方式。 我的code是如下（我使用Perl只是为了简单，但可以很容易地转换为C /的Java / C ++）

I have a question about how to convert 'recursion' to 'tail recursion'. this is not a homework, just a question pop up when I tried to polish the recursion theorem from algorithm book. I am familiar with the 2 typical examples of using recursion(factorial and Fibonacci sequence), and also know how to implement them in recursive way and tail-recursive way. My code is as below(I use Perl just to make it simple, but can be easily convert 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;$k<10;$k++) {
    print "*"x10,"\n";
    print "recP($k)=", recP($k), "\n";
}

在运行code，如下的输出：

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 invoke itself twice with different parameter before return; I tried several ways to convert this to a tail recursive way but all turns out wrong.

任何人都可以看看在code和告诉我正确的方法，使之尾递归？尤其是我相信有针对此树递归转换例程（返回之前调用递归函数多次），可以在任何阐明这光？因此，我可以使用相同的逻辑后，以处理不同的问题。 在此先感谢。

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 any shed some light on this? So I can use the same logic to handle different questions later. thanks in advance.

推荐答案

虽然你经常会看到下面的转换因子，以尾调用的一个例子：

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

请注意，这些计算的序列从头开始，而不是在一个调用栈排队待处理的延续。因此，他们在结构上更像是迭代求解比递归解决方案。不同的是迭代计划，虽然，他们从来没有修改任何变化;所有绑定都不变。这是一个有趣且有用的属性;在这些简单的情况下，它并没有太大的差别，但是写code，而不再分配使得一些编译器优化更容易。

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语句可以pssed作为一个尾调用EX $ P $。因此有可能（但不一定pretty的）重写任何递归作为尾递归

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.

通常的机制是延续传递风格，这是说，你要调用一个函数每一次，你不是目前的功能的其余部分作为一个新的功能包（以下简称继续），一个奇特的方式，并传递延续到被调用的函数。由于每个函数然后接收的延续作为参数，它必须完成它通过调用它收到的延续造成任何延续。

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.

这可能足以让你头晕，所以我会换一种说法：不是推的参数和返回的位置压入堆栈，并调用一个函数（这将在稍后返回），你把参数和延续的位置入堆栈，GOTO功能，这将在后面转到这个延续的位置。总之，你只需做栈明显的参数，然后你永远需要返回。这种编程方式是常见的事件驱动code（请参阅Python的扭曲），这是一个真正的痛苦写（和读）。所以我强烈建议让编译器做这种转换为你，如果你能找到一个这将做到这一点。

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:

       ˚F<子> N = F <子> N-1 *˚F<子> N-3 + 1
    =＆GT;
       ˚F N =＆LT;˚F N-1 <子> 1 *˚F N-1 <子> 3 +1 F N-1 <子> 1 F N-1 2 ＆GT;

fn = fn-1*fn-3 + 1
=>
Fn = <Fn-11*Fn-13+1, Fn-11, Fn-12>

我不知道这是再清楚不过，但它是最好的，我能做到。看看斐波那契例如一个稍微简单的情况。

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 的要求是什么在这种转变的限值。它适用于递归序列，其中每个元素都可以通过的previous一些公式pssed EX $ P $ 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));
}

---

由于阿列克谢伏龙芝用于以下试验： 输出（ ideone ）：

---

Thanks to Alexey Frunze for the following test: Output (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屋！