Skip to content

Instantly share code, notes, and snippets.

@jpenney1
Last active April 5, 2021 18:11
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 jpenney1/79e5f29f5717751467ca4e82c5c96ea1 to your computer and use it in GitHub Desktop.
Save jpenney1/79e5f29f5717751467ca4e82c5c96ea1 to your computer and use it in GitHub Desktop.
Custom efficient tail end optimization for recursive functions in JavaScript utilizing the trampoline pattern
const trampoline = fn => (...args) => {
let res = fn(...args)
while(typeof res === 'function'){
res = res()
}
return res
}
/*call trampoline with a function that returns either the resolved
value (if termination parameters are met) or the next function call
to recurse into.*/
// Exmaples / timing tests:
// TAIL END TEST FUNCTIONS
// Test 1: unnamed function declaration with return
const fibDeclRet = (n, mem=[0, 1]) => (
n === 1
? mem[1]
: function(){
return fibDeclRet(
n-1,
[mem[1], (mem[0]+mem[1])]
)
}
)
// Test 2: pure function w/ implicit return
const fibPurRet = (n, mem=[0, 1]) => (
n === 1
? mem[1]
: () => fibPurRet(
n-1,
[mem[1], (mem[0]+mem[1])]
)
)
const testFunctions = {
fibDeclRet,
fibPurRet
}
const testLabels = Object.keys(testFunctions)
const trampolineTimingTest = (fn, i, epochs=1) => {
console.log('*************************')
let counter = 0,
start, end, diff, fibCalculated
const timings = []
while(counter++ < epochs) {
start = performance.now()
fibCalculated = trampoline(fn)(5)
end = performance.now()
diff = end - start
timings.push(diff)
}
const timeTaken = timings.reduce((acc, time) => (acc + time), 0) / epochs
console.log(`Function test ${i}: ${testLabels[i]} | ${timeTaken}ms`)
}
const epochs = 10000
Object.values(testFunctions).forEach((testFn, i) => trampolineTimingTest(testFn, i, epochs))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment