Go 语言递归函数

递归是一种函数直接或间接调用自身的编程技术。

递归函数通常包含两个部分：

  1. 基准条件（Base Case）：这是递归的终止条件，防止函数无限调用自身。
  2. 递归条件（Recursive Case）：这是函数调用自身的部分，用于将问题分解为更小的子问题。

在 Go 语言中，递归的使用与其他语言类似，但需要注意 Go 的一些特性。

语法格式如下：

func recursion() {
   recursion() /* 函数调用自身 */
}

func main() {
   recursion()
}

Go 语言支持递归，但我们在使用递归时，开发者需要设置退出条件，否则递归将陷入无限循环中。

递归函数对于解决数学上的问题是非常有用的，就像计算阶乘，生成斐波那契数列等。

阶乘

阶乘是一个正整数的乘积，表示为 n!。例如：

5! = 5 * 4 * 3 * 2 * 1 = 120

以下实例通过 Go 语言的递归函数实例阶乘：

实例

package main

import "fmt"

// 递归函数计算阶乘
func factorial(n int) int {
    // 基准条件
    if n == 0 {
        return 1
    }
    // 递归条件
    return n * factorial(n-1)
}

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

代码解释

  1. 基准条件：当 n 等于 0 时，函数返回 1，因为 0! 定义为 1。
  2. 递归条件：函数返回 n 乘以 factorial(n-1) 的结果，逐步将问题分解为更小的子问题。

以上实例执行输出结果为：

120

斐波那契数列

以下实例通过 Go 语言的递归函数实现斐波那契数列：

实例

package main

import "fmt"

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

func main() {
    var i int
    for i = 0; i < 10; i++ {
       fmt.Printf("%d\t", fibonacci(i))
    }
}

以上实例执行输出结果为：

0    1    1    2    3    5    8    13    21    34

求平方根

以下实例通过 Go 语言使用递归方法实现求平方根的代码：

实例

package main

import (
        "fmt"
)

func sqrtRecursive(x, guess, prevGuess, epsilon float64) float64 {
        if diff := guess*guess - x; diff < epsilon && -diff < epsilon {
                return guess
        }

        newGuess := (guess + x/guess) / 2
        if newGuess == prevGuess {
                return guess
        }

        return sqrtRecursive(x, newGuess, guess, epsilon)
}

func sqrt(x float64) float64 {
        return sqrtRecursive(x, 1.0, 0.0, 1e-9)
}

func main() {
        x := 25.0
        result := sqrt(x)
        fmt.Printf("%.2f 的平方根为 %.6f\n", x, result)
}

以上实例中，sqrtRecursive 函数使用递归方式实现平方根的计算。

sqrtRecursive 函数接受四个参数：

  • x 表示待求平方根的数
  • guess 表示当前猜测的平方根值
  • prevGuess 表示上一次的猜测值
  • epsilon 表示精度要求（即接近平方根的程度）

递归的终止条件是当前猜测的平方根与上一次猜测的平方根非常接近，差值小于给定的精度 epsilon。

在 sqrt 函数中，我们调用 sqrtRecursive 来计算平方根，并传入初始值和精度要求，然后在 main 函数中，我们调用 sqrt 函数来求解平方根，并将结果打印出来。

执行以上代码输出结果为：

25.00 的平方根为 5.000000

递归的优缺点

优点

  • 简洁性：递归代码通常比迭代代码更简洁，易于理解。
  • 问题分解：递归天然适合解决可以分解为相似子问题的问题，如树遍历、分治算法等。

缺点

  • 性能开销：递归调用会占用栈空间，可能导致栈溢出，尤其是在深度递归时。
  • 调试困难：递归代码可能较难调试，尤其是在递归深度较大时。

递归与迭代

递归和迭代是解决问题的两种不同方法。递归通过函数调用自身来解决问题，而迭代则通过循环结构（如 for 循环）来重复执行代码块。

递归 vs 迭代

特性 递归 迭代
代码简洁性 通常更简洁 可能更冗长
性能 可能较慢，占用栈空间 通常更快，占用较少内存
适用场景 适合分解为子问题的问题 适合线性或简单重复的问题

递归的常见应用

递归在许多算法和数据结构中都有广泛应用，例如：

  • 树和图的遍历：如深度优先搜索（DFS）。
  • 分治算法：如归并排序、快速排序。
  • 动态规划：如斐波那契数列的计算。

文件目录遍历

实例

import (
    "fmt"
    "os"
    "path/filepath"
)

func walkDir(dir string, indent string) {
    entries, err := os.ReadDir(dir)
    if err != nil {
        return
    }

    for _, entry := range entries {
        fmt.Println(indent + entry.Name())
        if entry.IsDir() {
            walkDir(filepath.Join(dir, entry.Name()), indent+"  ")
        }
    }
}

func main() {
    walkDir(".", "")
}

在 Go 中使用递归时，应特别注意基线条件（终止条件）的正确性，避免无限递归。对于性能敏感或可能深度递归的场景，建议考虑迭代实现或使用 channel/goroutine 等 Go 特有机制。