Skip to content
JS tail recursion shim through trampolining
Find file
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.
tests
.travis.yml
Readme.md
core.js
package.json

Readme.md

tail-call

Build Status

Unfortunately does not has tail call optimization (a.k.a tail recursion), technique often used in functional languages. Recursions usually are way more expressive than imperative loops for iterative calculations and they helps avoid side-effects.

Unfortunately though lack of tail call optimization in JS makes it impossible to perform significant calculations in recursive style. Here is example demonstrating stack overflow:

var sum = function(x, y) {
  return y > 0 ? sum(x + 1, y - 1) :
         y < 0 ? sum(x - 1, y + 1) :
         x
}

sum(20, 100000) // => RangeError: Maximum call stack size exceeded

This module is provides a solution to overcome this limitation through trampolining. It's more or less a polifill for proper tail calls coming in ES.next. API is simple, it just requires wrapping of tali recursive function:

var recur = require('tail-call').recur
var sum = recur(function(x, y) {
  return y > 0 ? sum(x + 1, y - 1) :
         y < 0 ? sum(x - 1, y + 1) :
         x
})

sum(20, 100000) // => 100020

Be aware though that this will be way slower than imperative loops. There are even numbers from @jdalton.

Finally keep in mind that recur returns function that is not side-effect free and there for should be used with a great care. More precisly it should not be called from anywhere else other then itself during tail recursion. For example following code will misbehave:

var foo = recur(function(x, y) {
  // ....
  bar(x, y)
  // ...
})

var bar = function(x, y) {
  // ...
  foo(x + 1, y - 1)
  // ...
}

Don't worry, bar still can call foo but it in slightly different manner:

function f(x, y) {
  // ....
  bar(x, y)
  // ...
}

var foo = recur(f)

var bar = function(x, y) {
  // ...
  recur(f)(x + 1, y - 1)
  // ...
}

Install

npm install tail-call
Something went wrong with that request. Please try again.