Рекурсия, стек

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

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

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

Сейчас мы посмотрим примеры.

Рекурсия – общая тема программирования, не относящаяся напрямую к JavaScript. Если вы разрабатывали на других языках или изучали программирование раньше в ВУЗе, то наверняка уже знаете, что это такое.

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

Степень pow(x, n) через рекурсию

В качестве первого примера использования рекурсивных вызовов – рассмотрим задачу возведения числа x в натуральную степень n.

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

pow(x, n) = x * pow(x, n - 1)

То есть, xn = x * xn-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

На шаге 1 нам нужно вычислить pow(2,3), поэтому мы делаем шаг 2, дальше нам нужно pow(2,2), мы делаем шаг 3, затем шаг 4, и на нём уже можно остановиться, ведь очевидно, что результат возведения числа в степень 1 – равен самому числу.

Далее, имея результат на шаге 4, он подставляется обратно в шаг 3, затем имеем pow(2,2) – подставляем в шаг 2 и на шаге 1 уже получаем результат.

Этот алгоритм на JavaScript:

function pow(x, n) {
  if (n != 1) { // пока n != 1, сводить вычисление pow(x,n) к pow(x,n-1)
    return x * pow(x, n - 1);
  } else {
    return x;
  }
}

alert( pow(2, 3) ); // 8

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

Значение, на котором рекурсия заканчивается, называют базисом рекурсии. В примере выше базисом является 1.

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

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

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

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

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

У каждого вызова функции есть свой «контекст выполнения» (execution context).

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

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

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

Далее функция pow начинает выполняться. Вычисляется выражение n != 1 – оно равно true, ведь в текущем контексте n=3. Поэтому задействуется первая ветвь if :

function pow(x, n) {
  if (n != 1) { // пока n != 1 сводить вычисление pow(x,n) к pow(x,n-1)
    return x * pow(x, n - 1);
  } else {
    return x;
  }
}

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

При любом вложенном вызове JavaScript запоминает текущий контекст выполнения в специальной внутренней структуре данных – «стеке контекстов».

Затем интерпретатор приступает к выполнению вложенного вызова.

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

Для нового вызова создаётся свой контекст выполнения, и управление переходит в него, а когда он завершён – старый контекст достаётся из стека и выполнение внешней функции возобновляется.

Разберём происходящее с контекстами более подробно, начиная с вызова (*):

function pow(x, n) {
  if (n != 1) { // пока n!=1 сводить вычисление pow(..n) к pow(..n-1)
    return x * pow(x, n - 1);
  } else {
    return x;
  }
}

alert( pow(2, 3) ); // (*)
pow(2, 3)

Запускается функция pow, с аргументами x=2, n=3. Эти переменные хранятся в контексте выполнения, схематично изображённом ниже:

  • Контекст: { x: 2, n: 3, строка 1 }
Выполнение в этом контексте продолжается, пока не встретит вложенный вызов в строке 3.
pow(2, 2)

В строке 3 происходит вложенный вызов pow с аргументами x=2, n=2. Текущий контекст сохраняется в стеке, а для вложеннного вызова создаётся новый контекст (выделен жирным ниже):

  • Контекст: { x: 2, n: 3, строка 3 }
  • Контекст: { x: 2, n: 2, строка 1 }
Обратим внимание, что контекст включает в себя не только переменные, но и место в коде, так что когда вложенный вызов завершится -- можно будет легко вернуться назад.

Слово «строка» здесь условно, на самом деле, конечно, запомнено более точное место в цепочке команд.

pow(2, 1)

Опять вложенный вызов в строке 3, на этот раз – с аргументами x=2, n=1. Создаётся новый текущий контекст, предыдущий добавляется в стек:

  • Контекст: { x: 2, n: 3, строка 3 }
  • Контекст: { x: 2, n: 2, строка 3 }
  • Контекст: { x: 2, n: 1, строка 1 }
На текущий момент в стеке уже два старых контекста.
Выход из pow(2, 1).

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

function pow(x, n) {
  if (n != 1) {
    return x * pow(x, n - 1);
  } else {
    return x; // первая степень числа равна самому числу
  }
}

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

  • Контекст: { x: 2, n: 3, строка 3 }
  • Контекст: { x: 2, n: 2, строка 3 }
Возобновляется обработка внешнего вызова `pow(2, 2)`.
Выход из pow(2, 2).

…И теперь уже pow(2, 2) может закончить свою работу, вернув 4. Восстанавливается контекст предыдущего вызова:

  • Контекст: { x: 2, n: 3, строка 3 }
Возобновляется обработка внешнего вызова `pow(2, 3)`.
Выход из pow(2, 3).

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

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

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

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

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

function pow(x, n) {
  var result = x;
  for (var i = 1; i < n; i++) {
    result *= x;
  }
  return result;
}

У такой функции pow будет один контекст, в котором будут последовательно меняться значения i и result.

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

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

Итого

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

Существуют много областей применения рекурсивных вызовов. Здесь мы посмотрели на один из них – решение задачи путём сведения её к более простой (с меньшими аргументами), но также рекурсия используется для работы с «естественно рекурсивными» структурами данных, такими как HTML-документы, для «глубокого» копирования сложных объектов.

Есть и другие применения, с которыми мы встретимся по мере изучения JavaScript.

Здесь мы постарались рассмотреть происходящее достаточно подробно, однако, если пожелаете, допустимо временно забежать вперёд и открыть главу Отладка в браузере Chrome, с тем чтобы при помощи отладчика построчно пробежаться по коду и посмотреть стек на каждом шаге. Отладчик даёт к нему доступ.

Задачи

важность: 5

Напишите функцию sumTo(n), которая для данного n вычисляет сумму чисел от 1 до n, например:

sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
sumTo(4) = 4 + 3 + 2 + 1 = 10
...
sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050

Сделайте три варианта решения:

  1. С использованием цикла.
  2. Через рекурсию, т.к. sumTo(n) = n + sumTo(n-1) для n > 1.
  3. С использованием формулы для суммы арифметической прогрессии.

Пример работы вашей функции:

function sumTo(n) { /*... ваш код ... */ }

alert( sumTo(100) ); // 5050

Какой вариант решения самый быстрый? Самый медленный? Почему?

Можно ли при помощи рекурсии посчитать sumTo(100000)? Если нет, то почему?

Решение с использованием цикла:

function sumTo(n) {
  var sum = 0;
  for (var i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}

alert( sumTo(100) );

Решение через рекурсию:

function sumTo(n) {
  if (n == 1) return 1;
  return n + sumTo(n - 1);
}

alert( sumTo(100) );

Решение по формуле: sumTo(n) = n*(n+1)/2:

function sumTo(n) {
  return n * (n + 1) / 2;
}

alert( sumTo(100) );

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

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

Рекурсия в данном случае работает медленнее всех.

P.P.S. Существует ограничение глубины вложенных вызовов, поэтому рекурсивный вызов sumTo(100000) выдаст ошибку.

важность: 4

Факториа́л числа – это число, умноженное на «себя минус один», затем на «себя минус два» и так далее, до единицы. Обозначается n!

Определение факториала можно записать как:

n! = n * (n - 1) * (n - 2) * ...*1

Примеры значений для разных n:

1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120

Задача – написать функцию factorial(n), которая возвращает факториал числа n!, используя рекурсивный вызов.

alert( factorial(5) ); // 120

Подсказка: обратите внимание, что n! можно записать как n * (n-1)!. Например: 3! = 3*2! = 3*2*1! = 6

По свойствам факториала, как описано в условии, n! можно записать как n * (n-1)!.

То есть, результат функции для n можно получить как n, умноженное на результат функции для n-1, и так далее до 1!:

function factorial(n) {
  return (n != 1) ? n * factorial(n - 1) : 1;
}

alert( factorial(5) ); // 120

Базисом рекурсии является значение 1. А можно было бы сделать базисом и 0. Тогда код станет чуть короче:

function factorial(n) {
  return n ? n * factorial(n - 1) : 1;
}

alert( factorial(5) ); // 120

В этом случае вызов factorial(1) сведётся к 1*factorial(0), будет дополнительный шаг рекурсии.

важность: 5

Последовательность чисел Фибоначчи имеет формулу Fn = Fn-1 + Fn-2. То есть, следующее число получается как сумма двух предыдущих.

Первые два числа равны 1, затем 2(1+1), затем 3(1+2), 5(2+3) и так далее: 1, 1, 2, 3, 5, 8, 13, 21....

Числа Фибоначчи тесно связаны с золотым сечением и множеством природных явлений вокруг нас.

Напишите функцию fib(n), которая возвращает n-е число Фибоначчи. Пример работы:

function fib(n) { /* ваш код */ }

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77)); // 5527939700884757

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

Вычисление рекурсией (медленное)

Решение по формуле, используя рекурсию:

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // не запускаем, подвесит браузер

При больших значениях n оно будет работать очень медленно. Например, fib(77) уже будет вычисляться очень долго.

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

...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...

Здесь видно, что значение fib(3) нужно одновременно и для fib(5) и для fib(4). В коде оно будет вычислено два раза, совершенно независимо.

Можно это оптимизировать, запоминая уже вычисленные значения, получится гораздо быстрее. Альтернативный вариант – вообще отказаться от рекурсии, а вместо этого в цикле начать с первых значений 1, 2, затем из них получить fib(3), далее fib(4), затем fib(5) и так далее, до нужного значения.

Это решение будет наиболее эффективным. Попробуйте его написать.

Алгоритм вычисления в цикле

Будем идти по формуле слева-направо:

var a = 1, b = 1; // начальные значения
var c = a + b; // 2

/* переменные на начальном шаге:
a  b  c
1, 1, 2
*/

Теперь следующий шаг, присвоим a и b текущие 2 числа и получим новое следующее в c:

a = b, b = c;
c = a + b;

/* стало так (ещё число):
   a  b  c
1, 1, 2, 3
*/

Следующий шаг даст нам ещё одно число последовательности:

a = b, b = c;
c = a + b;

/* стало так (ещё число):
      a  b  c
1, 1, 2, 3, 5
*/

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

P.S. Этот подход к вычислению называется динамическое программирование снизу-вверх.

Код для вычисления в цикле

function fib(n) {
  var a = 1,
    b = 1;
  for (var i = 3; i <= n; i++) {
    var c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

Цикл здесь начинается с i=3, так как первое и второе числа Фибоначчи заранее записаны в переменные a=1, b=1.

Карта учебника

Комментарии

перед тем как писать…
  • Приветствуются комментарии, содержащие дополнения и вопросы по статье, и ответы на них.
  • Для одной строки кода используйте тег <code>, для нескольких строк кода — тег <pre>, если больше 10 строк — ссылку на песочницу (plnkr, JSBin, codepen…)
  • Если что-то непонятно в статье — пишите, что именно и с какого места.