dart - Avoiding Recursion Stackoverflow by Asynchronously Waiting-CodePudding

I'm having trouble understanding how a Fibonacci code made in DART works.

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);
}

The code only works if you keep the delayed routine (in case you want to generate 15000 sequences). If you remove the delay, an overflow error will be displayed.

I want to understand how this scenario works.

CodePudding user response：

The reason it "works" is because your method is async but you are not awaiting the implicit returned Future. That means that your current code does not really add anything to the callstack since each finobacciPOC will be running "independent" since the recursive call you are doing are never awaiting the returned Future.

Another way to see your code is the following where I have removed the await and converted it into what your code is really doing:

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);
  });
}

Here it becomes more clear that we are actually not have recursive calls on our call stack since the call to finobacciPOC will finish immediately after creating a new Future from Future.delayed which will end up making a new event on the event queue after the provided Duration of time have elapsed.

If you e.g. change your method so it now specify the returned Future and makes it so it await the recursive call:

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);
}

It will start crashing with stackoverflow errors because this change would actually mean we do have a call stack in play again.

This change would be needed if we want a given caller of finobacciPOC to know for sure when the method is done running and the listResult actually contains the result.

E.g. in your code, you don't actually know in your main when the finobacciPOC is done which also means your counting of spend time is wrong.