尾递归函数仍然在 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(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

我读过 JAVA 8 支持尾调用优化，但我想我一定没有正确实现它。

那你读错了。或者，您已经阅读了正确的陈述，但没有正确解释它。

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

但是，Java（VM）具有一些特性，这些特性使其他非 Java 语言更容易编译成类文件以在 Java 运行时上运行，以支持 TCO。这大概就是你读到的。

我只是在寻找有关如何使用真正的尾调用优化、lambda 表达式或我可以使用的任何建议。

用scala或类似的东西写它。

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

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

此外，TCO 作为一种模式是一种做事方式，但不是唯一的方式。对于任何可以编写为 TCO 递归应用程序的内容，将其重构为基于循环的非递归算法通常并不难。与基于收益的异步操作相比，您当然可以重写（嘿，都是图灵机），但重写会很困难，并且生成的代码更难理解。我不想深入探讨 yield/async 风格编码的价值（或缺乏价值），只是指出 TCO 没有那种“啊”的外表，但是，如果TCO 是一个好主意，那么只有 TCO 会做'。

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

那么我在java中做什么？

不要使用递归；使用while或for代替。

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

在评论中，您已链接到此博客条目。那不是 TCO。

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

该代码的工作方式如下：

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

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

因此，那篇博客文章说“看，Java 中的 TCO！” 是误导。

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

*) 永远不要说永远，但我的意思是：目前还没有任何计划，Java 平台的未来计划在未来很多年之后并且是相当公开的。我会在“java（该语言）在 4 年内没有尾调用递归”的概率为 1 到 40，并且仍然会下注。