Last active
April 5, 2021 18:11
-
-
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
This file contains hidden or 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
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