Finding the factorial using recursion with the Big

问题:

So consider the following program-segment! I've tried to use the basic recursion function to determine the factorial of a number, but now using the BigInteger class.

public static BigInteger fact(int a)
{
    BigInteger factorial = BigInteger.ONE;

    BigInteger factz = BigInteger.ONE;

    if(a == 1)
    {
        return factorial;
    }

    else
    {
        return factz.multiply(fact(a-1));
    }
}

So when I try implementing this in a program, it returns the output as 1. Is it because BigInteger objects are immutable? Or am I missing something here?

回答1:

There's an error in the code, you should put

  BigInteger factz = BigInteger.valueOf(a);

instead of BigInteger factz = BigInteger.ONE;

回答2:

The pseudocode of calculate factorial recursively looks as:

function factorial(n) {
   if (n == 0)
      return 1;
   else
      return n * factorial(n - 1);
}

Implementing it with BigInteger will be:

public static BigInteger factorial(BigInteger n) {
    if (n.equals(BigInteger.ZERO))
        return BigInteger.ONE;
    else
        return n.multiply(factorial(n.subtract(BigInteger.ONE)));
}

public static void main(String[] args) {
    System.out.println(factorial(new BigInteger("100")));
}

An output will be:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Note: recursion takes too much memory if n is large. In this case it's better to use some iterative algorithm to calculate factorial.

回答3:

I don't get the relevance of the local variables and you need to use BigInteger.valueOf(a).

Your method can be expressed in just one line:

public static BigInteger fact(int a) {
    return a == 1 ? BigInteger.ONE : BigInteger.valueOf(a).multiply(fact(a - 1));
}

回答4:

Find factorial with and without recursion of any number.

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    System.out.println("Enter no to find factorial :");
    BigInteger inputNo1 = input.nextBigInteger();
    System.out.println("With recursion    " + inputNo1 + "! Factorial = " + (factorial(inputNo1.intValue())));
    System.out.println("Without recursion " + inputNo1 + "! Factorial = " + (findFactorial(inputNo1)));
}

private static String findFactorial(BigInteger inputNo1) {
    int counter;
    BigInteger increment = new BigInteger("1");
    BigInteger fact = new BigInteger("1");
    for (counter = 1; counter <= inputNo1.longValueExact(); counter++) {
        fact = fact.multiply(increment);
        increment = increment.add(BigInteger.ONE);
    }
    return String.valueOf(fact);
}

public static BigInteger factorial(int number) {
    if (number <= 1)
        return BigInteger.ONE;
    else
        return factorial(number - 1).multiply(BigInteger.valueOf(number));
}

回答5:

My solution for finding the factorial using recursion with the BigInteger Class

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.*;
import java.util.*;

class Main {
    public static String factorial(int n,String s){
        if(n>0){
            BigInteger fact = new BigInteger(s);
            fact = fact.multiply(new BigInteger(n + ""));
            return factorial(n-1,fact.toString());
        }
        else{
            return s.toString();
        }
    }

    public static void main(String args[] ) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
            int n = Integer.parseInt(line);
            if(n==0)
            System.out.println("Factorial is 0");
            else{
            String s = factorial(n,"1");
            System.out.println("Factorial is " + s);
            }
    }
}

Output screenshot for the above code:

回答6:

Take a look at this:

 public static BigInteger fact(BigInteger a)
      {

          if(a.intValue()==1||a.intValue()==0)
          {
              return BigInteger.ONE;
          }

          else
          {
              return a.multiply(fact(a.subtract(BigInteger.ONE)));
          }
      }

The modifications are:
- Include 0!=1
- Because the function fact returns BigInteger the its argument must be BigInteger too!