Рекурсия — это процесс, в котором функция вызывает сама себя.

Например:

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.