4.3 Go 递归函数学习笔记

1. 递归基本概念 — 阶乘

递归函数是自己调用自己的函数。每个递归必须有两个要素：基例（停止条件）和递归步（向基例靠近）：

package main

import "fmt"

// 阶乘：n! = n * (n-1) * (n-2) * ... * 1
func factorial(n int) int {
    if n <= 1 {   // 基例：n=0 或 n=1 时返回 1（停止递归）
        return 1
    }
    return n * factorial(n-1) // 递归步：n! = n * (n-1)!
}

func main() {
    // factorial(5) 的递归展开过程：
    // 5 * factorial(4)
    // 5 * 4 * factorial(3)
    // 5 * 4 * 3 * factorial(2)
    // 5 * 4 * 3 * 2 * factorial(1)  → 基例，返回 1
    // 5 * 4 * 3 * 2 * 1 = 120
    fact5 := factorial(5)
    fmt.Println("Factorial of 5:", fact5)

    // factorial(0)：基例，直接返回 1
    fact0 := factorial(0)
    fmt.Println("Factorial of 0:", fact0)
}

执行结果：

Factorial of 5: 120
Factorial of 0: 1

要点：

• 递归 = 函数调用自身。factorial(n) 内部调用 factorial(n-1)
• 基例（base case）：if n <= 1 { return 1 } — 递归停止条件，没有基例会无限递归导致栈溢出
• 递归步（recursive step）：return n * factorial(n-1) — 每次调用向基例靠近（n 逐渐减小到 1）
• factorial(5) 的计算过程：5 → 4 → 3 → 2 → 1（基例返回1）→ 回溯计算 21=2 → 32=6 → 46=24 → 524=120
• factorial(0)：0 ≤ 1，直接走基例，返回 1（0! = 1 是数学定义）
• Go 没有尾递归优化（tail call optimization），过深的递归会导致栈溢出。深度大时应改用循环或迭代

2. 多基例递归 — 斐波那契数列

斐波那契数列有两个基例（n=0 和 n=1），递归步是两个子递归之和：

package main

import "fmt"

// 斐波那契数列：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
func fibonacci(n int) int {
    if n == 0 {   // 基例1：F(0) = 0
        return 0
    }
    if n == 1 {   // 基例2：F(1) = 1
        return 1
    }
    return fibonacci(n-1) + fibonacci(n-2) // 递归步：F(n) = F(n-1) + F(n-2)
}

func main() {
    // fibonacci(7) 的计算过程：
    // F(7) = F(6) + F(5)
    // F(6) = F(5) + F(4), F(5) = F(4) + F(3)
    // ... 逐步展开到基例 F(0)=0, F(1)=1
    // 最终：F(7) = 13
    fib7 := fibonacci(7)
    fmt.Println("7th Fibonacci number:", fib7)

    // 基例验证
    fib0 := fibonacci(0) // 基例1：返回 0
    fib1 := fibonacci(1) // 基例2：返回 1
    fmt.Println("0th Fibonacci:", fib0, "1st Fibonacci:", fib1)
}

执行结果：

7th Fibonacci number: 13
0th Fibonacci: 0 1st Fibonacci: 1

要点：

• 斐波那契有两个基例：n == 0 返回 0，n == 1 返回 1
• 递归步调用两个子递归：fibonacci(n-1) + fibonacci(n-2)
• 数列：0, 1, 1, 2, 3, 5, 8, 13, 21...（F(7) = 13）
• 性能陷阱：fibonacci 的朴素递归有大量重复计算。fibonacci(7) 会计算 fibonacci(3) 多次
• 计算复杂度是 O(2^n)，n=30 就已经很慢。优化方法：

  // 使用缓存（memoization）避免重复计算
  var memo = map[int]int{0: 0, 1: 1}
  func fibonacciMemo(n int) int {
      if v, ok := memo[n]; ok { return v }
      memo[n] = fibonacciMemo(n-1) + fibonacciMemo(n-2)
      return memo[n]
  }
  

• 或直接用循环迭代，效率更高：

  func fibonacciIter(n int) int {
      a, b := 0, 1
      for i := 0; i < n; i++ { a, b = b, a+b }
      return a
  }
  

3. 递归的副作用 — 倒计时打印

递归不仅可以用于计算返回值，还可以在递归过程中执行操作（如打印）：

package main

import "fmt"

// 倒计时：打印 n 到 1，最后打印 "Blast off!"
func countdown(n int) {
    if n == 0 {              // 基例：n=0，打印结束语
        fmt.Println("Blast off!")
        return
    }
    fmt.Println(n)           // 打印当前值
    countdown(n - 1)         // 递归调用 n-1
}

func main() {
    fmt.Println("Starting countdown:")
    countdown(5)
}

执行结果：

Starting countdown:
5
4
3
2
1
Blast off!

要点：

• 递归过程：countdown(5) → 打印 5 → countdown(4) → 打印 4 → ... → countdown(0) → 打印 "Blast off!"
• 注意 fmt.Println(n) 在 countdown(n-1) 之前，所以打印顺序是 5→4→3→2→1（递减）
• 如果交换顺序（先递归再打印），输出会变成 1→2→3→4→5（递增）：

  func countup(n int) {
      if n == 0 { return }
      countup(n - 1)      // 先递归
      fmt.Println(n)       // 递归返回后再打印
  }
  // countup(5) 输出：1, 2, 3, 4, 5
  

• 递归函数不一定需要返回值（countdown 没有返回值，只执行打印操作）
• 这种"先操作后递归"vs"先递归后操作"的区别是理解递归执行顺序的关键

知识点总结