Created
October 14, 2016 16:07
-
-
Save inmatarian/a8b0b1dcbfe3857c6807a81033ea14a0 to your computer and use it in GitHub Desktop.
Proper tail recursion in javascript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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