在Java中，biginteger尾部递归函数仍在破坏堆栈

Question

我正在尝试实现一个尾部递归阶乘计算器，但仍然得到堆栈溢出。有谁能帮我找出原因吗

• 我已经读到Java8支持尾部调用优化，但我认为我一定没有正确地实现它
• 我已经读到可以使用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 Factoriel\n");
        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();
    }
}

Answer 1

I have read that JAVA 8 supports Tail call optimization, but I am thinking I must not be implementing it correctly.

那你看错了。或者，你读了一个正确的陈述，但没有正确地解释它

Java语言不支持尾部调用递归。从来没有。它可能永远不会

然而，虚拟机java有一些特性，使其他非java语言更容易编译成类文件在java运行时上运行，以支持TCO。这大概就是你读到的

I am just looking for any advice on how to get this to use real tail call optimization, lambda expressions or however I can.

用scala或类似的语言编写

说真的，java怎么没有TCO

TCO是昂贵的：Java有这样一条规则：当发生错误时，您会得到一个堆栈跟踪，而堆栈跟踪是一个定义良好的概念，至关重要的是，每个逻辑调用跟踪一个堆栈帧。如果存在TCO，则此无法继续。当然，也有一些选择：堆栈上的每个单独帧都可以获得一个“计数器”，这样堆栈跟踪在正确表示“并且该调用序列已重复8190581次”的同时，仍然保持较小的内存占用。这也是lang规范中关于它如何工作、何时起作用和不起作用以及这一切意味着什么的一大堆文本，规范中的任何附加页面都是永远的维护负担——这不是“将TCO添加到java中是绝对优越的”，所以当我们着手解决它时，扣篮，任何具有该功能的拉取请求都将立即集成”

此外，TCO作为一种模式是一种做事的方式，但它不是唯一的方式。对于任何可以编写为TCO递归应用程序的应用程序，将其重构为基于循环的非递归算法通常并不那么困难。比如说，与基于产量的异步操作不同，在异步操作中，您当然可以重写（嘿，这都是图灵机器），但是重写会很困难，并且生成的代码也很难理解。我不想讨论屈服/异步风格编码的价值（或缺乏价值），只是强调TCO没有“啊，但是，如果TCO是个好主意，那么只有TCO会做”的外表

我手头没有这些链接，但是那些对java的未来有很大影响的人已经说过这种说法，比如Brian Goetz、Mark Reinhold等。如果你真的致力于尝试将其添加到java中，我建议你在网上搜索这些陈述，然后尝试形成一些论据，专门解决它们所陈述的问题。因为如果你不能说服那些人，那就永远不会发生

那么我在java中做什么呢

不要使用递归；改用while或for

更新：那篇博文呢

在您链接到this blog entry的注释中。那是。。不是TCO

这就是使用lambdas编写一个框架，让您或多或少地模拟TCO，但它不是TCO。博客描述了一个小框架——因此，你需要他们粘贴的所有东西：特别是TailCall接口

该代码的工作原理如下：

• 您的“递归”方法根本不是递归的，它总是在不调用自身的情况下快速返回
• 它返回一个lambda，它可能会调用自己。但是，正如我们刚刚介绍的，调用您自己可以快速返回，而无需递归，并且它会返回一个函数
• 框架将执行您的函数，通常会生成一个函数（或实际结果）。它循环（因此没有递归），重复应用“调用函数。如果它返回函数，则循环。如果它返回结果，好的，这就是我们想要的结果，所以只需返回该结果”

这描述了TCO试图完成的任务（使用不同的参数反复调用同一个函数，直到达到硬编码的边缘情况，然后反向退出），但不使用TCO来完成

因此，这篇博文说“看，java中的TCO！”这是误导

就像我说的：“看，墙上的画笔！”并描述如何使用罐喷漆，以看起来像是手工刷过的方式对隧道壁进行喷漆。这很好，但称之为“刷墙画画”是一种误导。充其量你可以说：“想在隧道里制作画笔风格的艺术作品吗？你不能，我也不能解决这个问题，但我可以告诉你如何获得类似的结果！”

---

*）永远不要说“永不”之类的话，但我的意思是：没有任何计划即将出台，java平台的未来计划将持续多年，而且相当公开。我会在“java（语言）在4年内没有尾部调用递归”这一点上赌1到40个赔率，但我还是要赌一把

Answer 2

你可能会发现这很有用。与您以前的尝试相比，我能够获得一些改进，但在本例中，导致SO的原因并不是BigInteger对象的大小。在我的机器上，这两种方法都会导致n的堆栈溢出在14000和15000之间。simpleLong只是一种基本的递归方法，可以减少长的数量，但它仍然会在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;
}