但是,为什么Java至少没有对它进行尾递归优化呢?静态方法并强制使用编译器调用静态方法的正确方法?
为什么Java根本不支持尾递归?
我不确定是否在这里根本没有任何困难。
关于建议的副本,如JörgW Mittag1所述:
另一个问一个关于TCO,这个关于TRE。 TRE比TCO简单得多。
另外,另一个问题是关于JVM对希望编译为JVM的语言实现施加哪些限制,这个问题是关于Java的,Java是不受JVM限制的一种语言,因为JVM规范可以由设计Java的同一个人来更改。
最后,JVM中甚至没有关于TRE的限制,因为JVM确实具有内部方法GOTO,这是TRE所需要的。
1添加了格式以标注要点。
#1 楼
正如这段视频中Oracle的Java语言架构师Brian Goetz所解释的:jdk类中的许多安全敏感方法都依赖于对堆栈帧的计数在jdk库代码和调用代码之间找出谁在调用它们。更改堆栈中帧数的任何操作都会破坏此错误并导致错误。他承认这是一个愚蠢的原因,因此JDK开发人员已替换了此机制。
然后他进一步提到这不是优先级,而是尾递归br />最终会完成的。
NB这适用于HotSpot和OpenJDK,其他VM可能会有所不同。
评论
我很惊讶这样一个如此干脆的答案!但这似乎确实是一个答案-由于过时的技术原因,现在有可能还没有完成,所以现在我们只等某人确定它足够重要就可以实施。
– BrianH
2015年2月4日在21:20
为什么不实施解决方法?就像是在幕后的标签定位器一样,它跳转到方法调用的顶部并带有新的参数值?这将是编译时的优化,并且不需要移动堆栈帧或引起安全冲突。
–詹姆斯·沃特金斯(James Watkins)
15年2月4日在21:45
如果您或这里的其他人可以更深入地研究并提供那些“安全敏感方法”是什么,那对我们会更好。谢谢!
–通知A
2015年2月6日下午0:39
@InstructedA-请参阅securejava.com/chapter-three/chapter-three-6.html,其中包含有关Java Security Manager系统在Java 2发行版左右的工作方式的详细说明。
–法律
15年2月8日在12:03
一种解决方法是使用另一种JVM语言。例如,Scala不在编译器中执行此操作。
–詹姆斯·摩尔
16-09-28在23:12
#2 楼
Java没有尾调用优化,原因是大多数命令式语言都没有。命令式循环是该语言的首选样式,程序员可以用命令式循环代替尾部递归。对于因样式而禁止使用的功能,复杂性是不值得的。在计算机开始按核而不是GHz扩展后的最后十年左右。即使到现在,它也不是很流行。如果我建议在工作中使用尾部递归来替换命令式循环,那么一半的代码审阅者会大笑,而另一半会给人以困惑的印象。即使在函数式编程中,通常也要避免尾部递归,除非其他构造(例如高阶函数)不能完全匹配。评论
这个答案似乎不正确。仅仅因为不严格要求尾递归并不意味着它就没有用。递归解决方案通常比迭代更容易理解,但是缺少尾部调用意味着递归算法对于大问题的规模变得不正确,这将使堆栈崩溃。这是关于正确性,而不是性能(为简单起见,交易速度通常是值得的)。正确答案指出,缺少尾部调用是由于依赖于堆栈跟踪而不是命令性偏执的怪异安全模型所致。
–阿蒙
2015年2月4日15:05
@amon James Gosling曾经说过,除非有多个人提出要求,否则他不会向Java添加功能,只有这样他才会考虑。因此,如果答案的一部分确实是“您可以始终使用for循环”(对于一流函数与对象同样如此),我也不会感到惊讶。我不会称其为“命令性偏执”,但我不认为它在1995年时有很高的需求,当时最主要的问题可能是Java的速度和缺少泛型。
–Doval
2015年2月4日在15:47
@amon,一个安全的模型使我感到震惊,因为没有将TCO添加到现有语言中是一个合理的理由,但是一个糟糕的理由却是没有首先将其设计为该语言。您不会抛出主要的程序员可见功能来包含次要的幕后功能。 “为什么Java 8没有TCO”和“为什么Java 1.0没有TCO?”是一个截然不同的问题。我在回答后者。
–卡尔·比勒费尔特(Karl Bielefeldt)
15年2月4日在16:21
@rwong,您可以将任何递归函数转换为迭代函数。 (如果可以的话,我在这里写了一个例子)
– alain
15年2月4日在22:14
@ZanLynx取决于问题的类型。例如,访客模式可以从总体拥有成本中受益(取决于结构和访客的细节),而与FP无关。尽管使用蹦床进行转换似乎更自然(取决于问题),但通过状态机还是一样。同样,虽然可以从技术上讲,使用循环来实现树,但我相信共识是递归更为自然(对于DFS而言,尽管在这种情况下,即使使用TCO,由于堆栈限制,您也可以避免递归)。
– Maciej Piechotka
2015年2月5日下午4:43
#3 楼
Java没有严格的调用优化,因为JVM没有用于尾部调用的字节码(用于某些静态未知的函数指针,例如,某些vtable中的方法)。可能是出于技术上的原因,在JVM规范的所有者中很难在JVM中添加新的字节码操作(这将使其与该JVM的早期版本不兼容)。不添加的技术原因JVM规范中的一个新字节码包括一个事实,即现实生活中的JVM实现是非常复杂的软件(例如,由于它正在执行许多JIT优化)。
对某些未知函数的尾部调用需要替换当前的堆栈框架带有一个新的框架,并且该操作应位于JVM中(这不仅是更改生成字节码的编译器的问题)。
评论
问题不是关于尾调用,而是关于尾递归。问题不是关于JVM字节码语言,而是关于Java编程语言,这是一种完全不同的语言。 Scala编译为JVM字节码(以及其他),并消除了尾递归。 JVM上的方案实现具有完整的正确尾调用。 Java 7(JVM Spec,第三版)添加了一个新的字节码。即使不需要特殊的字节码,IBM的J9 JVM也可以执行TCO。
–Jörg W Mittag
2015年2月4日在16:59
@JörgWMittag:是的,但是然后,我想知道Java编程语言没有正确的尾调用是否是真的。声明Java编程语言不必进行适当的尾调用可能更为准确,因为规范中没有任何规定。 (也就是说:我不确定规范中的任何内容实际上都禁止实现消除尾部调用。只是没有提及。)
–ruakh
2015年2月5日,下午1:45
评论
引用埃里克·利珀特(Eric Lippert)的话:“功能并不便宜;它们非常昂贵,而且它们不仅必须证明自己的成本是合理的,而且还必须证明不采用我们在该预算中可以完成的其他一百项功能的机会成本。” Java的设计部分是为了吸引C / C ++开发人员,并且不能保证使用这些语言进行尾部递归优化。如果我错了,请纠正我,但是Eric Lippert是具有尾递归优化功能的C#设计师吗?
是的,他在C#编译器团队中。
据我了解,如果满足某些条件,JIT可能会这样做。因此在实践中,您不能依靠它。但是C#是否具备它对Eric而言并不重要。
@InstructedA如果深入研究,您会发现它从未在32位JIT编译器中完成。 64位JIT在许多方面都更新,更智能。甚至更新的实验性编译器(适用于32位和64位)都更加智能,并且将支持IL中没有明确要求的尾递归优化。您还需要考虑另一点-JIT编译器没有很多时间。它们对速度进行了严格的优化-可能需要花费数小时才能在C ++中编译的应用程序,最多(至少部分)仍需要在数百毫秒内将IL从本机转换为本机。