递归函数

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

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

基准条件(Base Case)：递归的终止条件，防止函数无限调用自身
递归条件(Recursive Case)：函数调用自身的部分，用于将问题分解为更小的子问题

语法格式：

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

func main() {
   recursion()
}

Go 语言支持递归，但使用时必须设置退出条件，否则递归会陷入无限循环导致栈溢出

递归实现阶乘

阶乘是一个正整数的乘积，表示为 n!。例如：5! = 5 * 4 * 3 * 2 * 1 = 120

package main

import "fmt"

// 递归函数计算阶乘
func factorial(n int) int {
    // 基准条件：0! 定义为 1
    if n == 0 {
        return 1
    }
    // 递归条件：n * (n-1)!，逐步分解为更小的子问题
    return n * factorial(n-1)
}

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

递归实现斐波那契数列

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

递归求平方根

牛顿迭代法：从某个猜测值 guess 开始，根据 guess 与 x 的近似度反复调整，直到差值小于精度 epsilon。

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)
}

输出：

25.00 的平方根为 5.000000

递归 vs 迭代

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

递归的优缺点

优点：

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

缺点：

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

递归的常见应用

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

对于性能敏感或可能深度递归的场景，建议考虑迭代实现或使用 channel/goroutine 等 Go 特有机制