How to make optimization for recursion?

Question

JavaScript

I'm going through a task on codewars - https://www.codewars.com/kata/58d9b332ac20339ecd00... , how to apply thunk & trampoline optimization in this case?

function thunk(fn, n, ac) {
  return fn.bind(null, n, ac);
}

const trampoline = res => {
  while (typeof res === 'function') { res = res(); }
  return res;
}

function chirp(n,string='') {
return  trampoline(n-1 && (thunk(chirp,n-1,string=string+'chirp-')) || string+'chirp')
}


chirp(9000)

Answer 1

As a recursion step, we take not the subtraction of one, but a bit shift by one to the right (dividing by 2 by 2) - so, with an increase in the recursion depth by one, one binary digit of the original value will be processed. Hence the maximum recursion depth is the binary logarithm of the original value.

X = n => n ? (n & 1 ? '-chirp' : '') + X(n >> 1) + X(n >> 1) : ''
chirp = n => X(n).slice(1)