// 第 12 周 – 阶乘的递归和迭代实现，打印调用过程
// 运行：java Factorial.java
public class Factorial {

    // 递归定义：0! = 1,n! = n · (n−1)!
    //   Function Fact(n)
    //     If n ≤ 1 then Return 1                 // base case
    //     else Return n · Fact(n − 1)            // recursive case
    //   End function
    static long fact(int n) {
        if (n <= 1) return 1;          // 基本情况：递归在这里停止
        return n * fact(n - 1);        // 在一个更小的问题上递归调用
    }

    // 同样的算法，缩进打印调用过程：可以清楚地看到调用栈
    static long factTrace(int n, int depth) {
        String indent = "  ".repeat(depth);
        System.out.println(indent + "fact(" + n + ") called");
        long r = (n <= 1) ? 1 : n * factTrace(n - 1, depth + 1);
        System.out.println(indent + "fact(" + n + ") = " + r);
        return r;
    }

    // 迭代版本 – 结果相同，不用栈
    static long factIter(int n) {
        long r = 1;
        for (int i = 2; i <= n; i++) r *= i;
        return r;
    }

    public static void main(String[] args) {
        factTrace(4, 0);
        System.out.println();
        for (int n : new int[] { 0, 1, 5, 10, 20 })
            System.out.printf("%2d! = %,d (iteratively: %,d)%n", n, fact(n), factIter(n));
        System.out.println("21! = " + fact(21) + "  <- overflow! (long max ≈ 9.2·10^18)");
    }
}