В теле функции могут быть вызваны другие функции для выполнения подзадач.
Частный случай подвызова – когда функция вызывает сама себя. Это называется рекурсией.
Рекурсия используется для ситуаций, когда выполнение одной сложной задачи можно представить как некое действие в совокупности с решением той же задачи в более простом варианте.
Сейчас мы посмотрим примеры.
Рекурсия – общая тема программирования, не относящаяся напрямую к JavaScript. Если вы разрабатывали на других языках или изучали программирование раньше в ВУЗе, то наверняка уже знаете, что это такое.
Эта глава предназначена для читателей, которые пока с этой темой незнакомы и хотят лучше разобраться в том, как работают функции.
В качестве первого примера использования рекурсивных вызовов – рассмотрим задачу возведения числа x
в натуральную степень n
.
Её можно представить как совокупность более простого действия и более простой задачи того же типа вот так:
То есть, xn = x * xn-1
.
Например, вычислим pow(2, 4)
, последовательно переходя к более простой задаче:
pow(2, 4) = 2 * pow(2, 3)
pow(2, 3) = 2 * pow(2, 2)
pow(2, 2) = 2 * pow(2, 1)
pow(2, 1) = 2
На шаге 1 нам нужно вычислить pow(2,3)
, поэтому мы делаем шаг 2, дальше нам нужно pow(2,2)
, мы делаем шаг 3, затем шаг 4, и на нём уже можно остановиться, ведь очевидно, что результат возведения числа в степень 1 – равен самому числу.
Далее, имея результат на шаге 4, он подставляется обратно в шаг 3, затем имеем pow(2,2)
– подставляем в шаг 2 и на шаге 1 уже получаем результат.
Этот алгоритм на JavaScript:
Говорят, что «функция pow
рекурсивно вызывает сама себя» до n == 1
.
Значение, на котором рекурсия заканчивается, называют базисом рекурсии. В примере выше базисом является 1
.
Общее количество вложенных вызовов называют глубиной рекурсии. В случае со степенью, всего будет n
вызовов.
Максимальная глубина рекурсии в браузерах ограничена, точно можно рассчитывать на 10000
вложенных вызовов, но некоторые интерпретаторы допускают и больше.
Итак, рекурсию используют, когда вычисление функции можно свести к её более простому вызову, а его – ещё к более простому, и так далее, пока значение не станет очевидно.
Теперь мы посмотрим, как работают рекурсивные вызовы. Для этого мы рассмотрим, как вообще работают функции, что происходит при вызове.
У каждого вызова функции есть свой «контекст выполнения» (execution context).
Контекст выполнения – это служебная информация, которая соответствует текущему запуску функции. Она включает в себя локальные переменные функции и конкретное место в коде, на котором находится интерпретатор.
Например, для вызова pow(2, 3)
из примера выше будет создан контекст выполнения, который будет хранить переменные x = 2, n = 3
. Мы схематично обозначим его так:
Далее функция pow
начинает выполняться. Вычисляется выражение n != 1
– оно равно true
, ведь в текущем контексте n=3
. Поэтому задействуется первая ветвь if
:
Чтобы вычислить выражение x * pow(x, n-1)
, требуется произвести запуск pow
с новыми аргументами.
При любом вложенном вызове JavaScript запоминает текущий контекст выполнения в специальной внутренней структуре данных – «стеке контекстов».
Затем интерпретатор приступает к выполнению вложенного вызова.
В данном случае вызывается та же pow
, однако это абсолютно неважно. Для любых функций процесс одинаков.
Для нового вызова создаётся свой контекст выполнения, и управление переходит в него, а когда он завершён – старый контекст достаётся из стека и выполнение внешней функции возобновляется.
Разберём происходящее с контекстами более подробно, начиная с вызова (*)
:
pow(2, 3)
Запускается функция pow
, с аргументами x=2
, n=3
. Эти переменные хранятся в контексте выполнения, схематично изображённом ниже:
pow(2, 2)
В строке 3
происходит вложенный вызов pow
с аргументами x=2
, n=2
. Текущий контекст сохраняется в стеке, а для вложеннного вызова создаётся новый контекст (выделен жирным ниже):
Слово «строка» здесь условно, на самом деле, конечно, запомнено более точное место в цепочке команд.
pow(2, 1)
Опять вложенный вызов в строке 3
, на этот раз – с аргументами x=2
, n=1
. Создаётся новый текущий контекст, предыдущий добавляется в стек:
pow(2, 1)
.При выполнении pow(2, 1)
, в отличие от предыдущих запусков, выражение n != 1
будет равно false
, поэтому сработает вторая ветка if..else
:
Здесь вложенных вызовов нет, так что функция заканчивает свою работу, возвращая 2
. Текущий контекст больше не нужен и удаляется из памяти, из стека восстанавливается предыдущий:
pow(2, 2)
.…И теперь уже pow(2, 2)
может закончить свою работу, вернув 4
. Восстанавливается контекст предыдущего вызова:
pow(2, 3)
.Самый внешний вызов заканчивает свою работу, его результат: pow(2, 3) = 8
.
Глубина рекурсии в данном случае составила: 3.
Как видно из иллюстраций выше, глубина рекурсии равна максимальному числу контекстов, одновременно хранимых в стеке.
Обратим внимание на требования к памяти. Рекурсия приводит к хранению всех данных для неоконченных внешних вызовов в стеке, в данном случае это приводит к тому, что возведение в степень n
хранит в памяти n
различных контекстов.
Реализация возведения в степень через цикл гораздо более экономна:
У такой функции pow
будет один контекст, в котором будут последовательно меняться значения i
и result
.
Любая рекурсия может быть переделана в цикл. Как правило, вариант с циклом будет эффективнее.
Но переделка рекурсии в цикл может быть нетривиальной, особенно когда в функции, в зависимости от условий, используются различные рекурсивные подвызовы, когда ветвление более сложное.
Рекурсия – это когда функция вызывает сама себя, как правило, с другими аргументами.
Существуют много областей применения рекурсивных вызовов. Здесь мы посмотрели на один из них – решение задачи путём сведения её к более простой (с меньшими аргументами), но также рекурсия используется для работы с «естественно рекурсивными» структурами данных, такими как HTML-документы, для «глубокого» копирования сложных объектов.