Recursion And Trampolines

I know it's not super practical, but I think there's a reason so many people use the Fibonacci Sequence (i.e. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...) as their go-to example for recursion. It's a simple example which makes it easy to see what's going on while you're learning:

var fib = function (n) {  
    if(n === 0) return 0
    if(n === 1) return 1
    return fib(n - 1) + fib(n - 2)
}

If n is 0 or 1 we just return 0 or 1 respectively, these are our base cases. If n is 2 we return fib(1) + fib(0), which (we already know) is 1 + 0. If we want fib(3) we return fib(2) + fib(1) and so on.

So, what if we wanted fib(10000)?

RangeError: Maximum call stack size exceeded  

Every time a function is called, its context (local variables, values of parameters, etc.) is added to a call stack. But this stack has a limited size. It can only handle so many functions at a time.

When the call stack hits its limit it's called a stack overflow.

The stack size varies depending on which browser you're using or if you're running in Node or some other JavaScript engine, but at some point, you'll hit the limit. Something to keep in mind...

Unless!!!

You have or can implement something called tail recursive optimization:

var fib_tail = function (n) {  
    var inner_fib = function (n, a, b) {
        console.log(n, a, b)
        if (n == 0) return a
        if (n == 1) return b
        return inner_fib(n - 1, b, a + b)
    }
    return inner_fib(n, 0, 1)
}
console.log(fib_tail(10))  

Before I explain how this works, here's what I get when I run this code:

10 0 1  
9 1 1  
8 1 2  
7 2 3  
6 3 5  
5 5 8  
4 8 13  
3 13 21  
2 21 34  
1 34 55  
55  

For each row, the last two pair of numbers are in the fibonacci sequence. By counting down with n we can use a and b to step through the fibonacci sequence through each call until we hit 1, at which point we stop and return the value.

Writing a function this way usually takes more work and is harder to understand, so why do do it? Because if we make the last instruction in a recursive function the recursive call, the compiler doesn't need to keep its context on the call stack.

fib has to call fib(n - 1), wait for and store that result, then it has to do the same with fib(n - 2), finally it has to add those two values and return them. It needs to keep information on the call stack to do this.

With fib_tail's inner_fib, a smart compiler could see that it doesn't need to keep the current context. It can simply throw it away when it calls the function again, avoiding a stack overflow.

Eventually this feature will show up in JavaScript engines but, as far as I know, it hasn't yet. But we can implement tail call optimization ourselves.

With trampolines!!

var t = require('./trampoline.js')

var fib_tramp = function (n) {  
    var inner_fib = t.trampoline(
        function inner_fib(n, a, b) {
            if (n == 0) return t.done(a)
            if (n == 1) return t.done(b)
            return t.continue(
                () => inner_fib(n - 1, b, a + b))
        })
    return inner_fib(n, 0, 1)
}

I promise to get into the details of trampoline.js in a moment, but I wanted to explain how to use it first.

t.trampoline is a function that takes what looks like a recursive function and returns a function you can use in your code.

For t.trampoline to do its magic, you've got to do something special with your return statements. If you want to return a value (meaning you want to end the recursive loop) return t.done(value). If you want to keep the loop going return t.continue(() => recursive_call()).

Ok, here's the code for trampoline.js:

function bounce(func) {  
    var result = func.apply(
        null,
        Array.prototype.slice.call(arguments, 1))
    while (!result.done) {
        result = result.func()
    }
    return result.value
}

module.exports = {  
    done: function (value) {
        return {value: value, done: true}
    },
    continue: function (func) {
        return {func: func, done: false}
    },
    trampoline: function (func) {
        return bounce.bind(null, func)
    }
}

done returns an object that holds the final return value, and a flag telling the code that the recursive loop is finished.

continue (yeah, I should probably choose a non-keyword for this method name :) ) returns an object that holds a function we're going to call next and a flag that tells the code that the recursive loop needs to continue.

trampoline returns a curried version of bounce.

bounce is where all the action is. It gets the result of the first 'recursive' function call. Then we start a while loop that keeps checking the done flag.

If we're not done we call the function again and get the result, check the flag again, and so on until we get our final return value.

Notice that this isn't functional code. That's fine, since this isn't code you should be debugging anyway. It belongs in a library that you just use.

Another thing to notice is that the name of the function for your recursive call has to be named. Notice I don't pass an anonymous function to t.continue, I pass it a function named inner_fib. You will run into weird errors if you don't do this.

Unfortunately, last I checked lodash doesn't have a trampoline function. An extension called lodash-contrib does but it doesn't work at the moment. An interesting library called bilby.js does, but I haven't messed around with it enough to fully endorse it.

Ok, there's one more problem. It doesn't have to do with recursion or trampolines, it has to do with the size of integers in JavaScript. Here's what I get when I run fib_tramp(10000):

Infinity  

This is the JavaScript engine basically saying it can't handle numbers that big. So what do we do? Enter the big-integer module:

var big_int = require("big-integer")

var fib_tramp_big = t.trampoline(function (n) {  
    var inner_fib = function (n, a, b) {
        if (n.equals(0)) return t.done(a)
        if (n.equals(1)) return t.done(b)
        return t.continue(
            () => inner_fib(n.minus(1), b, a.plus(b)))
    }
    return inner_fib(n, big_int(0), big_int(1))
})

console.log(fib_tramp_big(big_int(10000)).toString())  

This gives us:

33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875  

I'm tempted to write a function that takes this number and puts it into scientific notation, but this post is already pretty long and...

You guys can do that yourselves right? :)

Looking for a software developer?