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

Рекурсивный случай

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

1-1-2-3-5-8-13-21-34-55-89 etc...

Используя рекурсию, мы можем написать простое решение.

function fib(num){
    if (num <= 2) return 1
    return fib(num-1) + fib(num-2)
}

Это имеет смысл благодаря формуле

fib(n) = fib(n-1) + fib(n-2)

Проблема с рекурсивными решениями заключается в их пространственной и временной сложности. Каждый новый вызов добавляется в стек вызовов, и каждая функция должна ждать, пока функция не завершится. В случае с Фибоначчи все становится очень плохо из-за того, сколько вызовов помещается в стек вызовов.

На изображениях ниже показан рост рекурсивного дерева от fib(5) до fib(7).

Насколько это плохо? Что ж, пространственная и временная сложность достигает O (2 ^ n). Вложенные циклы дают вам O (n²), что довольно ужасно, но это еще хуже.

Лучший подход

При просмотре последовательности Фибоначчи становится очевидным, что мы повторяемся много раз. Взгляните еще раз на fib(7). Я обводил все время, когда вызывается один и тот же код, и его нужно вычислять снова.

Теперь лучшим подходом к решению fib(7) было бы однократное решение каждого предыдущего fib вызова. Когда поступает новый вызов для последовательности Фибоначчи, которую вы уже вычислили, просто верните значение вместо того, чтобы повторять свою работу. Такой подход называется динамическое программирование.

Реализация динамического решения

В случае с Фибоначчи мы можем обновить наше решение, чтобы использовать хранилище данных (массив или объект), которое отслеживает ранее вычисленные ответы. Наш код должен сначала проверить, вычислили ли мы уже ответ, если да, вернуть значение. Если нет, произведите вычисление, но перед тем, как вернуть ответ, сохраните решение для использования в будущем.

function memoizedFib(n, memo=[]){
    if (memo[n] !== undefined) return memo[n];
    if (n <= 2) return 1;
    let res = memoizedFib(n-1, memo) + memoizedFib(n-2, memo)
    memo[n] = res
    return res
}

Этот подход называется мемоизацией, и он значительно упрощает нашу временную сложность. Фактически, мы кэшировали ранее выполненные вызовы Фибоначчи, сохраняя их результаты в массиве. Наша временная сложность Big O улучшается с O (2 ^ n) до O (n).

Этот подход считается подходом сверху вниз, потому что мы начинаем с наивысшей ценности и продвигаемся вниз по дереву.

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

function tableFib(n){
    if (n <= 2) return 1
    let fibResult = [0,1,1]
    for (let i=3; i<=n; i++){
        fibResult[i] = fibResult[i-1] + fibResult[i-2]
    }
    return fibResult[n]
}

На изображении ниже показано, как будет работать этот процесс.

Когда использовать динамическое программирование

Динамическое программирование нельзя использовать со всеми рекурсивными решениями. Согласно определению, задача должна содержать два свойства, чтобы считаться жизнеспособной для динамического программирования:

  1. Перекрывающиеся подзадачи
  2. Оптимальная подконструкция

Что это значит? С точки зрения непрофессионала это означает следующее:

Оптимальные подзадачи означает, что один и тот же подшаблон должен повторяться. В случае Фибоначчи это будет, например, многократный вызов fib(4) в fib(7). Сортировка слиянием - это пример рекурсивной проблемы, когда есть НЕ перекрывающиеся подзадачи.

При сортировке слиянием массив разбивается посередине. Сравните каждую сторону - сторону 1 и 2. Цифры разные. Результаты будут разными. Мы не можем вычислить и сохранить для другого времени, потому что не будет другого времени, когда будут выполнены те же самые условия.

Оптимальная подструктура означает, что оптимальное решение, используемое для решения подзадачи, совпадает с решением общей проблемы. Это имеет смысл для нашей последовательности Фибоначчи, потому что суммирование меньших частей и их сложение работает так же, как попытка сложить их все сразу.

5+10+15+20 = 50
- we could also sum up it up in the following manner - 
Side 1: 5+10 = 15
Side 2: 15+20 = 35
Add Side 1 & 2: 15+35 = 50

Ниже приведен пример, в котором оптимальное решение для вспомогательного решения не работает для общего решения. Представьте, что вы пытаетесь пройти по следующему графику - построить самый длинный неповторяющийся путь между двумя узлами.

Оптимальный путь для A -> C - A -> B -> C. Оптимальный путь для C -> D - C -> B -> D. Из этого следовало бы, что оптимальным решением для A -> D было бы объединение двух ранее оптимальных решений. Это даст: A -> B -> C -> B -> D. Однако мы ищем неповторяющийся путь. На самом деле, самый длинный путь будет: A -> B -> D.