Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Write stack safe non-tailrec recursive functions

Write stack safe non-tailrec recursive functions

Recrusive function is cool, but it sometimes cause stack overflow in naive implementation. I'll explain how to write any recursive functions in stack safe way.

Jun Tomioka

June 29, 2019
Tweet

More Decks by Jun Tomioka

Other Decks in Technology

Transcript

  1. Tail recursion? • Make functions tailrec to avoid StackOverflow …

    but can we? It’s… still cool I believe! FP Programmers
  2. Tail-recursion’s limitation • It tends to be difficult to convert

    recursive functions that depend on results of multiple recursive calls.
  3. Tail-recursion’s limitation • It tends to be difficult to convert

    recursive functions that depend on results of multiple recursive calls.
  4. Tail-recursion’s limitation • It tends to be difficult to convert

    recursive functions that depend on results of multiple recursive calls. Monad! FP Programmers
  5. The Monad version of recursion • This function still describes

    the problem’s structure intuitively, doesn’t it?
  6. The Monad version of recursion • This function still describes

    the problem’s structure intuitively, doesn’t it? Cool! FP Programmers
  7. The Monad version of recursion • Of course just rewriting

    the recursive function with Monad doesn’t mean it is stack safe.
  8. Trampoline • > a trampoline is a loop that iteratively

    invokes thunk-returning functions ◦ https://en.wikipedia.org/wiki/Trampoline_(computing) #High-level_programming ◦ “Trampoline” in computer science has a lot of meanings. This is just one of them.
  9. Trampoline • A trampoline loop evaluates values one by one

    until it returns final result. • We can write this evaluation loop as tailrec! Eval evaluate Eval Result OR loop
  10. Eval * We typically implement “Defer”, “Suspend” or something like

    that to avoid stack overflow when building the Eval.
  11. Eval * We typically implement “Defer”, “Suspend” or something like

    that to avoid stack overflow when building the Eval. Represents single value
  12. Eval * We typically implement “Defer”, “Suspend” or something like

    that to avoid stack overflow when building the Eval. Has following evaluation
  13. [Optional] Memoization • This is not the essence, but memoization

    to reduce running time • In many cases, we can make such “What it is” style of recursive functions faster by using memoization
  14. Let’s implement stack safe foldRight with Eval This recursive call

    of loop causes stack overflow before stack safe trampoline evaluation
  15. Recap • Recursive functions is cool especially when it describes

    ”what” rather than ”how” • We can apply the trampoline technique to avoid stack overflow when tail-recursion is not effective