Go 语言递归函数

递归是计算机科学中一个重要的编程技术，指函数调用自身来解决问题。本章将详细介绍 Go 语言中递归函数的概念、实现和应用。

📋 递归基础概念

什么是递归

递归函数是一个调用自身的函数。递归必须包含两个要素：

基础情况（Base Case）：递归的终止条件
递归情况（Recursive Case）：函数调用自身的部分

简单递归示例

package main

import "fmt"

// 计算阶乘的递归函数
func factorial(n int) int {
    // 基础情况：递归终止条件
    if n <= 1 {
        return 1
    }
    
    // 递归情况：调用自身
    return n * factorial(n-1)
}

// 倒计时递归函数
func countdown(n int) {
    // 基础情况
    if n <= 0 {
        fmt.Println("结束!")
        return
    }
    
    // 递归情况
    fmt.Printf("%d ", n)
    countdown(n - 1)
}

func main() {
    // 阶乘示例
    fmt.Println("=== 阶乘计算 ===")
    for i := 0; i <= 5; i++ {
        result := factorial(i)
        fmt.Printf("%d! = %d\n", i, result)
    }
    
    // 倒计时示例
    fmt.Println("\n=== 倒计时 ===")
    countdown(5)
}

🔢 经典递归算法

斐波那契数列

package main

import (
    "fmt"
    "time"
)

// 基础递归实现（效率较低）
func fibonacciSimple(n int) int {
    if n <= 1 {
        return n
    }
    return fibonacciSimple(n-1) + fibonacciSimple(n-2)
}

// 记忆化递归实现（效率较高）
func fibonacciMemo(n int, memo map[int]int) int {
    if n <= 1 {
        return n
    }
    
    // 检查是否已计算过
    if val, exists := memo[n]; exists {
        return val
    }
    
    // 计算并存储结果
    memo[n] = fibonacciMemo(n-1, memo) + fibonacciMemo(n-2, memo)
    return memo[n]
}

// 包装函数，简化调用
func fibonacci(n int) int {
    memo := make(map[int]int)
    return fibonacciMemo(n, memo)
}

func main() {
    // 测试小数字
    fmt.Println("=== 斐波那契数列 ===")
    for i := 0; i <= 10; i++ {
        result := fibonacci(i)
        fmt.Printf("F(%d) = %d\n", i, result)
    }
    
    // 性能比较
    fmt.Println("\n=== 性能比较 ===")
    n := 35
    
    // 测试简单递归
    start := time.Now()
    result1 := fibonacciSimple(n)
    duration1 := time.Since(start)
    
    // 测试记忆化递归
    start = time.Now()
    result2 := fibonacci(n)
    duration2 := time.Since(start)
    
    fmt.Printf("F(%d) = %d\n", n, result1)
    fmt.Printf("简单递归耗时: %v\n", duration1)
    fmt.Printf("记忆化递归耗时: %v\n", duration2)
    fmt.Printf("性能提升: %.2fx\n", float64(duration1)/float64(duration2))
}

数字相关递归

package main

import "fmt"

// 计算数字位数
func countDigits(n int) int {
    if n < 10 {
        return 1
    }
    return 1 + countDigits(n/10)
}

// 计算数字各位之和
func sumDigits(n int) int {
    if n < 10 {
        return n
    }
    return (n % 10) + sumDigits(n/10)
}

// 反转数字
func reverseNumber(n, reversed int) int {
    if n == 0 {
        return reversed
    }
    return reverseNumber(n/10, reversed*10+n%10)
}

// 判断是否为回文数
func isPalindrome(n int) bool {
    return n == reverseNumber(n, 0)
}

// 最大公约数（欧几里得算法）
func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

// 幂运算
func power(base, exp int) int {
    if exp == 0 {
        return 1
    }
    if exp == 1 {
        return base
    }
    
    // 快速幂算法
    if exp%2 == 0 {
        half := power(base, exp/2)
        return half * half
    } else {
        return base * power(base, exp-1)
    }
}

func main() {
    numbers := []int{123, 456, 12321, 987654321}
    
    fmt.Println("=== 数字分析 ===")
    for _, num := range numbers {
        digits := countDigits(num)
        sum := sumDigits(num)
        reversed := reverseNumber(num, 0)
        palindrome := isPalindrome(num)
        
        fmt.Printf("数字: %d\n", num)
        fmt.Printf("  位数: %d\n", digits)
        fmt.Printf("  各位之和: %d\n", sum)
        fmt.Printf("  反转后: %d\n", reversed)
        fmt.Printf("  是否回文: %v\n", palindrome)
        fmt.Println()
    }
    
    // 最大公约数
    fmt.Println("=== 最大公约数 ===")
    pairs := [][2]int{{48, 18}, {100, 25}, {17, 13}}
    for _, pair := range pairs {
        result := gcd(pair[0], pair[1])
        fmt.Printf("gcd(%d, %d) = %d\n", pair[0], pair[1], result)
    }
    
    // 幂运算
    fmt.Println("\n=== 幂运算 ===")
    fmt.Printf("2^10 = %d\n", power(2, 10))
    fmt.Printf("3^5 = %d\n", power(3, 5))
    fmt.Printf("5^0 = %d\n", power(5, 0))
}

🌳 树结构递归

二叉树基础

package main

import "fmt"

// 二叉树节点
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// 创建新节点
func NewNode(val int) *TreeNode {
    return &TreeNode{Val: val}
}

// 前序遍历（根-左-右）
func preorderTraversal(root *TreeNode) {
    if root == nil {
        return
    }
    
    fmt.Printf("%d ", root.Val)
    preorderTraversal(root.Left)
    preorderTraversal(root.Right)
}

// 中序遍历（左-根-右）
func inorderTraversal(root *TreeNode) {
    if root == nil {
        return
    }
    
    inorderTraversal(root.Left)
    fmt.Printf("%d ", root.Val)
    inorderTraversal(root.Right)
}

// 后序遍历（左-右-根）
func postorderTraversal(root *TreeNode) {
    if root == nil {
        return
    }
    
    postorderTraversal(root.Left)
    postorderTraversal(root.Right)
    fmt.Printf("%d ", root.Val)
}

// 计算树的高度
func treeHeight(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    leftHeight := treeHeight(root.Left)
    rightHeight := treeHeight(root.Right)
    
    if leftHeight > rightHeight {
        return leftHeight + 1
    }
    return rightHeight + 1
}

// 计算节点总数
func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    return 1 + countNodes(root.Left) + countNodes(root.Right)
}

// 查找节点
func searchNode(root *TreeNode, target int) bool {
    if root == nil {
        return false
    }
    
    if root.Val == target {
        return true
    }
    
    return searchNode(root.Left, target) || searchNode(root.Right, target)
}

func main() {
    // 构建二叉树
    //       1
    //      / \
    //     2   3
    //    / \   \
    //   4   5   6
    
    root := NewNode(1)
    root.Left = NewNode(2)
    root.Right = NewNode(3)
    root.Left.Left = NewNode(4)
    root.Left.Right = NewNode(5)
    root.Right.Right = NewNode(6)
    
    fmt.Println("=== 二叉树遍历 ===")
    fmt.Print("前序遍历: ")
    preorderTraversal(root)
    fmt.Println()
    
    fmt.Print("中序遍历: ")
    inorderTraversal(root)
    fmt.Println()
    
    fmt.Print("后序遍历: ")
    postorderTraversal(root)
    fmt.Println()
    
    // 树的统计信息
    height := treeHeight(root)
    nodeCount := countNodes(root)
    
    fmt.Printf("\n=== 树的信息 ===\n")
    fmt.Printf("树的高度: %d\n", height)
    fmt.Printf("节点总数: %d\n", nodeCount)
    
    // 查找节点
    fmt.Println("\n=== 节点查找 ===")
    targets := []int{3, 5, 7, 1}
    for _, target := range targets {
        found := searchNode(root, target)
        fmt.Printf("查找 %d: %v\n", target, found)
    }
}

📁 文件系统递归

目录遍历模拟

package main

import (
    "fmt"
    "strings"
)

// 文件系统节点
type FileNode struct {
    Name     string
    IsDir    bool
    Size     int64
    Children []*FileNode
}

// 创建目录节点
func NewDir(name string) *FileNode {
    return &FileNode{
        Name:     name,
        IsDir:    true,
        Children: make([]*FileNode, 0),
    }
}

// 创建文件节点
func NewFile(name string, size int64) *FileNode {
    return &FileNode{
        Name:  name,
        IsDir: false,
        Size:  size,
    }
}

// 添加子节点
func (f *FileNode) AddChild(child *FileNode) {
    f.Children = append(f.Children, child)
}

// 递归计算目录大小
func calculateDirSize(node *FileNode) int64 {
    if !node.IsDir {
        return node.Size
    }
    
    var totalSize int64
    for _, child := range node.Children {
        totalSize += calculateDirSize(child)
    }
    
    return totalSize
}

// 递归打印文件树
func printFileTree(node *FileNode, prefix string, isLast bool) {
    // 打印当前节点
    connector := "├── "
    if isLast {
        connector = "└── "
    }
    
    nodeInfo := node.Name
    if node.IsDir {
        nodeInfo += "/"
    } else {
        nodeInfo += fmt.Sprintf(" (%d bytes)", node.Size)
    }
    
    fmt.Printf("%s%s%s\n", prefix, connector, nodeInfo)
    
    // 递归打印子节点
    if node.IsDir {
        newPrefix := prefix
        if isLast {
            newPrefix += "    "
        } else {
            newPrefix += "│   "
        }
        
        for i, child := range node.Children {
            isChildLast := i == len(node.Children)-1
            printFileTree(child, newPrefix, isChildLast)
        }
    }
}

// 查找文件
func findFile(node *FileNode, fileName string, path string) []string {
    var results []string
    currentPath := path + "/" + node.Name
    
    // 检查当前节点
    if strings.Contains(strings.ToLower(node.Name), strings.ToLower(fileName)) {
        results = append(results, currentPath)
    }
    
    // 递归搜索子节点
    if node.IsDir {
        for _, child := range node.Children {
            childResults := findFile(child, fileName, currentPath)
            results = append(results, childResults...)
        }
    }
    
    return results
}

// 统计文件和目录数量
func countItems(node *FileNode) (int, int) {
    if !node.IsDir {
        return 1, 0 // 1个文件，0个目录
    }
    
    fileCount, dirCount := 0, 1 // 当前是目录
    
    for _, child := range node.Children {
        childFiles, childDirs := countItems(child)
        fileCount += childFiles
        dirCount += childDirs
    }
    
    return fileCount, dirCount
}

func main() {
    // 构建文件系统树
    root := NewDir("项目根目录")
    
    // src 目录
    src := NewDir("src")
    src.AddChild(NewFile("main.go", 1024))
    src.AddChild(NewFile("utils.go", 512))
    
    // models 目录
    models := NewDir("models")
    models.AddChild(NewFile("user.go", 2048))
    models.AddChild(NewFile("product.go", 1536))
    src.AddChild(models)
    
    // docs 目录
    docs := NewDir("docs")
    docs.AddChild(NewFile("README.md", 800))
    docs.AddChild(NewFile("API.md", 1200))
    
    // 添加到根目录
    root.AddChild(src)
    root.AddChild(docs)
    root.AddChild(NewFile("go.mod", 256))
    root.AddChild(NewFile("go.sum", 180))
    
    // 打印文件树
    fmt.Println("=== 文件系统树 ===")
    printFileTree(root, "", true)
    
    // 计算目录大小
    fmt.Println("\n=== 目录大小统计 ===")
    totalSize := calculateDirSize(root)
    srcSize := calculateDirSize(src)
    docsSize := calculateDirSize(docs)
    
    fmt.Printf("总大小: %d bytes\n", totalSize)
    fmt.Printf("src目录: %d bytes\n", srcSize)
    fmt.Printf("docs目录: %d bytes\n", docsSize)
    
    // 统计文件和目录数量
    fmt.Println("\n=== 统计信息 ===")
    fileCount, dirCount := countItems(root)
    fmt.Printf("文件总数: %d\n", fileCount)
    fmt.Printf("目录总数: %d\n", dirCount)
    
    // 查找文件
    fmt.Println("\n=== 文件查找 ===")
    searchTerms := []string{"go", "md", "user"}
    for _, term := range searchTerms {
        results := findFile(root, term, "")
        fmt.Printf("搜索 '%s': %v\n", term, results)
    }
}

⚠️ 递归的注意事项

栈溢出和优化

package main

import (
    "fmt"
    "runtime"
)

// 可能导致栈溢出的递归
func dangerousRecursion(n int) int {
    fmt.Printf("当前递归深度: %d\n", n)
    
    // 检查栈使用情况
    var m runtime.MemStats
    runtime.ReadMemStats(&m)
    
    if n%1000 == 0 {
        fmt.Printf("栈大小约: %d KB\n", m.StackInuse/1024)
    }
    
    if n <= 0 {
        return 0
    }
    
    return n + dangerousRecursion(n-1)
}

// 尾递归优化模拟
func factorialTailRecursive(n, acc int) int {
    if n <= 1 {
        return acc
    }
    return factorialTailRecursive(n-1, acc*n)
}

// 迭代版本（更安全）
func factorialIterative(n int) int {
    result := 1
    for i := 1; i <= n; i++ {
        result *= i
    }
    return result
}

// 互递归示例
func isEven(n int) bool {
    if n == 0 {
        return true
    }
    return isOdd(n - 1)
}

func isOdd(n int) bool {
    if n == 0 {
        return false
    }
    return isEven(n - 1)
}

func main() {
    fmt.Println("=== 递归安全性测试 ===")
    
    // 测试安全的递归深度
    safeDepth := 100
    fmt.Printf("测试递归深度: %d\n", safeDepth)
    
    // 尾递归vs迭代比较
    n := 20
    
    tailResult := factorialTailRecursive(n, 1)
    iterResult := factorialIterative(n)
    
    fmt.Printf("\n%d! 计算结果:\n", n)
    fmt.Printf("尾递归: %d\n", tailResult)
    fmt.Printf("迭代: %d\n", iterResult)
    fmt.Printf("结果一致: %v\n", tailResult == iterResult)
    
    // 互递归示例
    fmt.Println("\n=== 互递归示例 ===")
    testNumbers := []int{0, 1, 2, 3, 4, 5}
    for _, num := range testNumbers {
        fmt.Printf("%d 是偶数: %v, 是奇数: %v\n", 
                  num, isEven(num), isOdd(num))
    }
    
    // 危险递归警告
    fmt.Println("\n=== 递归深度警告 ===")
    fmt.Println("注意：过深的递归可能导致栈溢出")
    fmt.Println("Go 默认栈大小约为 1MB")
    fmt.Println("建议递归深度不超过几千层")
    
    // 可以尝试小数值测试（注释掉避免栈溢出）
    // result := dangerousRecursion(5000) // 可能栈溢出！
}

🎯 递归应用实例

汉诺塔问题

package main

import "fmt"

// 汉诺塔移动步骤
type Move struct {
    Disk int
    From string
    To   string
}

var moves []Move

// 解决汉诺塔问题
func hanoi(n int, from, to, aux string) {
    if n == 1 {
        // 基础情况：只有一个盘子，直接移动
        move := Move{Disk: 1, From: from, To: to}
        moves = append(moves, move)
        return
    }
    
    // 步骤1：将前n-1个盘子从起始柱移到辅助柱
    hanoi(n-1, from, aux, to)
    
    // 步骤2：将最大的盘子从起始柱移到目标柱
    move := Move{Disk: n, From: from, To: to}
    moves = append(moves, move)
    
    // 步骤3：将n-1个盘子从辅助柱移到目标柱
    hanoi(n-1, aux, to, from)
}

// 打印移动步骤
func printMoves(n int) {
    fmt.Printf("=== %d层汉诺塔解法 ===\n", n)
    fmt.Printf("总共需要 %d 步\n", len(moves))
    fmt.Printf("理论最少步数: %d\n", (1<<n)-1) // 2^n - 1
    
    for i, move := range moves {
        fmt.Printf("步骤 %d: 将盘子%d从 %s 移动到 %s\n", 
                  i+1, move.Disk, move.From, move.To)
    }
}

// 组合问题：计算C(n,r)
func combination(n, r int) int {
    if r == 0 || r == n {
        return 1
    }
    if r == 1 {
        return n
    }
    
    return combination(n-1, r-1) + combination(n-1, r)
}

// 杨辉三角
func printPascalTriangle(rows int) {
    fmt.Printf("=== %d行杨辉三角 ===\n", rows)
    
    for i := 0; i < rows; i++ {
        // 打印前导空格
        for j := 0; j < rows-i-1; j++ {
            fmt.Print("  ")
        }
        
        // 打印数字
        for j := 0; j <= i; j++ {
            val := combination(i, j)
            fmt.Printf("%4d", val)
        }
        fmt.Println()
    }
}

func main() {
    // 汉诺塔问题
    n := 3
    moves = nil // 重置移动记录
    
    fmt.Printf("解决 %d 层汉诺塔问题\n", n)
    hanoi(n, "A", "C", "B")
    printMoves(n)
    
    fmt.Println()
    
    // 组合数计算
    fmt.Println("=== 组合数计算 ===")
    testCases := [][2]int{{5, 2}, {6, 3}, {8, 4}}
    for _, tc := range testCases {
        result := combination(tc[0], tc[1])
        fmt.Printf("C(%d,%d) = %d\n", tc[0], tc[1], result)
    }
    
    fmt.Println()
    
    // 杨辉三角
    printPascalTriangle(6)
}

🎓 小结

本章我们深入学习了 Go 语言的递归函数：

✅ 递归基础：基础情况和递归情况
✅ 经典算法：斐波那契、阶乘、数字处理
✅ 树结构：二叉树遍历和操作
✅ 文件系统：目录遍历和文件查找
✅ 安全性：栈溢出预防和优化技巧
✅ 实际应用：汉诺塔、组合数学问题

递归是解决复杂问题的强大工具，但需要注意性能和安全性。

接下来，我们将学习 Go 语言类型转换，掌握不同类型之间的转换方法。

递归使用建议

确保有明确的基础情况（终止条件）
注意递归深度，避免栈溢出
考虑使用记忆化优化重复计算
对于深度递归，考虑改用迭代实现

Go 语言递归函数 ​

📋 递归基础概念 ​

什么是递归 ​

简单递归示例 ​

🔢 经典递归算法 ​

斐波那契数列 ​

数字相关递归 ​

🌳 树结构递归 ​

二叉树基础 ​

📁 文件系统递归 ​

目录遍历模拟 ​

⚠️ 递归的注意事项 ​

栈溢出和优化 ​

🎯 递归应用实例 ​

汉诺塔问题 ​

🎓 小结 ​

Go 语言递归函数

📋 递归基础概念

什么是递归

简单递归示例

🔢 经典递归算法

斐波那契数列

数字相关递归

🌳 树结构递归

二叉树基础

📁 文件系统递归

目录遍历模拟

⚠️ 递归的注意事项

栈溢出和优化

🎯 递归应用实例

汉诺塔问题

🎓 小结