Yield based Trampolines

Some weeks ago I came across this article about using trampoline functions with generators to avoid stack overflows in recursive functions. I've recently written about "classic" trampolines for non tail recursions and about an alternative, using await, so I decided to transport the technique explained in that article to a javascript example.

Let's see first an example of adapting a Tail recursive function to be used with a trampoline function to prevent stack overflows in a runtime lacking of TCO (like node.js). We have a recursive factorial like this:

function recursiveFactorial(n, accumulator) {
    if (n <= 0) return accumulator;

    return recursiveFactorial(n-1, n*accumulator);
}

And we transform it into this:

function trampolineReadyFactorial(n, accumulator){
    if (n <= 0) return accumulator;

    return () => recursiveFactorial(n-1, n*accumulator);
}

To use it with a trampoline that we create with a factory:

function createTrampoline(fn){
    return (...args) => {
        let result = fn(...args);

        while (typeof result === "function")
            result = result();
        return result;
    };
}

let factorialTrampoline = createTrampoline(trampolineReadyFactorial);
console.log("factorialTrampoline: " + factorialTrampoline(50, 1));

Now let's do it differently, let's rewrite the "trampoline enabled" recursive function, using generators as explained in that python article.

//there's no recursion cause invoking the generator function returns a generator object, and the code
//inside the generator function is not executed until we call next() on the returned generator object (iterable/iterator)
function* yieldBasedFactorial(n, accumulator){
    if (n <= 0) 
        yield accumulator;
    else
        yield yieldBasedFactorial(n-1, n*accumulator);
}

So now the "trampoline enabled" function no longer returns a function (containing the "recursive" call), but a generator object (iterable-iterator). Calling next() on that generator object will perform the next "recursive" call). We can create a trampoline for this kind of "trampoline enabled" functions, like this:

function createTrampolineFromYieldBasedFn(yieldBasedFn){
    return (...args) => {
        let genObj = yieldBasedFn(...args);
        let item = genObj.next();
        while (item.value.next !== undefined )
            item = item.value.next();
        return item.value;
    }
}

let yieldBasedFactorialTrampoline = createTrampolineFromYieldBasedFn(yieldBasedFactorial);
let result = yieldBasedFactorialTrampoline(50, 1);
console.log("yield based Trampoline 2: " + result);

The trampoline function looks more complex to me in this case, but one could say that the adapted, recursive-like function, seems more close to the original with that yield. As usual, I've uploaded the code to a gist