Skip to content

Instantly share code, notes, and snippets.

@inmatarian
Created October 14, 2016 16:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save inmatarian/a8b0b1dcbfe3857c6807a81033ea14a0 to your computer and use it in GitHub Desktop.
Save inmatarian/a8b0b1dcbfe3857c6807a81033ea14a0 to your computer and use it in GitHub Desktop.
Proper tail recursion in javascript
// object containing the call and parameters, and optionally context
function tail_call() {
this.params = Array.prototype.slice.call(arguments);
this.fn = this.params.shift();
}
tail_call.prototype.self = function (context) {
this.that = context;
return this;
}
// wrapper that continually makes tail calls and returns final result
function tail_wrap(tc) {
var x = tc;
while (x instanceof tail_call) {
var that = this;
if (x.that != undefined) that = x.that;
x = x.fn.apply(that, x.params);
}
return x;
}
// fibonacci
function fib_tail(n, f1, f2) {
if (n == 0) {
return f1;
}
console.log(n, f1, f2);
// this is the way tail calls are performed. looks lispy now, doesn't it?
return new tail_call(fib_tail, n - 1, f2, f1 + f2);
}
// and the wrapper
console.log(tail_wrap(fib_tail(10, 1, 1)));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment