Java中的尾部/前向递归

Question

我不明白为什么这是前向递归:

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

这是一个关于练习考试的问题,答案是它的前向递归.为什么会这样？我怎么能区分这两者？

Answer 1

在给自己打电话之后,你正在做一个补充.尾递归意味着绝对没有什么可以追随

如果您了解实施,那么很明显为什么.

假设我们count第一次来自main,在程序柜台 0xAAA.然后它完成了大部分方法.我们会说对count的递归调用是0xBBB针对这个堆栈帧.如果您正在使用尾递归,那么在调用自身时,它可以将返回地址设置为0xAAA(直接转到调用我的代码).如果之后正在执行任何操作,则必须将返回地址设置为0xBBC(添加的地址).因为它不需要堆栈帧来存储返回地址,所以将递归转换为迭代也更容易.当count自己调用时,它可以跳转到方法的开头.

解决方案(对于简单的例子)是在另一个参数中建立结果:

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

注意我们之后什么都不做.