我正在尝试实现一个尾部递归阶乘计算器，但仍然会出现堆栈溢出。有人能帮我弄清楚为什么吗？
- 我读到Java 8支持Tail调用优化，但我认为我一定没有正确实现它
- 我读到使用lambda表达式是可能的。我不确定我是否完全理解这个概念，但我仍在阅读
- 我只是在寻找任何关于如何使用真正的尾调用优化、lambda表达式或其他我可以使用的方法的建议
代码：
package factorielRecursiveTerminale;
import java.math.BigInteger;
import java.util.Scanner;
public class factorielRecursiveTerminale {
public static BigInteger factoriel(BigInteger n, BigInteger m) {
if (n.compareTo(BigInteger.ZERO) < 1) return m;
return factoriel(n.subtract(BigInteger.ONE), n.multiply(m));
}
public static BigInteger fact(int n) { //convertir l'entree en BigInteger et lancer la recursion
if(n < 0) {
return BigInteger.valueOf(-1);
}
BigInteger b = BigInteger.valueOf(n);
return factoriel(b, BigInteger.ONE);
}
public static void runBigFact() { //gestion des erreurs + boucle d'entree de valeurs.
String valeurRecu = "";
int valeur;
BigInteger resultat;
System.out.println("Calcul Factorieln");
while(!valeurRecu.contentEquals("q")){
System.out.println("Entrer la valeur a calculer (q - quitter) : ");
Scanner entree = new Scanner(System.in);
valeurRecu = entree.nextLine();
if (valeurRecu.contentEquals("q")) entree.close();
else {
try {
valeur = Integer.parseInt(valeurRecu);
}catch (NumberFormatException e){
System.out.println("Pas un entier. Essayer encore.n");
continue;
}
try {
resultat = fact(valeur);
if(resultat.compareTo(BigInteger.valueOf(-1)) == 0) {
System.out.println("Valeur negative. Essayer encore.n");
}
else System.out.println("Factoriel " + valeur + " -> " + fact(valeur) + "n");
} catch(StackOverflowError e) {
System.out.println("Depassement de la pile. Essayer un entier plus petit.n");
continue;
}
}
}
System.out.println("Au revoir! :)n");
}
public static void main(String[] args) {
runBigFact();
}
}
我读到JAVA 8支持Tail调用优化，但我认为我一定没有正确实现它。
那么你读错了。或者，你读了一个正确的陈述，但没有正确解读。
语言Java不支持尾调用递归。它从来没有。它可能永远不会。
然而，虚拟机java有一些特性，使其他非java语言更容易编译成类文件在java运行时运行，以支持TCO。这大概就是你读到的。
我只是在寻找任何关于如何使用真正的尾部调用优化、lambda表达式或我可以使用的任何方法的建议。
用scala或类似的语言编写。
说真的，java怎么没有TCO
TCO是昂贵的：Java有一条规则，当发生错误时，你会得到一个堆栈跟踪，而堆栈跟踪是一个定义良好的概念，至关重要的是，它为每个逻辑调用跟踪一个堆栈帧。如果TCO存在，这种情况就不能继续下去。当然，也有一些选择：堆栈上的每个单独的帧都可以获得一个"计数器"，这样堆栈跟踪在正确表示"并且此调用序列已重复8190581次"的同时保持较小的内存占用。lang规范中还有一大堆关于它是如何工作的，什么时候起作用，什么时候不起作用，以及这一切意味着什么的文本，规范中的任何额外页面都是永远的维护负担——这并不是"将TCO添加到java中是绝对优越的，所以当我们开始使用它时，slam-dunk和任何具有该功能的Pull请求都将立即集成"。
此外，TCO作为一种模式是一种做事方式，但它不是唯一的方式。对于任何可以写为TCO递归应用程序的东西，通常都不难将其重构为基于循环的非递归算法。相比之下，比如说，基于产量的异步操作，在那里你当然可以重写(嘿，这都是图灵机器)，但重写会很困难，结果代码也很难理解。我不想讨论yield/async风格编码的价值(或缺乏价值)，只是强调TCO没有那种"啊，但是，如果TCO是个好主意，那么只有TCO才能做到"的外表。
我手头没有这些链接，但那些对java的未来有很大影响力的人，如Brian Goetz、Mark Reinhold等，已经说过这种说法。因为如果你不能说服那些人，那就永远不会发生。
那么我在java中该怎么做呢
不要使用递归；而是使用while或for。
最新消息：那个博客怎么办
在评论中，您已链接到此博客条目。是的。。而不是TCO。
这就是使用lambdas编写一个框架，让您或多或少地模拟TCO，但它不是TCO。博客描述了一个小框架，因此，你需要他们粘贴的所有东西：特别是TailCall接口。
该代码的工作原理如下：
- 您的"recursive"方法根本不是递归的，它总是在不调用自己的情况下快速返回
- 它返回一个lambda，它可以调用自己。但是，正如我们刚刚介绍的那样，调用自己可以快速返回而不需要递归，并且它返回一个函数
- 框架将执行您的函数，该函数通常会产生一个函数(或实际结果)。它循环(因此没有递归)，重复应用以下过程：；调用函数。如果它返回一个函数，则循环。如果它返回一个结果，好吧，这就是我们想要的结果，所以只返回那个">
这描述了TCO试图实现的目标(用不同的参数反复调用同一个函数，直到达到硬编码的边缘情况，然后反向退出)，但不使用TCO来实现。
因此，那篇博客文章说："看，java中的TCO！"具有误导性。
就像我在说："看，隧道墙上的画笔"以及描述如何使用罐的喷漆以看起来像手工刷过的方式对隧道墙进行喷漆。这很好，但称之为"刷墙"是一种误导。你最多可以说：；想在隧道里创作画笔风格的艺术吗？好吧，你不能，我也不能解决这个问题，但我可以告诉你如何获得类似的结果&"；。
*)永远不要说永远，但我的意思是：目前还没有任何计划，java平台的未来计划将在未来许多年后公布。我认为"java(该语言)在4年内没有尾调用递归"的几率为1到40，但我仍然相信这一点
您可能会发现这很有用。与您之前的尝试相比，我得到了一些改进，但在这种情况下，导致SO的并不是BigInteger对象的大小。在我的机器上，这两种方法都会导致n的堆栈溢出在14000到15000之间。simpleLong只是一种减少Long的基本递归方法，它仍然会在15000时爆炸。两者都以14000的成绩成功。
public static void main(String[] args) {
count = 0;
long n = 14000;
simpleLong(n);
factoriel(BigInteger.valueOf(n));
}
static BigInteger factoriel(BigInteger n) {
if (n.compareTo(BigInteger.TWO) == 1) {
return factoriel(n.subtract(BigInteger.ONE)).multiply(n);
}
return n;
}
static long simpleLong(long n) {
if (n > 1) {
simpleLong(n-1);
}
return n;
}