Go 语言递归函数
基线条件、递归 vs 迭代、尾递归为何不被优化、记忆化。
Key Points递归必须有基线条件；Go 不做尾调用优化，深递归会爆栈。
基本形态
Go
func factorial(n int) int {
if n <= 1 { // 基线条件
return 1
}
return n * factorial(n-1) // 递归调用
}
fmt.Println(factorial(5))
fmt.Println(factorial(10))Output
120
3628800Writing recursion needs two answers: when to stop (base case) and how to shrink the problem (recursive step). Once both are clear the code is three lines.
斐波那契：从慢到快
Go
// 朴素递归：O(2^n)，n=40 就要几秒
func fibSlow(n int) int {
if n < 2 {
return n
}
return fibSlow(n-1) + fibSlow(n-2)
}
// 记忆化：O(n)
func fibMemo(n int, cache map[int]int) int {
if n < 2 {
return n
}
if v, ok := cache[n]; ok {
return v
}
r := fibMemo(n-1, cache) + fibMemo(n-2, cache)
cache[n] = r
return r
}
fmt.Println(fibSlow(10))
fmt.Println(fibMemo(50, map[int]int{}))Output
55
12586269025fibSlow(50) would take roughly 40 billion calls; the memoised version is instant. Recursion is not slow — repeated subproblems are.
递归 vs 迭代
| Aspect | Recursion | Iteration |
|---|---|---|
| 可读性 | 树、图遍历时更直观 | 线性逻辑更清楚 |
| 内存 | 每次调用压栈 | 常量空间 |
| 性能 | 有函数调用开销 | 更快 |
| 深度 | 受栈大小限制 | 几乎无限制 |
Go
// 迭代版：省栈，快一倍
func factorialIter(n int) int {
r := 1
for i := 2; i <= n; i++ {
r *= i
}
return r
}Go 不做尾递归优化
Go
// 尾递归写法，在 Scheme/Haskell 里会被优化成循环
func sumTail(n, acc int) int {
if n == 0 {
return acc
}
return sumTail(n-1, acc+n)
}
// Go 不会优化，n 很大时栈溢出
// runtime: goroutine stack exceeds 1000000000-byte limitGoroutine stacks grow dynamically (2 KB up to 1 GB), so they survive deeper recursion than C's 8 MB stack. But that is growth, not optimisation —
sumTail(10000000) still dies. Rewrite deep recursion as a loop.树遍历
Go
type Node struct {
Val int
Left, Right *Node
}
func (n *Node) InOrder(visit func(int)) {
if n == nil {
return
}
n.Left.InOrder(visit)
visit(n.Val)
n.Right.InOrder(visit)
}
root := &Node{2, &Node{1, nil, nil}, &Node{3, nil, nil}}
root.InOrder(func(v int) { fmt.Print(v, " ") })
fmt.Println()Output
1 2 3 Recursion is the natural fit for tree traversal; an iterative version needs a hand-managed stack. For problems whose structure is recursive, recursion earns its cost.
基本形态
Go
func factorial(n int) int {
if n <= 1 { // 基线条件
return 1
}
return n * factorial(n-1) // 递归调用
}
fmt.Println(factorial(5))
fmt.Println(factorial(10))Output
120
3628800写递归只需回答两个问题：什么时候停（基线条件）、怎么缩小问题规模（递归式）。两个都想清楚了，代码就是三行。
斐波那契：从慢到快
Go
// 朴素递归：O(2^n)，n=40 就要几秒
func fibSlow(n int) int {
if n < 2 {
return n
}
return fibSlow(n-1) + fibSlow(n-2)
}
// 记忆化：O(n)
func fibMemo(n int, cache map[int]int) int {
if n < 2 {
return n
}
if v, ok := cache[n]; ok {
return v
}
r := fibMemo(n-1, cache) + fibMemo(n-2, cache)
cache[n] = r
return r
}
fmt.Println(fibSlow(10))
fmt.Println(fibMemo(50, map[int]int{}))Output
55
12586269025fibSlow(50) 要算约 400 亿次，实际跑不完；记忆化版本瞬间出结果。递归本身不慢，重复子问题才慢。
递归 vs 迭代
| 对比项 | 递归 | 迭代 |
|---|---|---|
| 可读性 | 树、图遍历时更直观 | 线性逻辑更清楚 |
| 内存 | 每次调用压栈 | 常量空间 |
| 性能 | 有函数调用开销 | 更快 |
| 深度 | 受栈大小限制 | 几乎无限制 |
Go
// 迭代版：省栈，快一倍
func factorialIter(n int) int {
r := 1
for i := 2; i <= n; i++ {
r *= i
}
return r
}Go 不做尾递归优化
Go
// 尾递归写法，在 Scheme/Haskell 里会被优化成循环
func sumTail(n, acc int) int {
if n == 0 {
return acc
}
return sumTail(n-1, acc+n)
}
// Go 不会优化，n 很大时栈溢出
// runtime: goroutine stack exceeds 1000000000-byte limitGo 的 goroutine 栈会动态增长（初始 2KB，最大 1GB），所以比 C 的 8MB 栈能扛更深。但它是增长不是优化，
sumTail(10000000) 依然会崩。深递归请改写成循环。树遍历
Go
type Node struct {
Val int
Left, Right *Node
}
func (n *Node) InOrder(visit func(int)) {
if n == nil {
return
}
n.Left.InOrder(visit)
visit(n.Val)
n.Right.InOrder(visit)
}
root := &Node{2, &Node{1, nil, nil}, &Node{3, nil, nil}}
root.InOrder(func(v int) { fmt.Print(v, " ") })
fmt.Println()Output
1 2 3 树的遍历用递归是最自然的写法，改成迭代要自己维护一个栈。这类「结构本身递归」的问题，递归的代价是值得付的。