Отказ от ответственности: этот материал был изучен Кольтом Стилом на Мастер-классе по алгоритмам JavaScript и структурам данных на Udemy, который я настоятельно рекомендую.

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

Допустим, функция вызывается с массивом, например [1, 2, 3, 4, 5], в качестве начального ввода. При использовании рекурсии при первом вызове функции она запускает свою операцию с первым элементом, 1, поскольку функция затем снова будет вызываться для меньшего фрагмента: [2, 3, 4, 5]. При получении [2, 3, 4, 5] второй вызов функции выполнит свою операцию, используя второй элемент, 2, прежде чем функция снова будет вызвана на меньшем фрагменте: [3, 4, 5]. И так далее, пока массив не станет пустым [].

Рекурсивная функция состоит из двух компонентов:

1) Базовый случай: условие, когда рекурсия заканчивается и функция перестает вызывать себя снова. Поскольку рекурсивная функция вызывает сама себя, легко написать некорректную функцию, которая завершится бесконечным циклом. Без базового случая для завершения рекурсии функция будет работать вечно (или до тех пор, пока программа не выйдет из строя / не будет остановлена).

2) Рекурсивный вызов. Рекурсивный случай - это когда функция вызывает себя - снова и снова с меньшей частью начального ввода.

Итак, как выглядит рекурсивная функция и как мы определяем базовый случай и рекурсивный вызов? Давайте возьмем что-нибудь простое, например функцию факториала, которая принимает заданное целое число и умножает это число на все целые числа под ним (факториал 3 возвращает 3 * 2 * 1 = 6). Ниже приведен пример факториала на JavaScript без использования рекурсии.

Теперь давайте посмотрим на факториал с рекурсией и определим базовый случай и рекурсивный вызов:

Рекурсивный вызов: вернуть число * факториал (число - 1). При каждом рекурсивном вызове общий продукт будет умножаться на число (num), а факториал будет вызываться снова с этим числом минус 1.

Базовый случай: if (num === 1) return 1. Функция будет выполняться до тех пор, пока число не станет равным 1, после чего мы возьмем общий продукт и умножим его на 1.

В качестве другого примера базового случая и рекурсивного вызова давайте рассмотрим функцию, которая принимает массив и возвращает его продукт (например, [3, 2, 4, 1] // = ›24):

Рекурсивный вызов: вернуть массив [0] * productOfArray (array.slice (1)). При каждом рекурсивном вызове общий продукт будет умножаться на array [0], а productOfArray будет вызываться снова с array.slice (1) - тем, что остается от массива после удаления первого элемента массива.

Базовый случай: if (array.length === 0) return 1. Функция будет работать до тех пор, пока массив не станет пустым, после чего мы возьмем общий продукт и умножим его на 1.

В качестве последнего примера давайте рассмотрим рекурсивную версию функции power, которая принимает число (основание) вместе с тем, сколько раз эта основа будет умножаться сама на себя (показатель степени). степень (основание: 5, экспонента: 3) = 5³ = 5 * 5 * 5 = 125:

Рекурсивный вызов: вернуть основание * мощность (основание, экспонента - 1). При каждом рекурсивном вызове общий продукт будет умножаться на базу, в то время как мощность будет вызываться снова с той же базой, но с ее показателем, вычтенным на 1.

Базовый случай: if (exponent === 0) return 1. Функция будет работать до тех пор, пока экспонента не станет 0, после чего мы возьмем общий продукт и умножим его на 1 - любое число до нулевой степени равно 1 (n ^ 0 = 1).

Часто проблема с рекурсивным вызовом заключается в том, чтобы определить, что входит в новый, меньший по размеру ввод для следующего вызова функции. Для целых чисел и показателей (таких как факториал и степень) вы можете просто вычесть или добавить из этого числа, пока не достигнете базового случая. Для массивов (таких как productOfArrays) используйте slice, оператор распространения или concat для создания копий исходных массивов (которые практически во всех случаях рекурсивных вызовов меньше исходного массива, пока вы не достигнете базового случая пустого массива. : []). Если у вас есть строка, вы можете использовать такие методы, как slice, substr или substring, для создания копий строк. Если у вас есть объект, вы можете делать копии с помощью Object.assign или оператора распространения.