Перевод статьи «Recursion and the Call Stack Explained By Reading A Book».
Рекурсия это один из наиболее потрясающих принципов во всех языках программирования.
Нерекурсивные функции (другими словами, функции, которые вы использовали в прошлом), запускались единожды при каждом вызове и возвращали результат благодаря инструкции возврата return.
А вот рекурсивная функция, вызванная единожды, может затем вызывать сама себя неопределенное число раз, прежде чем скомбинирует результат всех вызовов и вернет его по инструкции return.
Выглядит это примерно так.
Статичная версия:
Динамичная версия:
Рекурсия замечательна тем, что отдельная функция может вызываться от одного до бесконечного числа раз благодаря простой инструкции.
Но вместе с тем довольно сложно придумать для этой ситуации аналогию из окружающего мира. И находить аналогии становится еще сложнее, когда мы затрагиваем концепцию стека вызовов (о ней мы еще поговорим).
Кто-то предлагает в качестве аналогии набор коробок, внутри которых спрятаны другие коробки:
Другие предлагают представить себе матрешку:
Но этот пример бесполезен для понимания стека вызовов.
В этой руководстве мы рассмотрим два популярных примера рекурсии. Также мы создадим визуальный язык для понимания функции и стека вызовов — это поможет нам разобраться в многократных вызовах функции, идущих подряд.
Чтобы разобраться в концепциях этой статьи, нужно иметь базовое понимание функций в JavaScript.
Пример 1 — факториалы
Факториалы это самый распространенный пример рекурсии. Вероятно, вы знакомы с понятием факториалов по курсу алгебры.
Факториал числа 3 записывается как 3! и означает 3*2*1, что равно 6.
Это можно выразить при помощи цикла for, где обновление переменной будет происходить вне цикла:
let factorial = 4;
let result = 1;
for (i=factorial; i>= 1; i--){
result = result*i;
}
Но с той же целью мы можем использовать и рекурсию. Вместо того чтобы создавать цикл, обновляющий переменную вне своей области видимости, мы можем применить рекурсию и сделать n-1 вызовов, где n — искомый факториал.
Я сначала покажу, как это выглядит в виде кода, а затем мы оценим, как это работает.
let getFactorial = (num) => {
if (num == 1)
return 1;
else
return num * getFactorial(num-1);
}
getFactorial(4);
// 24
Этот код позволяет достигнуть того же результата, что и код, приведенный выше.
Но если вы посмотрите на строку 5, вы заметите, что инструкция return упоминает саму функцию.
Так когда же эта функция вернет итоговое значение? Как нам связать 4 вызова функции, чтобы в итоге вернулось значение 24?
Вот как раз здесь нам и пригодится стек вызовов. Он определяет правила для порядка возврата этих вызовов функций.
Но теперь у нас две концепции — рекурсия и стек вызовов — налагаются одна на другую. Это сложно.
Чтобы визуализировать стек вызовов, давайте представим, сто он строится слева направо. Каждый раз при добавлении блока он добавляется на левом конце стека и сдвигает остальные блоки вправо.
Итак, проходя нашу рекурсивную функцию, мы генерируем стек:
Стек вызовов создается внизу гифки. В конце у нас остается 1*2*3*4, что дает 24.
Этот стек состоит из четырех вызовов функции, и ни один из них не запускается, пока функция не вернет 1. Они остаются в стеке, пока не будет добавлено последнее значение, в данном случае — 1.
Это потому, что каждый из первых трех вызовов в стеке включает ссылку на следующий вызов.
Итак, когда num=4, функция возвращает 4*getFactorial(3). Конечно, функция не может вернуть точное значение, пока мы не узнаем значения getFactorial(3). Вот поэтому нам и нужен стек вызовов!
Рекурсия позволяет функции вызываться бесконечное число раз подряд. При этом обновляется стек вызовов. Итоговое значение возвращается после запуска последнего вызова.
Стек вызовов обновляется слева направо, после чего вы можете прочесть все вызовы в порядке их отработки. Самый последний вызов обрабатывается первым, а первый —последним.
Но наша гифка не слишком хороша для показа отношений между вызовами. Поэтому вот еще одна, обновленная версия, показывающая, как вызовы связана между собой инструкцией return:
Пример 2 — разделение строки
Первый пример был математическим, он напоминает задачу из курса алгебры. Факториалы хороши, но есть и другие примеры рекурсии, не связанные с математикой. В этом разделе мы разберем, как можно использовать рекурсию для манипуляций со строкой.
Стоит задача: развернуть строку.
То есть, нужно вернуть строку, где буквы строки, переданной в качестве input, будут записаны в обратном порядке.
Это тоже можно сделать при помощи цикла for, но мы воспользуемся рекурсией.
Давайте подумаем, как нам развернуть слово «cat».
При каждом вызове функции нам нужно отделить первую (или последнюю) букву в строке, а затем вырезать ее из строки. При повторном запуске функции мы опять берем первую (или последнюю) букву.
В конечном итоге стек вызовов позволит нам вернуть буквы в нужном порядке.
Вот код:
let testStr = 'cat';
let revStr = (str) => {
if (str.length == 0)
return '';
else
return revStr(str.substr(1)) + str[0];
};
revStr(testStr);
// 'tac'
Давайте разберем его, как мы делали в первом примере.
Опять-таки, хотя благодаря гифке все кажется простым, если мы хотим действительно понять эти вызовы функции, нам нужно углубиться в итоговую инструкцию return.
Этот пример имеет одно важное отличие от предыдущего: мы осуществляем конкатенацию строки, а не умножение.
Поэтому порядок строк в этой инструкции return имеет большое значение, ведь он определяет порядок дальнейшего объединения.
Поскольку это не серия операций умножения, здесь немного проще понять стек вызовов. Вот как это выглядит:
Когда мы строим стек вызовов так, как показано на гифке, у нас есть определенный порядок вызовов рекурсивной функции и фрагментов строки. Этот порядок очень важен.
Когда мы осуществим все вызовы в стеке, этот порядок позволит нам воссоздать строку в обратном порядке.
