Рекурсия

Чтобы переложить Ханойскую башню из 64 дисков, нужно 18 446 744 073 709 551 615 ходов; рекурсивная функция описывает решение в четыре строки.

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

Некоторые задачи содержат свою уменьшенную копию. Факториал 5, записывается 5!, равен 5 × 4 × 3 × 2 × 1 = 120. Посмотри ещё раз: это 5 × (4 × 3 × 2 × 1), то есть 5 × 4!. В общем виде n! = n × (n − 1)!, так что для вычисления факториала можно вычислить меньший факториал и умножить. Функция, которая решает задачу, вызывая себя на меньшем варианте, называется рекурсивной.

function factorial(n) {
  if (n <= 1) return 1;          // базовый случай: здесь остановка
  return n * factorial(n - 1);   // рекурсивный случай: задача поменьше
}
console.log(factorial(5)); // 120

Каждой рекурсивной функции нужны две части. Базовый случай представляет собой входные данные, достаточно маленькие, чтобы ответить сразу, без нового вызова: здесь факториал 1 равен 1. Рекурсивный случай уменьшает задачу и снова вызывает функцию. Каждый вызов должен приближаться к базовому случаю. Если нет, например если по ошибке написать factorial(n + 1), вызовы никогда не закончатся.

Стек вызовов

Как компьютер следит за всеми этими незаконченными вызовами? Когда выполняется factorial(5), он доходит до 5 * factorial(4) и должен ждать ответа. Компьютер кладёт ждущий вызов в стек, стопку, из которой первым берут то, что положили последним. factorial(4) ждёт factorial(3), и так далее вниз до factorial(1), который сразу возвращает 1. Затем стек разворачивается: factorial(2) возвращает 2, factorial(3) возвращает 6, factorial(4) возвращает 24, а factorial(5) возвращает 120.

Размер стека ограничен. Рекурсия, которая никогда не доходит до базового случая, всё добавляет вызовы, пока не кончится место, и JavaScript останавливается с ошибкой; в Chrome и Node.js сообщение звучит так: "RangeError: Maximum call stack size exceeded". Из-за того же ограничения очень глубокую рекурсию, в сотни тысяч уровней, лучше писать циклом.

Ханойская башня

Ханойская башня является головоломкой, которую опубликовал французский математик Эдуард Люка в 1883 г. Есть три стержня, а на первом стопка дисков разного размера, самый большой внизу. Цель: переложить всю стопку на третий стержень. Перекладывать можно только по одному диску, только верхний диск стержня и никогда нельзя класть больший диск на меньший.

Если пошагово думать, куда идёт каждый диск, быстро запутаешься. Если думать рекурсивно, всё коротко. Чтобы переложить n дисков с A на C: сначала убери верхние n − 1 дисков с дороги, с A на B. Затем переложи самый большой диск с A на C. Затем переложи n − 1 дисков с B на него, на C. Переложить n − 1 дисков является той же головоломкой на размер меньше, а переложить один диск является базовым случаем. Для 3 дисков получается 7 ходов; лаборатория показывает стопку ждущих вызовов на каждом ходу.

function hanoi(n, from, to, via) {
  if (n === 0) return;
  hanoi(n - 1, from, via, to);
  console.log("disk " + n + ": " + from + " -> " + to);
  hanoi(n - 1, via, to, from);
}
hanoi(3, "A", "C", "B");  // 7 ходов

Сколько ходов нужно для n дисков? Переложить n дисков стоит двух перекладываний n − 1 дисков плюс один ход: M(n) = 2M(n − 1) + 1, при M(1) = 1. Это даёт 1, 3, 7, 15, 31, так что M(n) = 2ⁿ − 1, и ни одно решение не обходится меньшим числом. Десять дисков требуют 1023 ходов. Шестьдесят четыре диска требуют 2⁶⁴ − 1 = 18 446 744 073 709 551 615 ходов; по одному ходу в секунду это около 585 миллиардов лет. Это рост O(2ⁿ) из прошлого урока.

Рекурсия, циклы и повторная работа

Всё, что написано рекурсией, можно написать циклом и собственным стеком, а простые случаи вроде факториала часто понятнее в виде цикла. Рекурсия хороша, когда сама задача устроена как дерево: деление списка в сортировке слиянием, обход папок внутри папок или поиск в лабиринте, о котором последний урок. Одна ловушка связана с повторной работой. Числа Фибоначчи 0, 1, 1, 2, 3, 5, 8, … подчиняются правилу fib(n) = fib(n − 1) + fib(n − 2). Если записать это прямо рекурсией, fib(10) = 55 делает 177 вызовов, fib(20) делает 21 891, а fib(30) делает 2 692 537, потому что одни и те же меньшие значения вычисляются снова и снова. Если запоминать уже найденные ответы или строить снизу вверх циклом, эти потери исчезают.