dart - 通过异步等待避免递归堆栈溢出

Question

我无法理解 DART 中生成的斐波那契代码的工作原理。

void main() async {
  List<BigInt> lista = [];
  final start = DateTime.now();
  finobacciPOC(lista, BigInt.from(15000), BigInt.zero, BigInt.one);
  print('lista');
  final time_exec = start.difference(DateTime.now());
  print("Calculate in time ${time_exec}");
}

void finobacciPOC(
    List<BigInt> listResult, BigInt total, BigInt start, BigInt end) async {
  BigInt sum = start + end;

  await Future.delayed(Duration(microseconds: 1));

  listResult.add(sum);
  total = total - BigInt.one;

  if (total == BigInt.zero) {
    print(listResult);
    return;
  }

  finobacciPOC(listResult, total, end, sum);
}

仅当您保留延迟例程时（如果您想生成 15000 个序列），该代码才有效。如果删除延迟，将显示溢出错误。

我想了解这个场景是如何运作的。

Answer 1

它“有效”的原因是因为您的方法是async，但您没有等待隐式返回Future。这意味着您当前的代码并没有真正向调用堆栈添加任何内容，因为每个代码都finobacciPOC将“独立”运行，因为您正在进行的递归调用永远不会等待返回的Future.

查看代码的另一种方法如下，我已删除await并将其转换为代码实际执行的操作：

void finobacciPOC(
    List<BigInt> listResult, BigInt total, BigInt start, BigInt end) {
  BigInt sum = start + end;

  Future.delayed(Duration(microseconds: 1)).then((_) {
    listResult.add(sum);
    total = total - BigInt.one;

    if (total == BigInt.zero) {
      print(listResult);
      return;
    }

    finobacciPOC(listResult, total, end, sum);
  });
}

finobacciPOC在这里，更清楚的是，我们实际上在调用堆栈上没有递归调用，因为在创建一个新Future事件后，调用将立即Future.delayed完成，在提供的时间过去后，该调用最终将在事件队列上创建一个新事件Duration。

例如，如果您更改方法，那么它现在指定返回的 Future 并使其成为await递归调用：

Future<void> finobacciPOC(
    List<BigInt> listResult, BigInt total, BigInt start, BigInt end) async {
  BigInt sum = start + end;

  await Future.delayed(Duration(microseconds: 1));

  listResult.add(sum);
  total = total - BigInt.one;

  if (total == BigInt.zero) {
    print(listResult);
    return;
  }

  await finobacciPOC(listResult, total, end, sum);
}

它将开始因 stackoverflow 错误而崩溃，因为此更改实际上意味着我们确实再次使用了调用堆栈。

如果我们希望给定的调用者finobacciPOC确切地知道该方法何时完成运行并且listResult实际包含结果，则需要进行此更改。

例如，在您的代码中，您实际上并不知道main何时finobacciPOC完成，这也意味着您对花费时间的计算是错误的。