巨数的阶乘不溢出堆栈但也不返回结果 (JAVA)

Question

编辑：我特别试图将此问题视为尾递归函数。使用迭代解决方案不是一种选择。

我正在尝试组装一个可以处理任何整数作为输入的阶乘计算器，只要结果小于 2^2147483647（因为我正在使用 BigInteger 来执行此操作）。

我运行遇到这样一个问题，即阶乘的结果有时仅打印为输出，即使我不相信我已经超过了堆栈的容量。对于 ~8000 以下的值，它似乎始终如一地工作（估计，每次执行都不一样......？），但间歇性地打印任何介于 ~8000 和 ~31400 之间的值（随着数字的增加，显示空白 returns 越来越频繁..?).

一次执行我得到 13947 作为堆栈溢出前处理的最高整数，另一次是 12000s。我在想至少有很多可以归因于执行期间的可变堆栈状态（因为用户输入每次都被获取并更改），但我是一个相当新的程序员，我对某些事情的理论理解可能不稳定，所以我不确定。

有谁知道为什么代码可能不打印某些高值？我最好的猜测是

该结果大于 2^2147483647，因此不能存储为 BigInteger，（但这不能解释间歇性...）
计算以某种方式花费的时间太长，并且在计算完成之前循环仍在继续（解释间歇性但似乎不可能）
即使正在进行计算，我的 Eclipse IDE 也不能很好地处理将那么多数字打印到屏幕上。

我不确定如何验证以上猜测。我已经阅读了 BigInteger 的局限性以及 Eclipse 的局限性，但没有找到任何可以与我的任务进行比较的答案。

这是代码：

package factorielRecursiveTerminale;

import java.math.BigInteger;
import java.util.Scanner; 

public class factorielRecursiveTerminale {  
static BigInteger factoriel(BigInteger n, BigInteger m) {       //calcule le factoriel pour n'importe quel entier.  
    if (n.compareTo(BigInteger.ZERO) < 1) return m;             //    théoriquement valide pour tout entier dont n! < 2^2147483647, mais 
    return factoriel(n.subtract(BigInteger.ONE), n.multiply(m));//    limité par la capacité de la pile (à cause de la récursion). 
}                                                               

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 main(String[] args) {                        //demonstration
    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 encore.\n");
        }
        }
    }
    System.out.println("Au revoir! :)\n");
  }
}

这是一些示例输出：

Calcul Factoriel

Entrer la valeur a calculer (q - quitter) : 0
Factoriel 0 -> 1

Entrer la valeur a calculer (q - quitter) : 1
Factoriel 1 -> 1

Entrer la valeur a calculer (q - quitter) : 2
Factoriel 2 -> 2

Entrer la valeur a calculer (q - quitter) : 3
Factoriel 3 -> 6

Entrer la valeur a calculer (q - quitter) : 4
Factoriel 4 -> 24

Entrer la valeur a calculer (q - quitter) : 10
Factoriel 10 -> 3628800
    
Entrer la valeur a calculer (q - quitter) : 8000
Factoriel 8000 -> 518418106.......

Entrer la valeur a calculer (q - quitter) : 9050
Factoriel 9050 -> 480838025.......

Entrer la valeur a calculer (q - quitter) : 9100
Factoriel 9100 -> 

Entrer la valeur a calculer (q - quitter) : 31400
Factoriel 31400 -> 

Entrer la valeur a calculer (q - quitter) : 31401
Depassement de la pile. Essayer encore.

Answer 1

阶乘方法工作正常，但在超过堆栈大小时确实会出现相对一致的溢出。我的计数大约是 9000-10000 次调用。请记住，对于每次递归，n 上的大值！在 BigInteger 对象中占用了相当多的 space。所以 SO 在堆栈跟踪中发生得有点早。

我建议您将值打印到文件而不是 IDE 的控制台。这样您就可以确定它是 IDE（可能）还是程序（可能不是）。我知道对于 Eclipse，必须设置控制台的内部缓冲区大小以及最大行大小。

static int count;
public static void main(String[] args) {
    count = 0;
    int n = 20000;
    BigInteger f = fact(n);
    
}
static BigInteger factoriel(BigInteger n, BigInteger m) {
    // calcule le factoriel pour n'importe quel entier.
    if (n.compareTo(BigInteger.ONE) < 1)
        return m; // théoriquement valide pour tout entier dont n! < 2^2147483647, mais
    
    count++;
    BigInteger f = null;
    try {
      f = factoriel(n.subtract(BigInteger.ONE), n.multiply(m));// limité par la capacité de la pile (à cause de la récursion).
    } catch(WhosebugError e) {
        System.out.println(count);
    }
    return f;
}
    
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);
}

Answer 2

就这么简单

public static BigInteger find(BigInteger B)
    {
        BigInteger res=BigInteger.ONE;
        int b=B.intValue();
        for(int i=1;i<=b;i++)
        {
            res=res.multiply(new BigInteger(new Integer(i).toString()));
            //System.out.println(res);
        }
        return res;
    }

Answer 3

如果你想要递归方式

public static BigInteger find(BigInteger B)
    {
        BigInteger res=BigInteger.ONE;
        if(B.compareTo(BigInteger.ZERO)==0)
            res=BigInteger.ONE;
        else
        {
            res=B.multiply(find(B.subtract(new BigInteger(new Integer(1).toString()))));
            //System.out.println(res);
        }
        return res;
    }

29.9255 秒 07:47:45 11/02/20

巨数的阶乘不溢出堆栈但也不返回结果 (JAVA)

Factorial of giant number not oveflowing stack but also not returning the result (JAVA)

java

recursion

jvm

biginteger

tail-recursion