递归函数 #

一、递归概述 #

递归是函数直接或间接调用自身的过程。

1.1 递归要素 #

  • 基准条件：终止递归的条件
  • 递归条件：函数调用自身

1.2 基本结构 #

go 
func recursive(n int) int {
    if n <= 0 {  // 基准条件
        return 0
    }
    return n + recursive(n-1)  // 递归条件
}

二、经典示例 #

2.1 阶乘 #

go 
func factorial(n int) int {
    if n <= 1 {
        return 1
    }
    return n * factorial(n-1)
}

fmt.Println(factorial(5))  // 120

2.2 斐波那契数列 #

go 
func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    return fibonacci(n-1) + fibonacci(n-2)
}

fmt.Println(fibonacci(10))  // 55

2.3 求和 #

go 
func sum(n int) int {
    if n <= 0 {
        return 0
    }
    return n + sum(n-1)
}

fmt.Println(sum(100))  // 5050

2.4 幂运算 #

go 
func power(x, n int) int {
    if n == 0 {
        return 1
    }
    return x * power(x, n-1)
}

fmt.Println(power(2, 10))  // 1024

三、递归应用 #

3.1 二分查找 #

go 
func binarySearch(arr []int, target, low, high int) int {
    if low > high {
        return -1
    }
    
    mid := (low + high) / 2
    
    if arr[mid] == target {
        return mid
    } else if arr[mid] > target {
        return binarySearch(arr, target, low, mid-1)
    } else {
        return binarySearch(arr, target, mid+1, high)
    }
}

arr := []int{1, 3, 5, 7, 9, 11, 13}
fmt.Println(binarySearch(arr, 7, 0, len(arr)-1))  // 3

3.2 汉诺塔 #

go 
func hanoi(n int, from, to, aux string) {
    if n == 1 {
        fmt.Printf("Move disk 1 from %s to %s\n", from, to)
        return
    }
    
    hanoi(n-1, from, aux, to)
    fmt.Printf("Move disk %d from %s to %s\n", n, from, to)
    hanoi(n-1, aux, to, from)
}

hanoi(3, "A", "C", "B")

3.3 全排列 #

go 
func permute(arr []int, start int) {
    if start == len(arr)-1 {
        fmt.Println(arr)
        return
    }
    
    for i := start; i < len(arr); i++ {
        arr[start], arr[i] = arr[i], arr[start]
        permute(arr, start+1)
        arr[start], arr[i] = arr[i], arr[start]
    }
}

permute([]int{1, 2, 3}, 0)

3.4 目录遍历 #

go 
func walkDir(path string, indent string) error {
    entries, err := os.ReadDir(path)
    if err != nil {
        return err
    }
    
    for _, entry := range entries {
        fmt.Println(indent + entry.Name())
        if entry.IsDir() {
            walkDir(filepath.Join(path, entry.Name()), indent+"  ")
        }
    }
    return nil
}

walkDir(".", "")

3.5 快速排序 #

go 
func quickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    
    pivot := arr[0]
    var left, right []int
    
    for _, v := range arr[1:] {
        if v < pivot {
            left = append(left, v)
        } else {
            right = append(right, v)
        }
    }
    
    result := append(quickSort(left), pivot)
    result = append(result, quickSort(right)...)
    return result
}

fmt.Println(quickSort([]int{3, 1, 4, 1, 5, 9, 2, 6}))

3.6 树遍历 #

go 
type TreeNode struct {
    Value int
    Left  *TreeNode
    Right *TreeNode
}

func (n *TreeNode) PreOrder() {
    if n == nil {
        return
    }
    fmt.Println(n.Value)
    n.Left.PreOrder()
    n.Right.PreOrder()
}

func (n *TreeNode) InOrder() {
    if n == nil {
        return
    }
    n.Left.InOrder()
    fmt.Println(n.Value)
    n.Right.InOrder()
}

func (n *TreeNode) PostOrder() {
    if n == nil {
        return
    }
    n.Left.PostOrder()
    n.Right.PostOrder()
    fmt.Println(n.Value)
}

四、尾递归 #

4.1 概念 #

尾递归是递归调用是函数最后一步操作的递归。

4.2 普通递归 vs 尾递归 #

普通递归：

go 
func factorial(n int) int {
    if n <= 1 {
        return 1
    }
    return n * factorial(n-1)  // 递归后还有乘法
}

尾递归：

go 
func factorialTail(n, acc int) int {
    if n <= 1 {
        return acc
    }
    return factorialTail(n-1, n*acc)  // 递归是最后操作
}

factorialTail(5, 1)  // 120

4.3 Go不支持尾递归优化 #

Go编译器不进行尾递归优化，尾递归仍会消耗栈空间。

五、递归优化 #

5.1 记忆化 #

缓存已计算结果：

go 
var memo = make(map[int]int)

func fibonacciMemo(n int) int {
    if n <= 1 {
        return n
    }
    
    if v, ok := memo[n]; ok {
        return v
    }
    
    memo[n] = fibonacciMemo(n-1) + fibonacciMemo(n-2)
    return memo[n]
}

5.2 迭代替代 #

go 
func factorialIter(n int) int {
    result := 1
    for i := 2; i <= n; i++ {
        result *= i
    }
    return result
}

func fibonacciIter(n int) int {
    if n <= 1 {
        return n
    }
    
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

5.3 限制递归深度 #

go 
func recursive(n, depth int) int {
    if depth > 1000 {
        panic("递归深度过大")
    }
    
    if n <= 0 {
        return 0
    }
    return n + recursive(n-1, depth+1)
}

六、递归陷阱 #

6.1 栈溢出 #

go 
func infinite(n int) int {
    return infinite(n + 1)  // 无基准条件，栈溢出
}

6.2 重复计算 #

go 
func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    // fibonacci(n-1) 和 fibonacci(n-2) 有大量重复计算
    return fibonacci(n-1) + fibonacci(n-2)
}

6.3 效率问题 #

递归通常比迭代慢：

go 
// 递归
func sumRecursive(n int) int {
    if n <= 0 {
        return 0
    }
    return n + sumRecursive(n-1)
}

// 迭代（更快）
func sumIterative(n int) int {
    sum := 0
    for i := 1; i <= n; i++ {
        sum += i
    }
    return sum
}

七、最佳实践 #

7.1 确保有基准条件 #

go 
func recursive(n int) int {
    if n <= 0 {  // 基准条件
        return 0
    }
    return n + recursive(n-1)
}

7.2 使用记忆化优化 #

go 
var memo = make(map[int]int)

func fib(n int) int {
    if n <= 1 {
        return n
    }
    if v, ok := memo[n]; ok {
        return v
    }
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]
}

7.3 考虑迭代替代 #

go 
// 对于简单问题，优先使用迭代
func factorial(n int) int {
    result := 1
    for i := 2; i <= n; i++ {
        result *= i
    }
    return result
}

7.4 限制递归深度 #

go 
const maxDepth = 1000

func recursive(n, depth int) int {
    if depth > maxDepth {
        return -1  // 或返回错误
    }
    // ...
}

八、总结 #

递归要点：

要素 说明
基准条件 终止递归的条件
递归条件 函数调用自身
尾递归 递归调用是最后操作
记忆化 缓存计算结果

关键点：

  1. 基准条件：必须有终止条件
  2. 栈空间：递归消耗栈空间
  3. 效率：递归可能比迭代慢
  4. 记忆化：优化重复计算
  5. 迭代替代：简单问题优先用迭代

准备好学习数组与切片了吗？让我们进入下一章！

最后更新：2026-03-26