// --------------
// Factorial.java
// --------------

import java.math.BigInteger;

final class Factorial {
    /**
     * O(n) in space
     * O(n) in time
     * Precondition: (n >= 0)
     */
    public static long recursive (long n) {
        assert n >= 0;
        if (n < 2)
            return 1;
        return n * recursive(n - 1);}

    /**
     * O(1) in space
     * O(n) in time
     * Precondition: (n >= 0)
     */
    public static long iterative (long n) {
        assert n >= 0;
        long x = 1;
        while (n > 1) {
            x *= n;
            --n;}
        return x;}

    /**
     * O(1) in space
     * O(n) in time
     * Precondition: (n >= 0)
     */
    public static BigInteger iterative (BigInteger n) {
        assert n.compareTo(BigInteger.ZERO) >= 0;
        BigInteger x = BigInteger.ONE;
        while (n.compareTo(BigInteger.ONE) > 0) {
            x = x.multiply(n);
            n = n.subtract(BigInteger.ONE);}
        return x;}}

final class FactorialTest {
    public static void main (String[] args) {
        System.out.println("Factorial.java");

        assert Factorial.recursive(0) ==   1;
        assert Factorial.recursive(1) ==   1;
        assert Factorial.recursive(2) ==   2;
        assert Factorial.recursive(3) ==   6;
        assert Factorial.recursive(4) ==  24;
        assert Factorial.recursive(5) == 120;

        assert Factorial.iterative(0) ==   1;
        assert Factorial.iterative(1) ==   1;
        assert Factorial.iterative(2) ==   2;
        assert Factorial.iterative(3) ==   6;
        assert Factorial.iterative(4) ==  24;
        assert Factorial.iterative(5) == 120;

        assert Factorial.iterative(BigInteger.ZERO) == BigInteger.ONE;
        assert Factorial.iterative(BigInteger.ONE)  == BigInteger.ONE;
        assert Factorial.iterative(new BigInteger("2")).equals(new BigInteger("2"));
        assert Factorial.iterative(new BigInteger("3")).equals(new BigInteger("6"));
        assert Factorial.iterative(new BigInteger("4")).equals(new BigInteger("24"));
        assert Factorial.iterative(new BigInteger("5")).equals(new BigInteger("120"));

        System.out.println("Done.");}}