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

Question

我正在尝试实现尾递归阶乘计算器，但仍然出现堆栈溢出。谁能帮我弄清楚为什么？

我读到 Java 8 支持尾调用优化，但我想我一定没有正确实现它。
我了解到可以使用 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(WhosebugError 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，语言，不支持尾调用递归。它从来没有。它可能永远不会*。

但是，VM java 有一些功能可以让其他 non-java 语言更容易使用，但这些语言仍然可以编译成 class 文件到运行 a 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 有这样的规则，当错误发生时，你会得到一个堆栈跟踪，堆栈跟踪是一个定义明确的概念，至关重要的是，跟踪每个逻辑调用的 1 个堆栈帧。如果 TCO 存在，此无法继续。当然，有一些选择：堆栈上的每个单独的帧都可以获得 'counter'，以便堆栈跟踪在正确表示 'and this sequence of calls has recurred 8190581 times' 的同时保持较小的内存占用。它也是 lang 规范中关于它如何工作、何时启动和不启动以及这一切意味着什么的大量文本，规范中的任何其他页面永远是维护负担——这不是 'it is strictly superior to add TCO to java so when we get around to it, slam dunk, and any Pull Requests with the feature will be integrated immediately'.

此外，TCO 作为一种模式是一种做事方式，但不是唯一的方式。对于任何可以写成 TCO-recursive 应用程序的东西，将其重构为 loop-based、non-recursing 算法通常并不难。与 yield-based 异步操作相比，您当然可以重写（嘿，都是图灵机），但重写会很困难，并且生成的代码更难理解。我不想深入探讨 yield/async 风格编码的价值（或缺乏价值），只是想指出 TCO 没有 'ah, but, if TCO is a good idea, then only TCO will do'.

的外表

我没有链接 off-hand，但是对 java 的未来有相当大影响的人已经说过类似的话，例如 Brian Goetz， Mark Reinhold 等。如果您真的致力于将此添加到 java，我建议您在网络上搜索这些陈述，然后尝试形成一些专门的论据来解决他们陈述的问题。因为如果你不能说服那些人，它就永远不会发生。

那么我在 java 中做什么？

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

更新：那个博客条目怎么样？

在您链接到 this blog entry 的评论中。那是..不是 TCO。

那是使用 lambda 编写一个框架，让您或多或少地模拟 TCO，但它不是 TCO。该博客描述了一个小框架 - 因此，您需要他们粘贴的所有内容：特别是 TailCall 接口。

该代码的工作原理如下：

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

这描述了 TCO 试图完成的事情（使用不同的参数反复调用相同的函数，直到达到硬编码的边缘情况，然后反向返回），但不使用 TCO 来完成它。

因此，博客 post 说 'look, TCO in java!' 具有误导性。

就像我说的：“看，隧道墙上的画笔！”并描述了如何使用罐喷漆以看起来 像手刷一样的方式喷涂隧道壁。这很好，但称它为 'paintbrushing a wall' 会产生误导。充其量你可以说：“想在隧道中制作画笔风格的艺术品？好吧，你不能，我也无法解决这个问题，但我可以告诉你如何获得类似的结果！”。

*) 永远不要说永远，但我的意思是：目前还没有任何计划，java 平台的未来计划需要很多年才能实现，并且相当 public。我会在 'java (the language) does not have tail call recursion within 4 years' 上接受 1 到 40 的赔率，并且仍然接受那个赌注。

Answer 2

您可能会发现这很有用。我能够比您之前的尝试得到一些改进，但在这种情况下，导致 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;
}

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

Tail recursive function still blowing the stack in Java

java

tail-recursion

biginteger

factorial

说真的，java怎么没有TCO？？？

那么我在 java 中做什么？

更新：那个博客条目怎么样？