Как сделать оптимизацию для рекурсии?

Question

[Quintis]

Прохожу задание на codewars -https://www.codewars.com/kata/58d9b332ac20339ecd00... ,как правильно применить thunk & trampoline оптимизацию в данном случае?

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)

Comments

[Kovalsky]

В данном случае это не нужно потому что все движки умеют в оптимизацию хвостовой рекурсии.

[Quintis]

Kovalsky, почему тогда у меня выбивает stack overflow ?

[Kovalsky]

Quintis, вопрос) Может быть она у вас как-то реализована так, что наоборот не оптимизирует, а добавляет сложности. В любом случае, это не единственный способ оптимизации, к тому же в исходной задаче недопустимо использование циклов

[Quintis]

Kovalsky, А можете рассказать как еще можно оптимизировать без thunk & trampoline ?)

Answer 1

[0xD34F]

В качестве шага рекурсии возьмём не вычитание единицы, а битовый сдвиг на единицу вправо (деление на 2 нацело) - так, при увеличении глубины рекурсии на единицу, будет обрабатываться один двоичный разряд исходного значения. Отсюда максимальная глубина рекурсии - двоичный логарифм исходного значения.

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

Comments

[Quintis]

а можете обьяснить , как вам удалось без thunk & trampoline оптимизировать ?

[0xD34F]

Дополнил ответ.