第二十回：Go 递归

唐伯虎： 从前有座山，山里有座庙，庙里有个老和尚讲故事，讲的是：从前有座山...

秋香： 停！公子你再念下去，我都要晕了。这不就是递归（Recursion）吗？自己调用自己，没完没了！

🪞 第一式：镜中镜 (递归原理)

我们来看一个最简单的递归：计算阶乘（Factorial）。
5! = 5 * 4 * 3 * 2 * 1
可以理解为：5! = 5 * 4!

package main
import "fmt"

func Factorial(n int) int {
    // 🛑 1. 终止条件：如果不写这个，就会无限递归，直到栈溢出
    if n == 0 {
        return 1 
    }
    
    // 🔄 2. 递归调用：自己调用自己，但是规模变小了
    return n * Factorial(n-1) 
}

func main() {
    fmt.Println(Factorial(5)) // 输出 120
}

🥞 第二式：叠罗汉 (调用栈)

函数调用就像叠罗汉，每调用一次，就在内存的“栈”上压一层。只有最上面的人下来了（返回了），下面的人才能动。

💥 走火入魔 (栈溢出 Stack Overflow)

如果你的递归没有终止条件，或者层数太深（成千上万层），内存的栈空间就会被用光，程序直接崩溃。

func DeadLoop() {
    DeadLoop() // 没完没了，只有去没有回
}
// 运行结果：fatal error: stack overflow

🐇 第三式：兔子生兔子 (斐波那契数列)

经典的递归应用：1, 1, 2, 3, 5, 8, 13... （当前数 = 前两个数之和）

func Fib(n int) int {
    if n < 2 {
        return n
    }
    return Fib(n-1) + Fib(n-2)
}

注意： 这种写法虽然代码简单，但效率极低（重复计算太多）。如果 n 很大，唐伯虎头发白了都算不出来。实战中建议用循环或带缓存的递归。

🎯 练功房（爬楼梯）

假设你正在爬华府的高塔，一次可以爬 1 个台阶，也可以爬 2 个台阶。如果有 n 个台阶，一共有多少种爬法？

提示：
爬 1 阶：1 种 (1)
爬 2 阶：2 种 (1+1, 2)
爬 3 阶：3 种 (1+1+1, 1+2, 2+1) -> 等于 爬2阶 + 爬1阶
这是不是和斐波那契数列很像？

func ClimbStairs(n int) int {
    // 基准条件
    if n <= 2 {
        return n
    }
    // 递归公式：要么从 n-1 爬上来，要么从 n-2 爬上来
    return ClimbStairs(____) + ClimbStairs(____)
}