Фибоначчи на собеседовании

"Запомните этот вариант. Так делать не стоит. Не следует. Нельзя. Никогда. Это хуже, чем пинать щеночков, и сравнимо с небольшим холокостом."

Это довольно холиварное утверждение) потом вы сами описываете что существуют способы для ускорения работы рекурсии. В целом есть ряд декларативных языков программирования где кроме рекурсии и алгебраических типов нет возможности реализовать циклы. Например Haskell, и прочие некоторые функциональные языки программирования. И говоря про рекурсию это она в джс так ужасно работает. Существет определенный набор оптимизаций для ускорения работы рекурсии, мемоизация, трамплины, ленивое исполнение и тд.
Использование рекурсии не нужно избегать, для определеного типа задач больше подойдет именно рекурсия. Просто нужно знать что ты делаешь.
А вообще декларативный код vs императивный это отдельная тема холивара))

Хочу предложить еще один способ, который работает с мемоизацией. Реализован при помощи Y-комбинатора.

// condition lazy
var condL = x => tF => fF => x ? tF() : fF();

// Y combinator
var Y = f => (x => x(x))(x => y => f(x(x))(y));

// Memoized Y combinator
var Ymem = memory => F => F(x => condL(memory.has(x))(y => memory.get(x))(y => memory.set(x, Ymem(memory)(F)(x)).get(x)));

// Fib function
var fibF = f => n => n === 0 || n === 1 ? 1 : f(n - 1) + f(n - 2);

// memoized fi function
var fib = Ymem(new Map)(fibF);

console.log(fib(160))