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