Go 递归

Go - 递归

递归（Recursion）是一种解决问题的技术，函数通过直接或间接调用自身来解决原问题的更小实例。递归函数必须有一个或多个基础情况（Base Cases）来终止递归，以及一个递归步骤（Recursive Step）将问题规模减小直至达到基础情况。

递归函数的一般结构：

func recursiveFunction(input parameters) output_type {
    if isBaseCase(input parameters) {
        // Solve directly for the base case
        return base_case_solution
    } else {
        // Recursive step: break down the problem
        modified_input := modify(input parameters) // Move towards a base case
        partial_solution := recursiveFunction(modified_input)
        // Combine partial_solution to form the solution for the current input
        return combine(partial_solution, current_input_data)
    }
}

Go 完全支持递归函数。然而，仔细设计递归函数至关重要，以确保它们总是能达到基础情况，否则，它们将无限递归，导致栈溢出错误（因为每次函数调用都会消耗栈内存）。

示例 1：阶乘计算

非负整数 n 的阶乘（记作 n!）是所有小于等于 n 的正整数的乘积。根据定义，0! = 1。

package main

import "fmt"

// factorial calculates n!
// This function assumes n >= 0. For production code, error handling for n < 0 might be needed.
func factorial(n uint64) uint64 {
    // Base case: if n is 0 or 1, factorial is 1.
    if n <= 1 {
        return 1
    }
    // Recursive step: n * factorial(n-1)
    return n * factorial(n-1)
}

func main() {
    var num uint64

    num = 5
    fmt.Printf("Factorial of %d is %d\n", num, factorial(num)) // Output: Factorial of 5 is 120

    num = 0
    fmt.Printf("Factorial of %d is %d\n", num, factorial(num)) // Output: Factorial of 0 is 1

    // For larger numbers, ensure the type can hold the result.
    // uint64 can hold up to 20! (factorial(20)). factorial(21) will overflow uint64.
    num = 20
    fmt.Printf("Factorial of %d is %d\n", num, factorial(num))
    // Output: Factorial of 20 is 2432902008176640000
}

示例 2：斐波那契数列

斐波那契数列是一个序列，其中每个数字是前两个数字之和，通常以 0 和 1 开头：F(0) = 0，F(1) = 1，对于 n > 1，F(n) = F(n-1) + F(n-2)。

package main

import "fmt"

// fibonacci returns the n-th Fibonacci number.
// This naive recursive implementation is inefficient for larger n due to repeated computations.
func fibonacci(n int) int {
    if n <= 0 { // Base case for F(0)
        return 0
    }
    if n == 1 { // Base case for F(1)
        return 1
    }
    // Recursive step
    return fibonacci(n-1) + fibonacci(n-2)
}

func main() {
    fmt.Println("First 10 Fibonacci numbers:")
    for i := 0; i < 10; i++ {
        fmt.Printf("%d ", fibonacci(i))
    }
    fmt.Println() // Output: 0 1 1 2 3 5 8 13 21 34
}

使用递归时的注意事项

优雅性 vs 效率：对于自然递归的问题（如树遍历、快速排序、归并排序），递归可以使代码非常优雅和易读。然而，由于函数调用的开销，它通常比迭代解决方案产生更多的开销。
栈溢出：深度递归会耗尽调用栈内存，导致栈溢出错误。Go 的 goroutine 栈起始较小并可以增长，但仍然存在限制。
重复计算：一些递归算法，如简单的斐波那契示例，可能会非常低效，因为它们多次重复计算相同的子问题。使用记忆化（缓存子问题的结果）或转换为迭代式的动态规划方法可以显著提高性能。
尾调用优化 (TCO)：某些语言会将特定类型的递归（称为尾递归）优化为迭代，避免栈增长。Go 的编译器目前不保证进行 TCO，因此深度尾递归函数仍然可能导致栈溢出。

虽然 Go 有效地支持递归，但在性能关键的部分或处理可能非常深的递归时，通常最好考虑迭代替代方案，除非递归解决方案明显更清晰且深度已知有限。