// 第 12 周 – 阶乘的递归和迭代实现
// 运行：go run ./w12/factorial
package main

import (
	"fmt"
	"strings"
)

// fact: 0! = 1, n! = n · (n−1)!
func fact(n int) int64 {
	if n <= 1 {
		return 1 // 基本情况
	}
	return int64(n) * fact(n-1) // 递归情况
}

func factTrace(n, depth int) int64 {
	indent := strings.Repeat("  ", depth)
	fmt.Printf("%sfact(%d) called\n", indent, n)
	var r int64 = 1
	if n > 1 {
		r = int64(n) * factTrace(n-1, depth+1)
	}
	fmt.Printf("%sfact(%d) = %d\n", indent, n, r)
	return r
}

func factIter(n int) int64 {
	var r int64 = 1
	for i := 2; i <= n; i++ {
		r *= int64(i)
	}
	return r
}

func main() {
	factTrace(4, 0)
	fmt.Println()
	for _, n := range []int{0, 1, 5, 10, 20} {
		fmt.Printf("%2d! = %d (iteratively: %d)\n", n, fact(n), factIter(n))
	}
	fmt.Println("21! =", fact(21), " <- overflow!")
}