尾巴的Java

Question

/向前递推我不明白为什么这是向前递推：

int count(int x) { 
    if(x<=0) return 0; 
    return 1 + count(x - 1); 
} 

这是对模拟考试的问题时，得到的答复是，其前向迭代。为什么会这样？我怎么能区分这两者？

Answer 1

你正在做一个补充后自称。尾递归的意思是绝对的没有什么可以在

如果你理解了实现，这是明确的原因。

假设我们从main第一次致电count，这是program counter0xAAA。然后它执行其大部分方法。我们会说这个堆栈帧的递归调用数为0xBBB。如果您使用尾递归，在调用自身时，它可以将返回地址设置为0xAAA（直接转到调用我的代码）。如果在之后的任何东西之后，它必须将返回地址设置为0xBBC（加法的地址）。因为它不需要堆栈帧来存储返回地址，所以将递归转换为迭代也更容易。当count自己调用时，它可以跳转到方法的开头。

该解决方案（在简单的例子）是建立在结果的另一个参数：

int count(int x, int res) { 
    if(x<=0) return res; 
    return count(x - 1, res + 1); 
} 

注意，我们以后什么也不做。

Answer 2

你看过this SO question, tail vs forward recursion吗？

马修有了答案，而长表将是：

int count(int x) { 
    if(x<=0) return 0; 
    return 1 + count(x - 1); 
} 

可以写为（和扩展为类似）：

int count(int x) { 
    if(x<=0) return 0; 
    int tmp_result = count(x - 1); 
    return 1 + tmp_result; // e.g. recursion is not last 
}