Рекурсия

Что такое рекурсия и как её использовать?

Наши соц. сети: instagram, vk, fb, tg

Что такое рекурсия?

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

Важно отметить, что рекурсивным функциям нужен базовый случай или точка остановки, чтобы она не могла вызывать себя вечно.

Когда мы используем рекурсивные функции?

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

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

Допустим, у нас есть следующий массив длиной 8:

let array = [19, 42, 36, 11, 16, 91, 84, 2]

Допустим нам нужно разделить этот массив пополам. Используем для этого функцию сортировки слиянием:

let firstSubArray = [19, 42, 36, 11]
let secondSubArray = [16, 91, 84, 2]
 

Теперь предположим, нам нужно разделить каждый из подмассивов пополам. Нам снова нужна сортировка слиянием. И как раз тут мы можем использовать рекурсию, потому что нам нужно вызывать нашу функцию сортировки слиянием из нашей функции сортировки слиянием.

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

Как только ваша рекурсивная функция вернула n подмассивов длиной 1, сортировка слиянием сравнивает по 2 массива и объединяет их в отсортированном порядке.

[19] [42] [36] [11] [16] [91] [84] [2]
 

Учитывая вышеупомянутый набор подмассивов, сортировка слиянием сравнивает 19 и 42, 36 и 11, 16 и 91, и 84 и 2, возвращая следующее:

[19, 42] [11, 36] [16, 91] [2, 84]

Следующая сортировка слиянием сравнит первую и вторую пары массивов. Она начинается со сравнения первого элемента первого массива и первого элемента второго массива. Их значения значения 19 и 11. 11 меньше, поэтому 11 добавляется в качестве первого элемента объединенного массива. Затем 19 сравнивается с 36, вторым элементом во втором массиве. 19 меньше, поэтому он добавляется в объединенный массив. Затем сравниваются 42 и 36, меньше 36, поэтому добавляется в объединенный массив, а затем уже добавляется 42.

[11, 19, 36, 42] [16, 91] [2, 84]

То же самое происходит с двумя другими массивами. 2 меньше 16, поэтому добавляется как первый элемент их объединенного массива, 16 меньше 84, поэтому добавляется, 84 меньше 91, поэтому добавляется, а затем добавляется 91.

[11, 19, 36, 42] [2, 16, 84, 91]

Теперь у нас осталось два массива, оба из которых отсортированы, которые нам нужно объединить. 2 меньше 11, поэтому добавляется 2. 11 меньше 16, поэтому добавляется 11. 16 меньше 19, поэтому добавляется 16. 19 меньше 84, поэтому добавляется 19. 36 меньше 84, а 42 также меньше 84, поэтому добавляется 36, а затем 42. Наконец 84 и 91 добавляются.

[2, 11, 16, 19, 36, 42, 84, 91]

Такими нехитрыми алгоритмами мы можем получить отсортированный массив.

Как выглядит рекурсия в JavaScript?

Сейчас мы просто хотим сосредоточиться на рекурсии и поэтому построим только функцию деления пополам в JavaScript.

Мы будем придерживаться нашего исходного массива для этого примера. Мы начинаем с такого вот беспорядка:

let array = [19, 42, 36, 11, 16, 91, 84, 2]

И мы хотим, чтобы наша функция расставила все красиво по порядочку:

[19] [42] [36] [11] [16] [91] [84] [2]

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

function halving(array) {
let length = array.length;
let half = length / 2;
let firstSubArray = array.slice(0, half;
let secondSubArray = array.slice(half, length);
}

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

function halving(array) {
let length = array.length;
let half = length / 2;
let firstSubArray = array.slice(0, half;
let secondSubArray = array.slice(half, length);
if (firstSubArray.length === 1) {
console.log(firstSubArray)
} else {
halving(firstSubArray);
}
if (secondSubArray.length === 1) {
console.log(secondSubArray)
} else {
halving(secondSubArray);
}
}

Если вы запустите этот код, вы увидите следующий вывод на консоль:

[ 19 ]
[ 42 ]
[ 36 ]
[ 11 ]
[ 16 ]
[ 91 ]
[ 84 ]
[ 2 ]

И вот уже все по красоте отсортировано благодаря рекурсивной функции!

Источник: https://medium.com/javascript-in-plain-english/recursion-what-it-is-and-how-you-use-it-302d85e6577e