递归函数是指一个函数在其定义中直接或间接地调用自身。递归是一种常见的算法设计思想，可以简化复杂问题的求解过程。Go 语言支持递归函数的定义和使用，但需要注意避免无限递归和堆栈溢出。

---

1. 递归函数的基本结构

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

1. 基准情况：用于终止递归调用的条件。没有基准情况的递归会导致无限循环。
2. 递归调用：通过不断调用自身来分解问题。

---

2. 示例：阶乘计算

阶乘是一个经典的递归问题，n! 定义为：

• 0! = 1
• n! = n * (n-1)! （当 n > 0）

2.1 阶乘递归实现

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
}

输出：

120

分析：

• 基准情况是 n == 0 时返回 1。
• 递归调用是 n * factorial(n-1)，将问题逐步分解为更小的子问题。

---

3. 示例：斐波那契数列

斐波那契数列也是一个经典的递归问题，定义为：

• Fib(0) = 0
• Fib(1) = 1
• Fib(n) = Fib(n-1) + Fib(n-2)（n >= 2）

3.1 斐波那契数列递归实现

package main

import "fmt"

// 递归函数计算斐波那契数列
func fibonacci(n int) int {
    if n <= 1 {
        return n  // 基准情况
    }
    return fibonacci(n-1) + fibonacci(n-2)  // 递归调用
}

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

输出：

5

分析：

• 基准情况是 n == 0 或 n == 1 时直接返回 n。
• 递归调用 fibonacci(n-1) + fibonacci(n-2)，计算斐波那契数列的每个值。

---

4. 递归的终止条件

递归函数必须包含基准情况，以确保递归能够终止。如果没有合适的基准条件，递归会导致堆栈溢出或无限循环。例如：

func infiniteRecursion() {
    infiniteRecursion()  // 没有终止条件，会导致堆栈溢出
}

这种情况会导致程序崩溃，因此在设计递归时需要特别注意终止条件。

---

5. 递归性能问题

递归函数通常会有较高的时间和空间复杂度，尤其是当递归调用较深时。在一些情况下，递归可能会非常低效，如在计算斐波那契数列时，存在大量的重复计算。

5.1 优化：尾递归

尾递归是指递归调用发生在函数的最后一步，不再进行其他计算。Go 语言不支持尾递归优化，但通过改写代码，可以避免不必要的重复计算。

5.2 示例：改写斐波那契为非递归

package main

import "fmt"

// 非递归实现斐波那契数列
func fibonacci(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
}

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

这种方式的时间复杂度为 O(n)，而递归方式的时间复杂度为 O(2^n)，所以非递归的实现更为高效。

---

6. 递归的应用

递归在很多算法中都有广泛应用，常见的应用场景包括：

• 分治算法：如归并排序、快速排序、二分查找等。
• 树的遍历：如二叉树的前序、中序、后序遍历。
• 图的遍历：深度优先搜索（DFS）等。

---

7. 总结

• 递归函数是通过自身调用自身来解决问题，具有简单的表达方式，但需要明确的终止条件。
• 基准情况是递归的终止条件，必须要有。
• 递归可能会导致性能问题，特别是在重复计算时，通常需要优化为非递归方式，或者使用记忆化技术（Memoization）来存储中间结果。
• 在设计递归算法时，需要特别注意堆栈的深度，避免堆栈溢出。

---

🔹 参考资料

• Go 官方文档 – 函数（递归）
• Go Wiki – Recursion