面试题：Go中闭包在简单递归场景下的行为

Question

请编写一个使用Go闭包实现的简单递归函数，用于计算斐波那契数列的第n项。并解释闭包在这个递归过程中是如何发挥作用的，以及闭包捕获的变量在递归调用过程中的变化情况。

Answer 1

package main

import "fmt"

func fibonacci() func(int) int {
    memo := make(map[int]int)
    var fib func(int) int
    fib = func(n int) int {
        if n <= 1 {
            return n
        }
        if val, ok := memo[n]; ok {
            return val
        }
        result := fib(n - 1) + fib(n - 2)
        memo[n] = result
        return result
    }
    return fib
}

你可以使用如下方式调用：

func main() {
    f := fibonacci()
    n := 10
    fmt.Printf("斐波那契数列第 %d 项的值为: %d\n", n, f(n))
}

闭包在递归过程中的作用

1. 状态保存：闭包内部的 memo 变量用于保存已经计算过的斐波那契数，避免了重复计算，大大提高了效率。这是典型的记忆化（Memoization）技术。
2. 封装逻辑：闭包将 fib 函数及其相关的状态（memo 变量）封装在一起，使得代码逻辑更加清晰，并且外部无法直接访问和修改 memo 变量，保证了数据的安全性。

闭包捕获的变量在递归调用过程中的变化情况

1. memo 变量：在递归调用过程中，memo 变量不断更新，将新计算出来的斐波那契数存入 memo 中。例如，当计算 fib(5) 时，先计算 fib(4) 和 fib(3)，并将它们的结果存入 memo，之后计算 fib(5) 时就可以直接从 memo 中获取 fib(4) 和 fib(3) 的值，而不需要再次递归计算。
2. fib 函数自身：fib 函数在闭包内定义，它通过递归调用自身来计算斐波那契数列的值。在每次递归调用时，fib 函数的参数 n 会发生变化，根据 n 的不同，计算并更新 memo 中的值。