Рекурсивно определяем числа Фибоначчи с помощью мемоизации в JavaScript

В этой статье рассказывается о том, как определить и оперировать числами Фибоначчи с помощью рекурсии и мемоизации на JavaScript.

Я постепенно расскажу про каждый момент в этой задаче, с объяснениями и примерами кода.

P.S Очень надеюсь, что эта статья поможет явисту Ростиславу узнать, что такое мемоизация и рекурсивный ряд чисел Фибоначчи.

Фибоначчи и рекурсия

Вообще, рекурсивный подход в решении этой задачи считается плохой практикой из-за высокого runtime complexity. Это решение будет O(log n). А если представить большие числа, то сложно представить насколько тяжелой будет операция.

Давайте посмотрим на рекурсивное решение этой задачки:

const fibo = (n) => {  
  if (n < 2) {
    return n;
  }
  return fibo(n - 1) + fibo(n - 2);
};

Суть в том, что мы последовательно запускаем функцию внутри себя же, делая ряд вычислений. Но давайте разберемся, что же там происходит на самом деле. Вот визуальное представление:

Давайте взглянем на три блока слева. А именно f(2) и затем на f(1) и f(0). Тут мы находим второй элемент в ряде чисел, начинающимся с 0.

Напоминаю, ряд чисел Фибоначчи это:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 и так далее.

Тут мы отдаем fibo значение 2, так как мы хотим высчитать fibo(2). Как вы видите сверху мы видим специальное условие когда число равно 2-м и не меньше двух.

Дальше отработают следующие строчки кода:

fibo(n - 1) + fibo(n - 2)

Замените n на 2 и мы получим fibo(1) + fibo(0)

Следующим шагом будет нахождение значений двух условий, а именно fibo(0) и fibo(1). Тут для каждого случая нам придётся заново запускать метод fibo и именно в этом моменте и начинается рекурсия.

В общем, мы получаем буквально следующее:

fibo(2) = fibo(1) + fibo(0) = 1 + 0 = 1

Давайте ещё немного разберем рекурсию, но уже с fibo(3).

fibo(3) = fibo(2) + fibo(1)

Используя рекурсию мы получаем мы получаем следующее продолжение:

fibo(2) + fibo(1), где fibo(2) рекурсивно станет (fibo(1) + fibo(0)) + fibo(1), где в результате мы получим 1 + 0 + 1 = 2.

Сейчас структура древа, описанного выше должна стать для вас более понятной. Рекурсия будет происходить вплоть до конца каждой ветви пока значение не будет 1 или 0.

А теперь самое интересное. Посмотрите на количество одинаковых аргументов в этом древе. Их несколько: 4, 3, 2 и все они будут отрабатывать снова и снова при вызове рекурсии.

И тут нам на помощь приходит мемоизация.

Мемоизация

Мемоизация это имплементация сложных рекурсивных или же итеративных функций более быстрым способом. Как? Кэшируя значения отдаваемые функцией при её первоначальном запуске.

Когда мы отдаём функции мемоизации уже использованное значение, то оно отдаст готовое значение, сохраненное в кэше и не будет запускать функцию снова. К чему это приведет? К тому ускорению производительности, очевидно же. Вашему коду не надо будет пересчитывать то, что уже давно посчитано.

Круто звучит, да? Тогда давайте посмотрим на пример мемоизации, что понять его более детально:

function memo(func){
  const cache = {};
    return function(){
      const key = JSON.stringify(arguments);
      if (cache[key]){
        return cache[key];
      }
      else{
        val = func.apply(null, arguments);
        cache[key] = val;
        return val; 
      }
  }
};

Мы отдаём так называемое анонимное замыкание, которое может наследовать любую переменную или в нашем случае функцию, переданную memo. Затем мы можем смело играться с объектом аргументов этой функции.

const memoFib = memo((n) => {
    if (n < 2) {
        return n;
    }
    return memoFib(n - 1) + memoFib(n - 2);
});

Например, запустив её с memoFib(8) мы получим 21, а объект с мемоизированными значениями будет выглядеть так:

{
	  {"0":0}: 0,
	  {"0":1}: 1,
	  {"0":2}: 1,
	  {"0":3}: 2,
	  {"0":4}: 3,
	  {"0":5}: 5,
	  {"0":6}: 8,
	  {"0":7}: 13
}