Recursion in Motoko

Developers Motoko
1

Just ramping up on Motoko and testing some language features. I wrote a function to return the n-th Fibonacci number.
Here’s the function:

func fibonacci(n: Nat): Nat {
  if (n == 0) {
    return 0;
  };
  if (n == 1) {
    return 1;
  };

  return fibonacci(n-1) + fibonacci(n-2);
};

I first tried running it in the live preview in the interactive tutorial and found it fails to return for numbers > 19. The error is: cancelled: interpreter reached step limit

So next, I tried running it from a local canister. I had to modify the code slightly to make the function async and await responses when called recursively. I was able to go beyond the 19th number but find it takes exponentially long to return a respond beyond n > 15 or so.
From these tests it appears recursion should not be used heavily?

1 Like
2

The call graph of your implementation is exponentially large, so this is to be expected.

That said, recursion through async function is not recommended even for more efficient functions, since every recursive call requires a new turn in the common case.

1 Like