A bit more on gcd by subtraction - it is easily written as a loop but I’ll use the recursive version to talk about Tail Recursion
This is gcd by recursive subtraction as written above by OP
function gcd(x, y) {
if(x === y)
return x
if(x > y)
return gcd(x - y, y)
return gcd(x, y - x)
}
We’ve seen this causes deep recursion for large |x - y| because every recursive step reduces the problem by just one multiple of the smaller number
The recursion in gcd is special because both recursive calls occur at the end of their code paths in the function - also the return value of the recursive call is immediately returned without further processing - this is an example of tail recursion
It is special because tail recursion can be implemented under the covers in a way to bypass the actual function call and eliminate the cost of increasing the call stack - this is in fact a feature of the ES6 version of javascript called Tail Call Optimization or TCO - unfortunately TCO is not yet implemented in Chrome and maybe other browsers too
With TCO and "use strict", gcd above would not cause javascript to run out of memory
Interestingly we can manually simulate TCO in javascript with a trampoline function - the idea of a trampoline is a piece of code that allows program execution to jump from one context to another - for example application programs run low-level kernel system code via trampolines
A trampoline function for recursion is one that eliminates tail recursion by calling the real function repeatedly in a loop until the base case of the recursion is reached
Here’s the trampoline replacement for recursive gcd above
function trampoline(f) {
return (...a)=>{
// call provided function on variable number of parameters
let r=f(...a)
// keep calling returned function while possible
while(r instanceof Function) {
r=r()
}
return r
}
}
function gcd_tco(x, y) {
// gcd is recursive gcd with tail recursion
// gcd returns either a number for the recursive base case or
// a function that returns the value of a single recursive call
// the single tail recursive call merges the two cases of x>y and y>x
const gcd=(x, y)=>x === y? x: ()=>gcd(Math.min(x, y), Math.abs(x-y))
// trampoline call simulates TCO
return trampoline(gcd)(x, y)
}
The gcd_tco function wraps the call to the recursive gcd function inside trampoline - there is just one true recursive call - all other calls are intercepted and run inside the loop in trampoline
gcd_tco(263340, 23) runs in the blink of an eye with no issues with the call stack
gcd is still recursive with a slight twist - it only returns a value for the base case - it returns a function that returns the value of recursive call instead for the recursive case - this is for trampoline to know when to stop simulating the recursion
This may be too much for anyone starting out with recursion in javascript - the concepts are important though