# Recursion in Motoko

**URL:** <https://forum.dfinity.org/t/recursion-in-motoko/25588>\
**Category:** Motoko\
**Created:** [December 15, 2023, 6:40pm UTC](https://forum.dfinity.org/t/recursion-in-motoko/25588 "2023-12-15T18:40:00Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![WarTech9](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/wartech9/32/14405_2.png) [@WarTech9](https://forum.dfinity.org/u/WarTech9)\
**Post date:** [December 15, 2023, 6:40pm UTC](https://forum.dfinity.org/t/recursion-in-motoko/25588/1 "2023-12-15T18:40:00Z")

</div>

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:

```auto
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?

---

<div class="post-metadata">

**Author:** ![rossberg](https://sea1.discourse-cdn.com/flex023/user_avatar/forum.dfinity.org/rossberg/32/795_2.png) [@rossberg](https://forum.dfinity.org/u/rossberg)\
**Post date:** [December 15, 2023, 11:34pm UTC](https://forum.dfinity.org/t/recursion-in-motoko/25588/2 "2023-12-15T23:34:31Z")

</div>

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.