Примеры

Вычисление факториала числа

Напишите рекурсивную функцию для вычисления факториала заданного числа. Факториал числа n (обозначается как n!) — это произведение всех положительных целых чисел от 1 до n.

function factorialExample() {
  function factorial(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) {
      result *= i;
    }
    return result;
  }

  function factorialR(n) {
    if (n === 1) {
      return 1;
    } else {
      return n * factorialR(n - 1);
    }
  }

  console.log(factorial(5));
  console.log(factorialR(5));
}

Числа Фибоначчи

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

function fiboExample() {
  function fibonacci(n) {
    if (n === 0) return 0;

    let first = 0;
    let second = 1;
    let cur = first + second;

    for (let i = 0; i < n - 1; i++) {
      cur = first + second;
      first = second;
      second = cur;
    }

    return cur;
  }

  function fibonacciR(n) {
    if (n === 0) {
      return 0; // Базовый случай: 0-е число Фибоначчи равно 0
    } else if (n === 1) {
      return 1; // Базовый случай: 1-е число Фибоначчи равно 1
    } else {
      return fibonacciR(n - 1) + fibonacciR(n - 2); // Рекурсивный вызов для вычисления
      // суммы двух предыдущих чисел Фибоначчи
    }
  }

  console.log(fibonacci(5));
  console.log(fibonacciR(5));
}

Как выглядит дерево вызовов внутри функции Фибоначчи?

При развертывании мы еще не получаем ответ Мы начинаем получать ответ, когда пойдет скрутка в обратную сторону из стека

fibonacci(7)
├─ fibonacci(6)
│  ├─ fibonacci(5)
│  │  ├─ fibonacci(4)
│  │  │  ├─ fibonacci(3)
│  │  │  │  ├─ fibonacci(2)
│  │  │  │  │  ├─ fibonacci(1) → returns 1
│  │  │  │  │  └─ fibonacci(0) → returns 0
│  │  │  │  └─ fibonacci(1) → returns 1
│  │  │  └─ fibonacci(2)
│  │  │     ├─ fibonacci(1) → returns 1
│  │  │     └─ fibonacci(0) → returns 0
│  │  └─ fibonacci(3)
│  │     ├─ fibonacci(2)
│  │     │  ├─ fibonacci(1) → returns 1
│  │     │  └─ fibonacci(0) → returns 0
│  │     └─ fibonacci(1) → returns 1
│  └─ fibonacci(4)
│     ├─ fibonacci(3)
│     │  ├─ fibonacci(2)
│     │  │  ├─ fibonacci(1) → returns 1
│     │  │  └─ fibonacci(0) → returns 0
│     │  └─ fibonacci(1) → returns 1
│     └─ fibonacci(2)
│        ├─ fibonacci(1) → returns 1
│        └─ fibonacci(0) → returns 0
└─ fibonacci(5)
├─ fibonacci(4)
│  ├─ fibonacci(3)
│  │  ├─ fibonacci(2)
│  │  │  ├─ fibonacci(1) → returns 1
│  │  │  └─ fibonacci(0) → returns 0
│  │  └─ fibonacci(1) → returns 1
│  └─ fibonacci(2)
│     ├─ fibonacci(1) → returns 1
│     └─ fibonacci(0) → returns 0
└─ fibonacci(3)
├─ fibonacci(2)
│  ├─ fibonacci(1) → returns 1
│  └─ fibonacci(0) → returns 0
└─ fibonacci(1) → returns 1

Мемоизация

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

function fibonacciMemo(n, memo = {}) {
  if (n <= 1) return n; // Базовый случай

  if (memo[n]) return memo[n]; // Проверяем, есть ли уже вычисленное значение в memo

  // Вычисляем значение и сохраняем его в memo
  memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);

  return memo[n]; // Возвращаем результат
}

console.log(fibonacciMemo(10)); // Вычисляет 55

fibonacci(7)
├─ fibonacci(6)
│  ├─ fibonacci(5)
│  │  ├─ fibonacci(4)
│  │  │  ├─ fibonacci(3)
│  │  │  │  ├─ fibonacci(2) → returns 1 (cached)
│  │  │  │  ├─ fibonacci(1) → returns 1 (cached)
│  │  │  │  └─ result → 2
│  │  │  ├─ fibonacci(2) → returns 1 (cached)
│  │  │  └─ result → 3
│  │  ├─ fibonacci(3) → returns 2 (cached)
│  │  └─ result → 5
│  ├─ fibonacci(4) → returns 3 (cached)
│  └─ result → 8
├─ fibonacci(5) → returns 5 (cached)
└─ result → 13

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

Глубокое копирование объекта

Напишите рекурсивную функцию, которая будет создавать полную копию (глубокое копирование) переданного объекта. Объект может содержать числа, строки, массивы и другие объекты.

Решение

function itemCopy(item) {
    // Проверка, если item равен null или не является объектом, возвращаем его как есть (базовый случай для рекурсии)
    if(item === null || typeof item !== 'object') {
        return item;
    }

    // Проверка, если item является массивом, выполняем глубокое копирование массива
    if(Array.isArray(item)) {
        let arr = [];
        // Проходим по всем элементам массива и рекурсивно копируем их
        for(let [index, value] of item.entries()) {
            arr[index] = itemCopy(value);
        }
        return arr; // Возвращаем новый массив
    }

    // Проверка, если item является объектом, выполняем глубокое копирование объекта
    if(item instanceof Object) {
        let obj = {};
        // Проходим по всем свойствам объекта и рекурсивно копируем их
        for(let [key, value] of Object.entries(item)) {
            obj[key] = itemCopy(value);
        }
        return obj; // Возвращаем новый объект
    }

}

function createDeepCopy(...items) {
const finalCopy = [];
// Проходим по всем переданным элементам и добавляем их глубокие копии в finalCopy
for (let i = 0; i < items.length; i++) {
finalCopy.push(itemCopy(items[i]));
}
return finalCopy; // Возвращаем массив с глубокими копиями элементов
}

console.log(createDeepCopy([2, 10, 14, 100], {'1' : 'value'}, 1));

Минусы и плюсы рекурсии

Плюсы

• Часто код с рекурсией короче и проще, чем код цикла. Это облегчает его написание и понимание другими разработчиками.
• Иногда код рекурсии можно упаковать в несколько строк, в то время как такой же цикл займёт десятки строк кода. В этом случае рекурсия будет выполняться быстрее аналогичного цикла.
• Есть алгоритмы, которые описываются рекурсией гораздо проще. Например, обход древовидных структур для сортировки.

Минусы

• Наш мозг не мыслит рекурсивно и часто нельзя выдумать такое решение без опыта работы с рекурсией.
• Нередко требует больше времени на выполнение, если число строк в рекурсии и аналогичном цикле не различается на порядки. Это может быть важно для программ, которые должны работать максимально быстро, — например, для аналитики больших объёмов данных в реальном времени.
• Может переполнить память. При каждом вызове рекурсивная функция добавляется в специальный стек, место в котором ограничено. Если вызовов окажется слишком много, память программы переполнится, что приведёт к ошибке.
• Если забыть прописать условие выхода, рекурсия будет выполняться бесконечно — программу придётся завершать принудительно.