Java中的尾递归

Question

这是一个展示尾递归的好例子吗？

public printName(){
    System.out.println("Smith");
    printName();
}

我并不打算在现实生活中这样做，但是我把这个作为我的考试例子。这个例子正确吗？

- user1419170

---

这是一个更好的例子，可以展示堆栈溢出 :) - Sergey Kalinichenko

是的，除非这会导致无限递归（并在堆栈空间耗尽时使程序崩溃）。 - nhahtdh

@dasblinkenlight，有时候我会回来看你的评论。它总是能让我开心起来。 - kritzikratzi

Answer 1

不行，有两个原因:

• 尾递归只有在编译器支持它（尾调用优化）时才有价值。在Java中，它仍然会以 StackOverflowError 结束。

• 最好显示一些停止条件。你的代码等同于永远运行的循环。

考虑Scala中几乎相同的代码，唯一的区别是Scala编译器将执行尾调用优化，该循环将永远运行：

def printName() {
  println("Smith"); 
  printName()
}

- Tomasz Nurkiewicz

---

我不知道：尾递归就是尾递归。编译器可以进行优化，但这并不是重点。如果我错了，请纠正我。 - nhahtdh

@nhahtdh：OP并不是在问这是否是尾递归（毫无疑问）。他在问这是否是尾递归的一个好例子。在我看来，它不是。 - Tomasz Nurkiewicz

根据Wikipedia和我自己的计算机科学记忆，语言是否特别处理尾递归并不重要 - 该示例是尾递归的。 - A.H.

@A.H.：最后一条语句是递归调用并不意味着尾递归如此重要（出于同样的原因，我们也不教授“头递归”）——它可以被优化为简单循环才是关键。在不支持尾递归的语言中展示尾递归的例子是误导性的——在Java中这样做没有任何好处。因此，如果没有额外的说明（“请注意，在Java中...”），这就不是一个好的例子——为什么不用伪代码或者在实际有意义的支持尾递归的语言中展示呢？否则，你会看到Java开发人员认为他们获得了什么。 - Tomasz Nurkiewicz

Answer 2

尾递归更好的例子可能是这样：

public printName(int level){
    if( level <= 0 )
         return;
    System.out.prntln("Smith");
    printName(--level);
}

这个示例包括递归终止的重要部分。

此外，正如其他答案已经指出的那样：由于Java不会优化尾递归，在这种语言中使用尾递归没有意义。因此，您基本上需要通过使其成为迭代算法来优化自己的算法。这就是尾递归的关键：可以证明，任何尾递归算法都可以转换为迭代算法。

- A.H.

Answer 3

我认为这是尾递归的一个例子，因为您在程序的尾部进行递归 :) 但我不认为JVM会对此进行优化，这可能是您想要的。

- Jonatan