CS1103 Exercise Unit 2 - Calculate the factorial (N) and Fibonacci (N) and save the results using BigInteger

Questions

Computes factorial(N) and fibonacci(N) for integers N entered by the user, as a demonstration of recursion. And save the results using BigInteger.

1. Codes

import java.math.BigInteger;

/**
 * Computes factorial(N) and fibonacci(N) for integers N entered by the user, as a demonstration of recursion.
 * The value of factorial(N) grows very quickly as N increases, and can be outside the limited size of values of type int
 * To solve this problem, this program use the class java.math.BigInteger,
 * which can represent integer values that can be arbitrarily large (within the limits of the computer's memory).
 */
public class FibonacciAndFactorial {

    /**
     * Main routine reads integers N from the user and prints the
     * values of factorial(N) and fibonacci(N), stopping when the
     * user inputs a zero.
     */
    public static void main(String[] args) {
        while (true) {
            System.out.print("\n\nEnter a postive integer, or -1 to end:  ");
            int N = TextIO.getlnInt();
            if (N == -1) {
                break;
            } else if (N < 0) {
                System.out.println("Negative numbers are not allowed.");
                continue;
            }
            BigInteger NasBigInteger = BigInteger.valueOf(N);
            System.out.println("\n  factorial(" + N + ") is " + factorial(NasBigInteger));
            if (N > 40) {
                System.out.println("\n  N is too big to compute fibonacci(N) recursively");
            } else {
                System.out.println("\n  fibonacci(" + N + ") is " + fibonacci(N) + "   (recursively)");
            }
            System.out.println("\n  fibonacci(" + N + ") is " + fibonacciNonrecursive(N) + "   (non-recursively)");
        }
    }


    /**
     * Compute fibonacci(N) using recursion.  Because this is so inefficient,
     * even for fairly small values of N, N should be less than or equal to 40.
     * Also, N must be greater than or equal to zero, or an infinite recursion
     * will occur.
     */
    static int fibonacci(int N) {
        assert N >= 0 : "fibonacci( n) is only defined for non-negative n";
        assert N <= 40 : "n is to large to compute fibonacci(N) recursively";
        if (N == 0 || N == 1) {
            // Base cases; the answer is 1.
            return 1;
        } else {
            // Recursive case; the answer is obtained by applying the function
            // recursively to N-1 and to N-2, and adding the two answers.
            return fibonacci(N - 1) + fibonacci(N - 2);
        }
    }


    /**
     * Compute fibonacci( N) using a for loop.  The answer is returned as
     * a BigInteger and can be very large even for fairly small values
     * of N.  N must be greater than or equal to zero.
     */
    static BigInteger fibonacciNonrecursive(int N) {
        assert N >= 0 : "fibonacci( n) is only defined for non-negative n";
        if (N == 0 || N == 1) {
            // fibonacci(0) = fibonacci(1) = 1;
            return BigInteger.ONE;
        } else {
            BigInteger f0 = BigInteger.ONE;  // In the loop, this is fibonacci(i-2)
            BigInteger f1 = BigInteger.ONE;  // In the loop, this is fibonacci(i-1)
            for (int i = 2; i <= N; i++) {
                BigInteger fi = f0.add(f1);  // Computes fibonacci(i)
                f0 = f1;  // Update to account for i++
                f1 = fi;  // Update to account for i++
            }
            return f1;  // Final value of f1 is fibonacci( N)
        }
    }


    /**
     * Compute factorial (N) using recursion.  The computation is done using
     * BigIntegers and can be very large even for fairly small values of N.
     * N must be greater than or equal to zero.
     */
    static BigInteger factorial(BigInteger N) {
        assert N.signum() >= 0 : "factorial( n) is only defined for non-negative n";
        if (N.equals(BigInteger.ZERO)) {
            // Base case; the answer is 1.
            // return new BigInteger("1");
            return BigInteger.ONE;
        } else {
            // Recursive case; the answer is obtained by applying the function
            // recursively to N-1 and multiplying the answer by N.
            BigInteger factorialOfNMinus1 = factorial(N.subtract(BigInteger.ONE));
            return N.multiply(factorialOfNMinus1);
        }
    }
}

2. Outputs

Enter a postive integer, or -1 to end:  20

  factorial(20) is 2432902008176640000

  fibonacci(20) is 10946   (recursively)

  fibonacci(20) is 10946   (non-recursively)


Enter a postive integer, or -1 to end:  -1

Process finished with exit code 0

​

---

This is the ending, thanks for reading.

---