Рекурсия и рекурсивные функции в JavaScript

Mark Nelyubin

Cover Image for Рекурсия и рекурсивные функции в JavaScript

Mark Nelyubin

November 30, 2022

В статье я разберу стек вызовов, примеры рекурсии в жизни, расскажу про рекурсивные функции и структуры данных в JavaScript.

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

Чтобы понять рекурсию, нужно сначала понять рекурсию

Рекурсия в природе

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

Пример из природы — суккуленты. Photo by Martin Rancourt on Unsplash

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

Треугольник Серпинского — пример геометрического фрактала в форме бесконечной рекурсии

Рекурсивные функции в JavaScript

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

Разберем на примере. Задача — написать функцию, которая суммирует все числа от 1 до n. f(3) —> 1+2+3 = 6

Первый способ — пройтись циклом от 1 до n и суммировать значения в переменную result:

const sumTo = (n) => {
    let result = 0;
    
    for (let i=1; i<=n; i++){
        result += i;
    }
    
    return result;
}

Эту задачу можно решить с помощью рекурсии. Для этого нам нужны две вещи:

функция, которая вызывает сама себя
условие, при котором функция перестает вызывать сама себя (базовый случай)

const sumToN = (n) => {
  // базовый случай, когда функция перестает вызывать сама себя
  if (n === 1) return 1;
  // функция вызывает саму себя с новым аргументом
  return n + sumToN(n-1);
}

sumToN(3); // 6

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

При первом вызове функция вернет n + f(n-1), то есть 3 + f(3-1). Этот return будет первой нижней книгой в стопке. Чтобы рассчитать его, нужно взывать функцию еще раз со значением 2.

Так повторяется до тех пор, пока мы не дойдем до базового случая, когда n=1. Теперь наша стопка начнет схлопываться, так как у нас есть значение для расчета предыдущего слоя. В итоге, не останется ни одного слоя, и функция вернет результат 6.

Два элемента рекурсивной функции — Different Input и Base Case

Рекурсия в программировании состоит из двух элементов—повторяющиеся операции с отличающимися вводными (Different Input) и базовый случай(Base Case).

Повторяющиеся операции в нашем примере — это когда функция раз за разом вызывала саму себя, но в качестве аргумента передавала разные значения — 3, 2 и 1.

Базовый случай — условие, при выполнении которого рекурсия заканчивается и функция больше не вызывает саму себя. В нашем примере это условие, когда n === 1. В этот момент функция возвращает значение 1 и не вызывает сама себя.

Если в рекурсивной функции забыть указать базовый случай — произойдет примерно то же самое что, и в случае бесконечного цикла: стек вызовов будет переполнен.

Пример: расчет факториала с помощью рекурсии

Факториал — произведение всех натуральных чисел от 1 до n включительно.

5! = 1*2*3*4*5 = 120
0! = 0

Напишем итеративную функцию с использованием цикла:

const factorial = num => {
    let total = 1;
    for(let i = num; i > 1; i--){
        total *= i
    }
    return total;
}

Напишем рекурсивную функцию:

function factorial(n){
  if (n===0) return 0; // на случай, если вызовем factorial(0)
  if (n===1) return 1;
  return n*factorial(n-1);
}

factorial(5); // 120

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

Структура данных — это набор значений, отношения между ними, а также функции и операции, которые можно применить к данным

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

Одна из рекурсивных структур данных — деревья. Дерево состоит из поддеревьев, которые тоже состоят из поддеревьев и так далее. Примеры древовидной структуры:

DOM-дерево, состоящее из HTML-элементов;
Файловая структура компьютера
Иерархическая структура компании

<!-- из HTML-разметки вроде такой-->

<html>
  <head>
    <meta charset="utf-8">
    <title>Medium</title>
  </head>
  <body>
    <header>
      <ul class="menu">
        <li>Main</li>
        <li>Articles</li>
        <li>Advertise</li>
      </ul>
    </header>
    <article id="12">
      <h1>Рекурсия и рекурсивные функции в JavaScript</h1>
      <p>Рекурсивная структура данных - структура, которая повторяет сама себя в своих частях.</p>
    </article>
  </body>
</html>

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

                          html
                    ______|_______
                    |             |
                  body           head
                ___|____       ___|___
                |       |     |       |
             header  article meta   title
                |     |   |           |
                ul    h1  p      "DevBlast"
...и так далее
-->

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

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

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

Плюсы и минусы рекурсии

У итеративной и рекурсивной реализации есть свои плюсы и минусы:

Рекурсивная функция, как правило, быстрее, но её сложнее отлаживать и читать;
Рекурсия может приводить к переполнению стека. Например, если мы вызовем factorial(10000) в консоли браузера, увидим ошибку о переполнении стека, тогда как в итеративной функции проблем не будет;
Результат выполнения рекурсивной функции проще закэшировать, чтобы ускорить выполнение. Это сложнее сделать в итеративной функции.
С помощью рекурсии намного проще работать с рекурсивными структурами данных.

Итог

Рекурсия — это процесс, который воспроизводит сам себя. В JS рекурсия — когда функция вызывает сама себя.
При вызове функция добавляется в стек (стопку), а при выполнении операций или возврате расчитанного значения в return — исчезает из стека.
Рекурсивная функция вызывает сама себя несколько раз, пока на одном из витков не дойдет до расчитанного значения (базового случая), поэтому стек вызовов сначала наполняется, а потом освобождается.
В рекурсивной функции обязательно присутствует повторяющаяся операция с новым вводными (different input), и базовый случай (base case).
Рекурсивная функция помогает работать с рекурсивными структурами данных, такими как деревья (например, DOM-дерево).

DevSurge 💦