Created
October 2, 2021 13:08
-
-
Save XoseLluis/5c1980818b3fa80cff343e0f37c8e2b2 to your computer and use it in GitHub Desktop.
Trampoline factory to use with Non Tail Recursion
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
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