如何在Dart中实现memoization？斐波那契实现栈溢出问题排查

问题原因 #

你遇到的栈溢出错误核心原因是递归缺少终止条件：

• 标准斐波那契数列的边界规则是n == 0时返回0，n == 1时返回1，你当前的代码没有对边界值做判断，递归时n会不断减小到负数，永远无法触发memo.containsKey(n)的返回逻辑，最终导致无限递归栈溢出。
• 额外的小问题：参数没有声明类型，默认的动态类型也可能带来潜在的运行时风险。

修复后的代码 #

int memoizedFibonacci(int n, {Map<int, int>? memo}) {
  // 初始化缓存
  memo ??= <int, int>{};
  // 递归终止条件：优先判断边界值
  if (n <= 1) return n;
  // 命中缓存直接返回
  if (memo.containsKey(n)) {
    return memo[n]!;
  }
  // 未命中缓存则计算后存入缓存
  memo[n] = memoizedFibonacci(n - 1, memo: memo) + memoizedFibonacci(n - 2, memo: memo);
  return memo[n]!;
}

void main() {
  print(memoizedFibonacci(10)); // 输出55
}

代码改动说明 #

• 给参数n明确指定了int类型，避免动态类型导致的异常
• 新增了递归终止条件if (n <= 1) return n，阻止无限递归
• 给缓存memo指定了泛型Map<int, int>，明确键值类型，同时用Dart的空值合并运算符??=简化了缓存初始化逻辑
• 适配Dart空安全要求，对memo[n]的取值添加了非空断言!，你也可以用memo[n] ?? 0替代进一步提升安全性

通用记忆化实现方案（可选） #

如果你需要对多个函数做记忆化，可以封装通用的高阶工具函数：

Function memoize(Function originalFunc) {
  final cache = <dynamic, dynamic>{};
  return (args) {
    if (cache.containsKey(args)) {
      return cache[args];
    }
    final result = originalFunc(args);
    cache[args] = result;
    return result;
  };
}

// 使用示例
final fib = memoize((int n) {
  if (n <= 1) return n;
  return fib(n-1) + fib(n-2);
});

void main() {
  print(fib(10)); // 输出55
}

内容的提问来源于stack exchange，提问作者Saran Kumar RS