Skip to content

Instantly share code, notes, and snippets.

@XoseLluis
Created October 2, 2021 13:08
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 XoseLluis/5c1980818b3fa80cff343e0f37c8e2b2 to your computer and use it in GitHub Desktop.
Save XoseLluis/5c1980818b3fa80cff343e0f37c8e2b2 to your computer and use it in GitHub Desktop.
Trampoline factory to use with Non Tail Recursion
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment