如何实现符合累加乘1.25逻辑的递归函数（输入int返回double）

原递归函数的问题分析 #

你写的递归函数只累加了_calc(index-1)，但根据逻辑，每个index对应的返回值需要前index-1项所有返回值的总和乘以1.25，而不是仅取前一项的结果，这是导致结果不符合预期的核心原因。

明确逻辑的数学定义 #

先把计算逻辑用数学公式明确，方便递归实现：

• ( f(1) = 1 )
• ( f(n) = (\sum_{k=1}^{n-1} f(k)) \times 1.25 )，其中 ( n \geq 2 )

递归实现方案 #

方案1：直接递归（简单但效率低）

这种写法完全贴合逻辑，但存在大量重复计算，时间复杂度为 ( O(2^n) )，仅适合小范围的index值：

double _calc(int index) {
  if (index == 1) return 1.0;
  double sum = 0.0;
  // 累加前index-1项的所有结果
  for (int i = 1; i < index; i++) {
    sum += _calc(i);
  }
  return sum * 1.25;
}

方案2：带辅助函数的高效递归（推荐）

通过辅助函数同时返回当前项的值和前n项的总和，避免重复计算，时间复杂度为 ( O(n) )，效率和你的非递归版本一致：

// 辅助函数：返回[当前项的值, 前index项的总和]
List<double> _calcHelper(int index) {
  if (index == 1) {
    return [1.0, 1.0];
  }
  // 获取前index-1项的结果与总和
  List<double> prevResult = _calcHelper(index - 1);
  // 当前项 = 前index-1项总和 × 1.25
  double current = prevResult[1] * 1.25;
  // 新总和 = 前index-1项总和 + 当前项
  double newSum = prevResult[1] + current;
  return [current, newSum];
}

// 对外调用的递归函数
double _calc(int index) {
  if (index < 1) return 0.0; // 处理非法输入
  return _calcHelper(index)[0];
}

方案3：带记忆化缓存的递归

通过缓存存储已计算的结果，避免重复计算，适合需要多次调用的场景：

List<double> _cache = [];

double _calc(int index) {
  if (index == 1) return 1.0;
  // 初始化缓存（索引0占位，对应index=0）
  if (_cache.isEmpty) {
    _cache.addAll([0.0, 1.0]);
  }
  // 缓存中已有结果直接返回
  if (index < _cache.length) {
    return _cache[index];
  }
  // 计算前index-1项的总和（利用缓存）
  double sum = 0.0;
  for (int i = 1; i < index; i++) {
    sum += _cache[i];
  }
  double current = sum * 1.25;
  _cache.add(current);
  return current;
}

结果验证 #

以几个关键值测试：

• index=1：返回1.0，正确
• index=2：返回1.25，正确
• index=3：返回2.8125（你写的2.8126是四舍五入结果），正确
• index=4：返回6.328125（与你的6.32825为四舍五入差异），正确

内容的提问来源于stack exchange，提问作者ominofelice