Рекурсия — это процесс, в котором функция вызывает сама себя.
Например:
function printArrayRecursive(arr, i) {
// base case, stop recurring
if (i === arr.length){
return;
}
console.log(arr[i])
// call ourself with the next index
recursive(arr, i+1)
}
В приведенном выше коде printArrayRecursive печатает один элемент из списка, а затем снова вызывает себя со следующим индексом. Каждый последующий вызов самого себя печатает следующий элемент и так далее. Рекурсия продолжается до тех пор, пока не будет достигнут базовый вариант. В нашем примере базовый случай — это когда индекс равен длине массива.
Та же самая функция выглядит несколько иначе в итеративном мире, с которым вы, вероятно, лучше знакомы:
function printArrayIterative(arr){
for (let i = 0; i < arr.length; i++){
console.log(arr[i])
}
}
В случае простой печати элементов списка итеративный подход лучше по ряду причин:
- Легче читать и понимать
- Меньшее использование памяти — Рекурсивные функции сохраняют все вызовы в стеке до тех пор, пока не будет достигнут базовый случай
- Более быстрое вычисление — рекурсивные функции требуют дополнительных затрат на вызов всей функции для каждого шага
- Если в рекурсии есть ошибка, программа, скорее всего, войдет в бесконечный цикл.
Так зачем использовать рекурсию?
Все итеративные программы могут быть написаны с использованием рекурсии, а все рекурсивные программы могут быть написаны с использованием итерации. Это связано с тем, что обе системы, если только они не ограничены реализацией, являются полными по Тьюрингу.
Основная причина выбора рекурсии вместо итерации — простота.
Много лет назад многие компиляторы и интерпретаторы не поддерживали синтаксис итерации. Циклов for просто не существовало. Это связано с тем, что гораздо проще написать интерпретатор, который может обрабатывать рекурсию, чем тот, который поддерживает циклы.
Точно так же, даже если компилятор поддерживает циклы, некоторые проблемы проще решить с помощью рекурсивной функции. Хорошим примером является обход дерева. Я часто ловлю себя на том, что пишу рекурсивные функции для поиска каждого свойства произвольного объекта JSON или просматриваю каждый файл в папке, которая может иметь бесконечное количество вложенных подпапок.
Примеры
Рекурсивно распечатать все свойства объекта JSON:
function printAllVals(obj) {
for (let k in obj) {
if (typeof obj[k] === "object") {
printAllVals(obj[k])
} else {
// base case, stop recurring
console.log(obj[k]);
}
}
}
Рекурсивно печатать все имена файлов папки, ее подпапок и их подпапок до бесконечности.
function printSubFiles(dir) {
files = fs.readdirSync(dir);
files.forEach(function (file) {
absName = `${dir}/${file}`
if (fs.statSync(absName).isDirectory()) {
printSubFiles(absName)
} else {
// base case, stop recurring
console.log(file)
}
});
};
Пытаясь понять, как рекурсивно написать функцию, подумайте:
"какой у меня базовый вариант?" или, другими словами, "что должно помешать продолжению рекурсии?"
Как только это будет выработано, остальная часть функции просто должна отвечать на вопросы,
"Что я хочу делать со своей текущей ценностью?"
и
"Как мне позвонить, чтобы перейти к следующему значению?"
Рекурсия — важный принцип, который должен понять любой программист, и я надеюсь, что это поможет вам стать немного лучше! Спасибо за чтение.
Лейн Вагнер @wagslane
Скачать Qvault: https://qvault.io
Пометьте наш Github: https://github.com/q-vault/qvault
Пост Думая о рекурсии: как рекурсивно обходить объекты JSON и файловую систему впервые появился на Qvault.