Рекурсивная функция - это функция, которая вызывает сама себя. Будь то погружение в смысл жизни, задавая снова и снова «почему» (спойлер: ответ - пицца), или обход вложенных структур данных, рекурсия играет решающую роль.
Для многих итерация - это первый основной инструмент программиста в динамическом программировании. Как правило, его легче изучить, и во многих случаях итерация имеет незначительные отличия в производительности от рекурсии.
Давайте посмотрим на вычисление 4! как итеративно, так и рекурсивно.
Итеративно:
function iterativeFactorial(num) { let result = 1; for (let i = 1; i < num + 1; i++) { result *= i; } return result; } iterativeFactorial(4); => 24
Рекурсивно:
function recursiveFactorial(num) { if (num === 0) { return 1; } return num * factorial(num - 1); } recursiveFactorial(4); => 24
В таких случаях реальная выгода просто заключается в улучшении читаемости кода. В рекурсивном примере используется на одну строку кода меньше, и в нем отсутствует более запутанная логика циклов итеративного примера. Это большое дело? Возможно нет.
С другой стороны, бывают случаи, когда рекурсия почти необходима. Фактически, обычным вариантом использования является обход вложенных структур данных.
Рассмотрим приведенную ниже структуру данных с, казалось бы, неизвестным количеством вложенных массивов:
const data = [ { id: "0" }, { id: "1", children: [ { id: "1.1", children: [ { id: "1.1.1", children: [ { id: "1.1.1.1", children: [ { id: "1.1.1.1.1" }, { id: "1.1.1.1.2" }, { id: "1.1.1.1.3" } ] }, { id: "1.1.1.2" }, { id: "1.1.1.3" } ] }, { id: "1.1.2" }, { id: "1.1.3" }, ] }, { id: "1.2" }, { id: "1.3" } ] }, { id: "2" }, { id: "3" } ];
Если мы хотим собрать все значения id объектов в один массив, итерация невозможна. Пожалуйста, сдайте свой компьютер за счетами, если вы планируете вручную подсчитать степень вложенности каждого объекта. Что, если мы используем API, а приведенное выше является динамически отображаемым JSON? Нам нужно решение, которое работает динамически.
Введите рекурсию.
Рекурсивная функция, возвращающая массив всех идентификаторов, может быть:
function returnIdArr(data, result = []) { for (let i = 0; i < data.length; i++) { result.push(data[i].id); if (data[i].children) { returnIdArr(data[i].children, result); } } return result; } returnIdArr(data); => ['0', '1', '1.1', '1.1.1', '1.1.1.1', '1.1.1.1.1', '1.1.1.1.2', '1.1.1.1.3', '1.1.1.2', '1.1.1.3', '1.1.2', '1.1.3', '1.2', '1.3', '2', '3']
Функция выполняет цикл по массиву, и если какой-либо из объектов включает свойство «дочерние элементы», функция рекурсивно вызывает себя во вложенном дочернем массиве до бесконечности (или до тех пор, пока «дочерние элементы» не исчезнут). Каждый идентификатор помещается в массив результатов, который сам передается в качестве аргумента при каждом рекурсивном вызове.
Разрыв потока выполнения для первых нескольких кадров:
... // the first iteration of the loop pushes '0' into the result array result.push(data[0].id); // result = ['0'] if (data[0].children)... // false /* ------------------------------------------------ */ ... // the second iteration pushes '1' into the result array result.push(data[1].id); // result = ['0', '1'] // now true: if (data[1].children) { returnIdArr(data[1].children, ['0', '1']); /* recursively calls the function with the children and current result array as arguments */ ... /* ------------------------------------------------ */ /* the first iteration of this new loop (nested one level down) pushes '1.1' into the result array */ result.push(data[0].id); // result = ['0', '1', '1.1'] // true again: if (data[0].children)... returnIdArr(data[1].children, ['0', '1', '1.1']); // and recursion again... ...
Мы можем видеть значение рекурсии в таких случаях - наша относительно простая функция returnIdArr действует как швейцарский армейский нож, возвращающий массив id для любой версии этой структуры данных. Он эффективен, удобочитаем и динамичен.
Теперь, посмотрев на приведенные выше кадры в стеке вызовов более разборчивым взглядом, мы можем даже начать рассматривать их влияние на память. Ни один из фреймов в стеке вызовов не может выскочить до тех пор, пока не будет пройден каждый элемент в текущем массиве. Это означает, что сначала должны быть оценены все дочерние свойства в текущем массиве, а также дочерние свойства в них. Фактически, первый уровень массива, заканчивающийся объектом, свойство id которого равно «3», остается в стеке вызовов все время, пока все остальные вложенные массивы не будут полностью пройдены.
Есть ли другие способы справиться с этим?
Фактически, в этом типе прямой рекурсии есть две распространенные реализации: головная и хвостовая рекурсия.
Рекурсия головы вызывает рекурсивную функцию в начале перед другими процессами. Обычно функция определяет, что требуется рекурсия, и вызывает себя с уменьшенным параметром.
Вот некоторая (надуманная) рекурсия головы в действии:
function headCount(num) { if (num === 0) { return; } else { countDown(num - 1); } console.log(num); } count(3) // 1 // 2 // 3
Функция headCount проверяет, равен ли ее аргумент num 0. Если нет, функция рекурсивно вызывает себя с уменьшенным числом в качестве аргумента.
Следует отметить две вещи:
- Рекурсия происходит наверху или в голове функции / обработки.
- Регистрируемые числа начинаются с 1 (а не с 3) и увеличиваются.
С другой стороны, с хвостовой рекурсией все наоборот - обработка происходит до рекурсивного вызова.
Вот немного (в равной степени надуманной) хвостовой рекурсии:
function tailCount(num) { if (num === 0) { return; } else { console.log(num) } countDown(num - 1); } countDown(3) // 3 // 2 // 1
В отличие от нашей функции headCount, tailCount выводит числа, начинающиеся с 3, а затем уменьшающиеся. Чтобы это различие существовало, фреймы в соответствующих стеках вызовов должны отличаться при достижении операторов console.log.
Функция headCount должна создавать фреймы для каждого контекста выполнения из каждого рекурсивного вызова. Только после достижения базового случая, num === 0, кадры могут начать выскакивать из стека, достигая, таким образом, каждого соответствующего console.log.
С другой стороны, функция tailCount заменяет свой контекст выполнения каждым рекурсивным вызовом. Вызываемая рекурсивная функция регистрирует свой номер и не нуждается ни в каком контексте из предыдущего вызова. Из-за оптимизации хвостовых вызовов многие компиляторы гарантируют, что в стеке вызовов существует только один кадр на протяжении всего потока выполнения.
Незначительная разница в написанном коде, но огромная разница в поведении.
Изучение рекурсии сопровождается крутой кривой и, вероятно, множеством неудачных бесконечных циклов, но нюансы повышения производительности и необходимые варианты использования делают ее критически важным инструментом для любого программиста.
О, пока вы здесь, вы можете прочитать эту статью: Рекурсия: орел или решка