Go 语言递归函数

递归是函数直接或间接调用自身的编程技巧，适合解决"一个问题可以拆成若干个结构相同的更小问题"的场景，比如阶乘、斐波那契、目录与树的遍历。写递归最重要的一条是必须存在终止条件：否则函数会无限调用自己，直到栈溢出程序崩溃。（说明：未给出完整 main 的片段需放入 main 函数运行）

递归的组成：终止条件 + 递归步骤

一个递归函数由两部分组成：基线条件在最小问题上直接给出答案、不再递归；递归步骤把问题规模缩小并再次调用自身。只写递归步骤、忘了基线条件是最典型的错误：

func down(n int) int {
	return down(n - 1) // 没有终止条件
}
// 运行报错：goroutine stack exceeds 1000000000-byte limit

每调用一次自身，系统就要在"调用栈"上压入一层信息，所以递归深度不是无限的。

阶乘递归完整示例

n! = n × (n-1)!，且 0! = 1，天然是递归定义。下面是完整可运行程序：

package main

import "fmt"

func factorial(n int) int {
	if n <= 1 { // 终止条件：基线
		return 1
	}
	return n * factorial(n-1) // 递归步骤：规模减 1
}

func main() {
	fmt.Println(factorial(5)) // 输出：120
	fmt.Println(factorial(3)) // 输出：6
	fmt.Println(factorial(0)) // 输出：1
}

斐波那契数列示例

斐波那契的定义 f(0)=0、f(1)=1、f(n)=f(n-1)+f(n-2)，可以直接翻译成递归：

func fib(n int) int {
	if n < 2 { // 终止条件
		return n
	}
	return fib(n-1) + fib(n-2) // 拆成两个子问题
}
// 放入 main 后调用：
// fmt.Println(fib(10)) // 输出：55

注意：这种朴素写法会重复计算大量子问题（fib(40) 已明显变慢），可用"记忆化"或循环优化。

递归执行过程简讲

以 factorial(3) 为例：程序先一路"递"下去——factorial(3) 调用 factorial(2)，factorial(2) 再调用 factorial(1)；到达基线条件后开始逐层"归"回来——factorial(1) 返回 1，于是 factorial(2)=2×1=2，最后 factorial(3)=3×2=6。所有未返回的调用都挂在调用栈上，所以递归也叫"先递后归"。

递归 vs 循环（含尾递归）

• 适用场景：递归代码简洁、贴近数学定义，适合树/图遍历、分治、回溯等"天然递归"的结构；循环适合简单线性迭代，性能更好且没有额外栈开销。
• 栈开销：每层递归占一个栈帧，深度达到几十万层就会栈溢出，循环则不会。
• 尾递归一句话：若递归调用是函数最后一个动作、结果直接返回不再参与运算，就叫尾递归，理论上可改写成循环等价形态；但 Go 目前不做尾调用优化，深层递归仍需自行改写为循环。

小结：递归是"函数调用自身"，代码简洁但要牢记终止条件；它吃调用栈，深度过大时应优先改用循环或尾递归形态。