From Recursion to Trampolines

I've recently come across one more piece of Groovy beauty. Closures (the objects used to represent a block of code), have multiple methods, the "usual suspects" (like memoize, curry...) and also so cool stuff like trampoline.

Trampolines are a technique used to adapt a tail recursive function into an iterative one, just by turning the recursive call into a function (usually called thunk) that is returned and will be used in a loop. Well, this article in JavaScript explains it pretty good.

All the articles I've seen use trampolines for Tail recursion (this is necessary as most languages do not implement Tail Call Optimizations), but what if we have a recursive function that peforms additional actions (post actions) after the recursive call? Last year I wrote 2 posts ([1] and [2]) about preventing stack overflows in recursive functions, both for tail and non tail recursion. The technique that I use there (and that probably I'll revisit in short) had nothing to do with trampolines, but the way I saved "post actions" for executing them after the recursive calls, helped me find a technique for using trampolines with not Tail recursion

In each call to the "recursive function adapted for trampoline iteration", apart from returning a function with the next "pseudo recursive call" I return a function with the post action, that I stack up and will execute after the recursion. Well, I better copy here the code:

let st = "helloworld";

//normal recursive (non tail recursion) function
function recursiveTransformString (source){
    if (source.length === 0)
        return "";
    if (source.length === 1)
        return source.toUpperCase() + source;

    
    let curItem = source[0];
    let transformed = recursiveTransformString(source.substring(1));
    return curItem.toUpperCase() + transformed + curItem;
}

console.log(recursiveTransformString(st));
//HELLOWORLDdlrowolleh

//the above function adapted to be used in a trampoline
function transformStringAdaptedForTrampoline (source){
    if (source.length === 0)
        return [""];
    if (source.length === 1)
        return [source.toUpperCase() + source];
    
    let curItem = source[0];
    let nextRecursion = () => transformStringAdaptedForTrampoline(source.substring(1));
    let postAction = (result) => curItem.toUpperCase() + result + curItem;
    return [undefined, nextRecursion, postAction];
}

//trampoline factory
function createTrampolineWithPostAction(fn){
    return (...args) => {
        let postActions = [];
        let [result, nextRecursion, postAction] = fn(...args);
        while (result === undefined){
            postActions.push(postAction);
            [result, nextRecursion, postAction] = nextRecursion();
        }

        while(postActions.length){
            result = postActions.pop()(result);
        }
        return result;
    }
}

let trampolined = createTrampolineWithPostAction(transformStringAdaptedForTrampoline);

console.log(trampolined(st));
//HELLOWORLDdlrowolleh

As usual I've uploaded the code to a gist

For further reading, this article is another good read about trampolines.