Рекурсия

Время чтения: больше 15 мин

Кратко

Секция статьи "Кратко"

Рекурсия — это что-то, что описывает само себя.

Представить рекурсию проще всего на примере зеркального коридора — когда напротив друг друга стоят два зеркала. Если посмотреть в одно, то в нём будет отражение второго, во втором — отражение первого и так далее.

Кадр из фильма «Начало» Нолана

В «Начале» Нолана есть момент с зеркальным коридором, когда в отражении зеркала видно отражение зеркала, в котором видно отражение зеркала, в котором видно...

Второй пример, чуть более академически правильный — это фрактал. Тот же треугольник Серпинского — это пример рекурсии, потому что часть фигуры — это одновременно вся фигура.

Треугольник состоит из 3 точно таких же треугольников

Треугольник состоит из 3 точно таких же треугольников.

Рекурсия в программировании

Секция статьи "Рекурсия в программировании"

В программировании под рекурсией чаще всего понимают функцию, которая вызывает саму себя.

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

Например, при возведении числа в степень мы берём число, умножаем его на себя несколько раз. Эту операцию можно представить в виде:

        
          
          // 2^5 = 2 * 2 * 2 * 2 * 2//// 1 шаг: 2// 2 шаг: 2 * 2// 3 шаг: 2 * 2 * 2// 4 шаг: 2 * 2 * 2 * 2// 5 шаг: 2 * 2 * 2 * 2 * 2//// Какой по счёту шаг —// столько и умножений.
          // 2^5 = 2 * 2 * 2 * 2 * 2
//
// 1 шаг: 2
// 2 шаг: 2 * 2
// 3 шаг: 2 * 2 * 2
// 4 шаг: 2 * 2 * 2 * 2
// 5 шаг: 2 * 2 * 2 * 2 * 2
//
// Какой по счёту шаг —
// столько и умножений.

        
        
          
        
      

Но это же можно представить в виде нескольких последовательных умножений на 2:

        
          
          // 2^5 = ((((2 * 2) * 2) * 2) * 2)//// 1 шаг: 2// 2 шаг: 2 * 2  (результат 1-го шага * 2)// 3 шаг: 4 * 2  (результат 2-го шага * 2)// 4 шаг: 8 * 2  (результат 3-го шага * 2)// 5 шаг: 16 * 2  (результат 4-го шага * 2)//// Для получения нового результата// мы берём предыдущий и умножаем его на 2.
          // 2^5 = ((((2 * 2) * 2) * 2) * 2)
//
// 1 шаг: 2
// 2 шаг: 2 * 2  (результат 1-го шага * 2)
// 3 шаг: 4 * 2  (результат 2-го шага * 2)
// 4 шаг: 8 * 2  (результат 3-го шага * 2)
// 5 шаг: 16 * 2  (результат 4-го шага * 2)
//
// Для получения нового результата
// мы берём предыдущий и умножаем его на 2.

        
        
          
        
      

При таком представлении всё возведение в степень — это лишь умножение предыдущего результата на 2:

        
          
          // 2^n = 2^(n-1) * 2// Значение степени двойки —// это предыдущее значение, умноженное на 2.
          // 2^n = 2^(n-1) * 2
// Значение степени двойки —
// это предыдущее значение, умноженное на 2.

        
        
          
        
      

Именно такие задачи называются рекурсивными — когда часть условия ссылается на всю задачу в целом (или похожую на неё).

У рекурсии 2 составляющие: повторяющиеся операции и базовый случай.

Повторяющиеся операции

Секция статьи "Повторяющиеся операции"

В примере с возведением в степень повторяющиеся операции — это умножение.

Такие операции могут быть сложными и включать в себя несколько подзадач. Такое, например, часто встречается в математике.

Базовый случай

Секция статьи "Базовый случай"

Вторая важная часть рекурсии — это базовый случай.

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

Как только выполнение доходит до базового случая, оно останавливается

Как только выполнение доходит до базового случая, оно останавливается.

Без базового случая любая рекурсивная функция уйдёт в бесконечное выполнение, потому что будет вызывать себя без конца.

В JS это приводит к переполнению стека вызовов, и функция останавливается с ошибкой.

Если выполнить функцию без базового случая, которая лишь вызывает себя, получим ошибку

Если выполнить функцию без базового случая, которая лишь вызывает себя, получим ошибку.

Цикл и рекурсия

Секция статьи "Цикл и рекурсия"

Из-за повторяющихся операций рекурсия схожа с циклом. Их часто считают взаимозаменяемыми, но это всё же не совсем так.

Рекурсия проигрывает циклу в следующем:

  • Отлаживать рекурсию значительно сложнее, чем цикл, а если функция написана плохо — то и просто читать.
  • Она может приводить к переполнению стека. Особенно это ощутимо в таких языках как JS, где переполнение стека может наступить раньше базового случая с высокой вероятностью.
  • Её выполнение может (хотя необязательно) занимать больше памяти.

Цикл же проигрывает рекурсии в таких вещах:

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

Поэтому на вопрос «Что использовать: рекурсию или цикл?» ответом будет «Зависит от задачи», серебряной пули здесь нет :–)

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

Факториал с помощью цикла

Секция статьи "Факториал с помощью цикла"

Сперва решим задачу нахождения факториала с помощью цикла.

        
          
          function factorial(n) {  // Начальный результат будет равен 1,  // чтобы его можно было умножать на последующие числа.  // 0 подходит только для подсчёта суммы,  // потому что умножение на 0 всегда даёт 0.  let result = 1  for (let i = 0; i < n; i++) {    // Так как наш счётчик начинается с 0    // и растёт до n-1, нам нужно прибавить к нему    // единицу, чтобы правильно рассчитать произведение.    result *= i + 1  }  return result}factorial(5) // 120
          function factorial(n) {
  // Начальный результат будет равен 1,
  // чтобы его можно было умножать на последующие числа.
  // 0 подходит только для подсчёта суммы,
  // потому что умножение на 0 всегда даёт 0.
  let result = 1

  for (let i = 0; i < n; i++) {
    // Так как наш счётчик начинается с 0
    // и растёт до n-1, нам нужно прибавить к нему
    // единицу, чтобы правильно рассчитать произведение.
    result *= i + 1
  }

  return result
}

factorial(5) // 120

        
        
          
        
      

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

Факториал с помощью рекурсии

Секция статьи "Факториал с помощью рекурсии"

Для расчёта факториала рекурсивно мы создадим функцию, в которой в первую очередь опишем базовый случай, а уже потом — повторяющиеся действия.

В виде блок-схемы мы можем представить алгоритм факториала как условие и под-вызов той же функции

В виде блок-схемы мы можем представить алгоритм факториала как условие и под-вызов той же функции.

        
          
          function factorial(n) {  // Если мы пытаемся найти факториал 1,  // возвращаем 1 — это базовый случай.  if (n <= 1) {    return 1  }  // В остальных случаях  // возвращаем произведение n  // на факториал предыдущего числа —  // таким образом мы от n дойдём до 1,  // перебрав каждое число.  return n * factorial(n - 1)}factorial(5) // 120
          function factorial(n) {
  // Если мы пытаемся найти факториал 1,
  // возвращаем 1 — это базовый случай.
  if (n <= 1) {
    return 1
  }

  // В остальных случаях
  // возвращаем произведение n
  // на факториал предыдущего числа —
  // таким образом мы от n дойдём до 1,
  // перебрав каждое число.
  return n * factorial(n - 1)
}

factorial(5) // 120

        
        
          
        
      

Кроме того, что функция стала заметно короче, она теперь выражает непосредственно математическую суть факториала.

Процесс вычисления факториала 5 будет состоять из 4 под-вызовов функции

Процесс вычисления факториала 5 будет состоять из 4 под-вызовов функции factorial().

Разберём по шагам, что происходит с переменной n и результатом функции factorial после каждого вызова:

        
          
          /*Сперва мы «спускаемся вглубь» вызовов.Первый вызов создаёт новую область видимости:factorial(5) {  в ней  переменная n становится равной 5;  n - 1 => 4; функция возвращает 5 * factorial(4);  Второй вызов создаёт ещё одну область видимости:  factorial(4) {    n => 4    n - 1 => 3    return 4 * factorial(3)    Третий вызов, ещё одна область видимости:    factorial(3) {      n => 3      n - 1 => 2      return 3 * factorial(2)      Четвёртый вызов, ещё одна область:      factorial(2) {        n => 2        n - 1 => 1        return 2 * factorial(1)        Финальный вызов, последняя область,        базовый случай:        factorial(1) {          n => 1          Так как это базовый случай, возвращаем 1.          После базового случая мы «поднимаемся наверх».        }        В этот момент результат factorial(1) становится равен 1        Возвращаем return 2 * 1      }      Результат factorial(2) => 2      return 3 * 2    }    factorial(3) => 6    return 4 * 6  }  factorial(4) => 24  return 5 * 24}После каждого return область видимости соответствующей функции очищается.Результат вызова становится равным конкретному числу.*/
          /*

Сперва мы «спускаемся вглубь» вызовов.
Первый вызов создаёт новую область видимости:
factorial(5) {
  в ней  переменная n становится равной 5;
  n - 1 => 4; функция возвращает 5 * factorial(4);

  Второй вызов создаёт ещё одну область видимости:
  factorial(4) {
    n => 4
    n - 1 => 3
    return 4 * factorial(3)

    Третий вызов, ещё одна область видимости:
    factorial(3) {
      n => 3
      n - 1 => 2
      return 3 * factorial(2)

      Четвёртый вызов, ещё одна область:
      factorial(2) {
        n => 2
        n - 1 => 1
        return 2 * factorial(1)

        Финальный вызов, последняя область,
        базовый случай:
        factorial(1) {
          n => 1
          Так как это базовый случай, возвращаем 1.
          После базового случая мы «поднимаемся наверх».
        }

        В этот момент результат factorial(1) становится равен 1
        Возвращаем return 2 * 1
      }

      Результат factorial(2) => 2
      return 3 * 2
    }

    factorial(3) => 6
    return 4 * 6
  }

  factorial(4) => 24
  return 5 * 24
}

После каждого return область видимости соответствующей функции очищается.
Результат вызова становится равным конкретному числу.

*/

        
        
          
        
      

Минусы такой реализации:

  • Много областей видимости (замыканий), которые относительно требовательны к памяти.
  • Относительно просто читать, но сложнее отлаживать, чем цикл.

Плюсы:

  • Если мы часто считаем факториалы, мы можем кэшировать результаты выполнения, чтобы не считать факториалы заново. Рекурсивная функция с кешем будет возвращать посчитанный ранее результат сразу же, цикл же будет считать заново.
  • Невозможно повлиять на процесс подсчёта как-то извне, замыкания не дают внешнему миру получить доступ к переменным внутри.

Рекурсивные структуры данных

Секция статьи "Рекурсивные структуры данных"

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

Структуры данных, части которых включают в себя такие же структуры, называются (вы угадали) рекурсивными. Работать с такими структурами в цикле не очень удобно. Чтобы понять почему, рассмотрим пример одной из рекурсивных структур данных — дерева.

Деревья

Секция статьи "Деревья"

Мы уже встречались с деревьями в статье «Как браузер рисует страницы». Мы рассматривали DOM, CSSOM и Render Tree. Вспомним, как выглядит DOM-дерево.

        
          
          <!-- Для такого документа: --><html>  <head>    <meta charset="utf-8">    <title>Hello</title>  </head>  <body>    <p class="text">Hello world</p>    <img src="/hello.jpg" alt="Привет!">  </body></html><!-- ...получится такое дерево:                          html                    ______|_______                    |             |                  body           head                ___|____       ___|___                |       |     |       |                p      img   meta    title                |                     |            "Hello world"           "Hello"-->
          <!-- Для такого документа: -->
<html>
  <head>
    <meta charset="utf-8">
    <title>Hello</title>
  </head>
  <body>
    <p class="text">Hello world</p>
    <img src="/hello.jpg" alt="Привет!">
  </body>
</html>

<!-- ...получится такое дерево:

                          html
                    ______|_______
                    |             |
                  body           head
                ___|____       ___|___
                |       |     |       |
                p      img   meta    title
                |                     |
            "Hello world"           "Hello"

-->

        
        
          
        
      

У каждого дерева есть корень — узел, из которого берут начало остальные узлы. Корень DOM-дерева выше — это элемент html.

Работать с деревьями с помощью циклов (итеративно) неудобно. Представьте, что мы хотим получить названия всех элементов на странице. Да, мы можем пройтись циклом по 1-му уровню или 2-му, но дальше нужно думать, как определять, где мы были, где ещё нет и куда идти дальше.

С рекурсией обход дерева становится немного проще.

Рекурсивный обход

Секция статьи "Рекурсивный обход"

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

  • базовый случай: если у узла дерева нет дочерних узлов вовсе, или мы обошли их все — возвращаем название этого элемента;
  • повторяемые операции: рекурсивно обходим каждый дочерний элемент, собирая их названия.

Таким образом, начав с элемента html, мы пройдём по каждому элементу дерева и запишем их названия. В псевдокоде это выглядело бы так:

        
          
          // Псевдокод:function nameOf(element) {  /* ...Возвращает название элемента. */}function eachChild(element, func) {  /* ...Вызывает функцию func      на каждом дочернем узле элемента element. */}function childrenOf(node) {  /* ...Возвращает дочерние узлы данного узла,      если их нет, возвращает null. */}function traverse(treeNode) {  // Если дочерних узлов нет, это базовый случай;  // возвращаем массив с названием текущего элемента.  // Массив здесь нужен для последовательности,  // так как дальше мы будем возвращать массивы с названиями других узлов,  // то чтобы нам не приходилось каждый раз проверять тип результата,  // мы всегда возвращаем массив.  if (!childrenOf(treeNode)) {    return [nameOf(treeNode)]  }  // Если же случай не базовый,  // то мы проходим по каждому из дочерних узлов  // и вызываем на нём функцию traverse.  // В nameArrays у нас получится список списков названий.  // (На каждый дочерний узел по списку.)  const namesArrays = eachChild(treeNode, traverse)  // Нам останется сделать список плоским  // и вернуть его как результат.  const names = namesArrays.flat()  return names}// Начав обход с корневого узла дерева,// вы получим на выходе список имён всех элементов.const names = traverse(rootNode)
          // Псевдокод:

function nameOf(element) {
  /* ...Возвращает название элемента. */
}

function eachChild(element, func) {
  /* ...Вызывает функцию func
      на каждом дочернем узле элемента element. */
}

function childrenOf(node) {
  /* ...Возвращает дочерние узлы данного узла,
      если их нет, возвращает null. */
}

function traverse(treeNode) {
  // Если дочерних узлов нет, это базовый случай;
  // возвращаем массив с названием текущего элемента.
  // Массив здесь нужен для последовательности,
  // так как дальше мы будем возвращать массивы с названиями других узлов,
  // то чтобы нам не приходилось каждый раз проверять тип результата,
  // мы всегда возвращаем массив.
  if (!childrenOf(treeNode)) {
    return [nameOf(treeNode)]
  }

  // Если же случай не базовый,
  // то мы проходим по каждому из дочерних узлов
  // и вызываем на нём функцию traverse.
  // В nameArrays у нас получится список списков названий.
  // (На каждый дочерний узел по списку.)
  const namesArrays = eachChild(treeNode, traverse)

  // Нам останется сделать список плоским
  // и вернуть его как результат.
  const names = namesArrays.flat()
  return names
}

// Начав обход с корневого узла дерева,
// вы получим на выходе список имён всех элементов.
const names = traverse(rootNode)

        
        
          
        
      

Когда использовать рекурсию

Секция статьи "Когда использовать рекурсию"

Сама по себе рекурсия — это всего лишь инструмент. Нет чётких правил, когда её надо использовать, а когда — нет. Есть лишь некоторые рекомендации.

  • Если вы работаете с рекурсивной структурой данных, лучше использовать рекурсию — это будет сильно проще.
  • Если промежуточный результат выполнения функции можно закэшировать, то стоит подумать об использовании рекурсии.

Когда использовать цикл

Секция статьи "Когда использовать цикл"
  • Если рекурсивную функцию сложно читать или отлаживать, можно превратить её в цикл. Код станет менее лаконичным, но сил на отладку будет уходить меньше.
  • Если вам жизненно необходимо оптимизировать работу программы, рекурсию можно переписать на цикл. Это почти всегда работает быстрее, хотя код и становится менее читаемым.