javascript 2.1.1 Рекурсия и стек

Вернёмся к функциям и изучим их более подробно. Нашей первой темой будет рекурсия.

Если вы не новичок в программировании, то, возможно, уже знакомы с рекурсией и можете пропустить эту главу.

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

В процессе выполнения задачи в теле функции могут быть вызваны другие функции для выполнения подзадач. Частный случай подвызова – когда функция вызывает сама себя. Это как раз и называется рекурсией.

Два способа мышления

В качестве первого примера напишем функцию pow(x, n), которая возводит x в натуральную степень n. Иначе говоря, умножает x на само себя n раз.

pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16

Рассмотрим два способа её реализации.

1. Итеративный способ: цикл for: function pow(x, n) { let result = 1; // умножаем result на x n раз в цикле for (let i = 0; i < n; i++) { result *= x; } return result; } alert( pow(2, 3) ); // 8
2. Рекурсивный способ: упрощение задачи и вызов функцией самой себя: function pow(x, n) { if (n == 1) { return x; } else { return x * pow(x, n - 1); } } alert( pow(2, 3) ); // 8

Обратите внимание, что рекурсивный вариант отличается принципиально.

Когда функция pow(x, n) вызывается, исполнение делится на две ветви:

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)

1. Если n == 1, тогда всё просто. Эта ветвь называется базой рекурсии, потому что сразу же приводит к очевидному результату: pow(x, 1) равно x.
2. Мы можем представить pow(x, n) в виде: x * pow(x, n - 1). Что в математике записывается как: xn = x * xn-1. Эта ветвь – шаг рекурсии: мы сводим задачу к более простому действию (умножение на x) и более простой аналогичной задаче (pow с меньшим n). Последующие шаги упрощают задачу всё больше и больше, пока n не достигает 1.

Говорят, что функция pow рекурсивно вызывает саму себя до n == 1.

Например, рекурсивный вариант вычисления pow(2, 4) состоит из шагов:

1. pow(2, 4) = 2 * pow(2, 3)
2. pow(2, 3) = 2 * pow(2, 2)
3. pow(2, 2) = 2 * pow(2, 1)
4. pow(2, 1) = 2

Итак, рекурсию используют, когда вычисление функции можно свести к её более простому вызову, а его – к ещё более простому и так далее, пока значение не станет очевидно.

Рекурсивное решение обычно короче

Рекурсивное решение задачи обычно короче, чем итеративное.

Используя условный оператор ? вместо if, мы можем переписать pow(x, n), делая код функции более лаконичным, но всё ещё легко читаемым:

function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

Общее количество вложенных вызовов (включая первый) называют глубиной рекурсии. В нашем случае она будет равна ровно n.

Максимальная глубина рекурсии ограничена движком JavaScript. Точно можно рассчитывать на 10000 вложенных вызовов, некоторые интерпретаторы допускают и больше, но для большинства из них 100000 вызовов – за пределами возможностей. Существуют автоматические оптимизации, помогающие избежать переполнения стека вызовов («оптимизация хвостовой рекурсии»), но они ещё не поддерживаются везде и работают только для простых случаев.

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

Контекст выполнения, стек

Теперь мы посмотрим, как работают рекурсивные вызовы. Для этого заглянем «под капот» функций.

Информация о процессе выполнения запущенной функции хранится в её контексте выполнения (execution context).

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

Один вызов функции имеет ровно один контекст выполнения, связанный с ним.

Когда функция производит вложенный вызов, происходит следующее:

• Выполнение текущей функции приостанавливается.
• Контекст выполнения, связанный с ней, запоминается в специальной структуре данных – стеке контекстов выполнения.
• Выполняются вложенные вызовы, для каждого из которых создаётся свой контекст выполнения.
• После их завершения старый контекст достаётся из стека, и выполнение внешней функции возобновляется с того места, где она была остановлена.

Разберёмся с контекстами более подробно на примере вызова функции pow(2, 3).

pow(2, 3)

В начале вызова pow(2, 3) контекст выполнения будет хранить переменные: x = 2, n = 3, выполнение находится на первой строке функции.

Можно схематически изобразить это так:

• Контекст: { x: 2, n: 3, строка 1 } pow(2, 3)

Это только начало выполнения функции. Условие n == 1 ложно, поэтому выполнение идёт во вторую ветку if:

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) );

Значения переменных те же самые, но выполнение функции перешло к другой строке, актуальный контекст:

• Контекст: { x: 2, n: 3, строка 5 } pow(2, 3)

Чтобы вычислить выражение x * pow(x, n - 1), требуется произвести запуск pow с новыми аргументами pow(2, 2).

pow(2, 2)

Для выполнения вложенного вызова JavaScript запоминает текущий контекст выполнения в стеке контекстов выполнения.

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

1. Текущий контекст «запоминается» на вершине стека.
2. Создаётся новый контекст для вложенного вызова.
3. Когда выполнение вложенного вызова заканчивается – контекст предыдущего вызова восстанавливается, и выполнение соответствующей функции продолжается.

Вид контекста в начале выполнения вложенного вызова pow(2, 2):

• Контекст: { x: 2, n: 2, строка 1 } pow(2, 2)
• Контекст: { x: 2, n: 3, строка 5 } pow(2, 3)

Новый контекст выполнения находится на вершине стека (и выделен жирным), а предыдущие запомненные контексты – под ним.

Когда выполнение подвызова закончится, можно будет легко вернуться назад, потому что контекст сохраняет как переменные, так и точное место кода, в котором он остановился. Слово «строка» на рисунках условно, на самом деле запоминается более точное место в цепочке команд.

pow(2, 1)

Процесс повторяется: производится новый вызов в строке 5, теперь с аргументами x=2, n=1.

Создаётся новый контекст выполнения, предыдущий контекст добавляется в стек:

• Контекст: { x: 2, n: 1, строка 1 } pow(2, 1)
• Контекст: { x: 2, n: 2, строка 5 } pow(2, 2)
• Контекст: { x: 2, n: 3, строка 5 } pow(2, 3)

Теперь в стеке два старых контекста и один текущий для pow(2, 1).

Выход

При выполнении pow(2, 1), в отличие от предыдущих запусков, условие n == 1 истинно, поэтому выполняется первая ветка условия if:

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

Вложенных вызовов больше нет, поэтому функция завершается, возвращая 2.

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

• Контекст: { x: 2, n: 2, строка 5 } pow(2, 2)
• Контекст: { x: 2, n: 3, строка 5 } pow(2, 3)

Возобновляется обработка вызова pow(2, 2). Имея результат pow(2, 1), он может закончить свою работу x * pow(x, n - 1), вернув 4.

Восстанавливается контекст предыдущего вызова:

• Контекст: { x: 2, n: 3, строка 5 } pow(2, 3)

Самый внешний вызов заканчивает свою работу, его результат: pow(2, 3) = 8.

Глубина рекурсии в данном случае составила 3.

Как видно из иллюстраций выше, глубина рекурсии равна максимальному числу контекстов, одновременно хранимых в стеке.

Обратим внимание на требования к памяти. Рекурсия приводит к хранению всех данных для неоконченных внешних вызовов в стеке, и в данном случае это приводит к тому, что возведение в степень n хранит в памяти n различных контекстов.

Реализация возведения в степень через цикл гораздо более экономна:

function pow(x, n) {
  let result = 1;

  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

Итеративный вариант функции pow использует один контекст, в котором будут последовательно меняться значения i и result. При этом объём затрачиваемой памяти небольшой, фиксированный и не зависит от n.

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

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

Часто код с использованием рекурсии более короткий, лёгкий для понимания и поддержки. Оптимизация требуется не везде, как правило, нам важен хороший код, поэтому она и используется.