3

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

  • 我读过 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();
    }
}
4

2 回答 2

9

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

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

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

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

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

用scala或类似的东西写它。

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

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

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

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

那么我在java中做什么呢？

不要使用递归；使用whileorfor代替。

更新：那个博客条目呢？

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

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

该代码的工作方式如下：

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

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

因此，该博客文章说“看，Java 中的 TCO！” 具有误导性。

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

*) 永远不要说永不，但我的意思是：没有计划在地平线上，Java 平台的未来计划在未来很多年，并且是相当公开的。对于“java（语言）在 4 年内没有尾调用递归”，我会采取 1 到 40 的赔率，但仍然会下注。

于 2020-11-06T15:33:19.293 回答
0

您可能会发现这很有用。与您之前的尝试相比，我能够得到一些改进，但在这种情况下BigInteger，导致 SO 的不是对象的大小。在我的机器上，这两种方法都会导致 n 的 Stack Overflow 介于 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;
}
于 2020-11-06T16:17:31.717 回答