Рекурсия
В видео есть неточность: в формуле вычисления факториала и в коде, который на ней основан, не учитывается, что для 0 (нуля) тоже можно вычислить факториал — он равен 1 (единице). Исправленный код есть ниже в конспекте.
Транскрипт урока
У нас уже есть функция surfaceAreaCalculator, которая принимает один аргумент — радиус — и возвращает площадь поверхности соответствующей сферы, используя формулу 4 * pi * r2. Помните, мы можем представить функции ящиками: кладем что-то в ящик, она производит какие-то действия и выплевывает результат.

Некоторые ящики не принимают ничего, другие ничего не выплевывают, а третьи вообще ничего не делают. Но мы сейчас заинтересованы в ящиках, подобных surfaceAreaCalculator, которая принимает что-то, вычисляет и возвращает результат.

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

Еще польза в том, что теперь код проще понять. Сравните это:

const surfaceOfMars = surfaceAreaCalculator(3390);
с этим:

const surfaceOfMars = 4 * 3.14 * 3390 * 3390;
Первый вариант намного приятней и проще, особенно для того, кто только что увидел этот код. Первый вариант отвечает на вопрос "что", второй — на вопрос "как".

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

const surfaceAreaCalculator = (radius) => {
  return 4 * 3.14 * square(radius);
}
Вместо умножения радиуса на радиус, мы вызовем функцию вычисления квадрата и передадим ей радиус. Очевидно — все, что делает функция вычисления квадрата, это "принимает число и возвращает его квадрат";

const square = (num) => {
  return num * num;
}
Давайте отследим шаги и посмотрим, что происходит, когда мы запускаем нашу программу. Мы создаем константу surfaceOfMars и пытаемся сохранить в нее значение, которое возвращает функция surfaceAreaCalculator, когда она вызывается с числом 3390 в качестве аргумента.

3390 внутри функции известно как radius. Функция хочет умножить числа и выполнить возврат, но ей нужно знать последнее число, ей требуется вызвать функцию square и передать этот радиус. square принимает один аргумент — это число 3390, в нашем случае, и внутри функции square оно известно как num.

square хочет умножить num на num и сделать возврат. Ей никто не мешает и она делает это умножение и возврат. Мы снова внутри surfaceAreaCalculator, который в прямом смысле ждал, пока функция square закончит свое дело. И теперь у нас есть результат вызова square. Он заменяет вызов, поэтому теперь становится возможным завершить умножение и вернуть ответ.

Ответ возвращается и сохраняется в surfaceOfMars.

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

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

Получается шесть уникальных комбинаций из трех книг. Из четырех — 24 комбинации. Из 13 — почти столько, сколько людей на планете. 25 книг? Вариантов их перестановки больше, чем атомов во Вселенной.

Вообще, существует n! вариантов перестановки n книг. Факториал означает — умножить все целые числа от 1 до n. Так что, 3! — это 1 * 2 * 3. Давайте напишем функцию факториала.

const factorial = (n) => {
  return 1 * 2 * 3 * 4; // oй...
}
Ой, подождите. Мы не знаем значение n изначально, в этом вся проблема. Хмм… Как там делается в математике?

А, хорошо, у них там есть два варианта: если n равно 0, тогда факториал — 1, это просто. Но если n не равно 0, тогда факториал — n*(n-1)!

Давайте попробуем вот так:

const factorial = (n) => {
  if (n === 0) {
    return 1;
  }
  else {
    return n * factorial(n - 1);
  }
}

const answer = factorial(3);
Это может показаться странным. Мы вызываем функцию из функции, но… это та же самая функция!

Может тут что-то не так? Вообще-то нет! Все дело в том, что сама по себе функция — это не ящик, это его описание. Когда вы вызываете функцию, тогда создается ящик, а после того, как функция выполнилась, ящик самоуничтожается. Поэтому когда вы вызываете ту же самую функцию из нее самой, просто создается еще один ящик.

Давайте это отследим: мы вызываем factorial(3). 3 это не 0, поэтому первое условие игнорируется. Функция хочет произвести умножение чисел и вернуть ответ, но она не может — ей нужно знать второе число, для чего она вызывает factorial(3-1) или factorial(2).

Формируется новый идентичный ящик factorial, он принимает число 2, это не 0, так что он пробует произвести умножение и вернуть ответ, но не может — ему нужно знать второе число, поэтому он вызывает factorial(1).

Формируется новый идентичный ящик factorial, он принимает число 1 и это снова не 0. Еще одна попытка произвести умножение и вернуть результат, происходит вызов factorial(0) и этот ящик уже может мгновенно вернуть ответ — он возвращает 1.

1 возвращается в предыдущий ящик, умножается на 1 и ответ "1" возвращается в предыдущий ящик, умножается на 2 и ответ "2" возвращается в предыдущий ящик, умножается на 3 и ответ "6" возвращается во внешний мир и сохраняется в константе answer.

Фуух!

Все это и есть рекурсия: что-то описывается через самого себя, содержит себя в своем описании. Когда дело касается математики или программирования, требуется два условия:

  1. Простой базовый случай или терминальный сценарий. Это точка, в которой нужно остановиться. В нашем примере это 0: мы остановили вычисление факториала когда в функцию был передан 0.
  2. Правило передвижения по рекурсии, углубление. В нашем случае это было n * factorial(n-1).
Еще один момент. Если проверить наш код с помощью линтера, то он выдаст ошибку no-else-return. Последуем рекомендациями линтера и отрефакторим код:

const factorial = (n) => {
  if (n === 0) {
    return 1;
  }
  return n * factorial(n - 1);
};

const answer = factorial(3);
Давайте проследим шаги еще раз, но с другой точки зрения, не заглядывая в ящики. Вот, как это выглядит пошагово:

factorial(3);
3 * factorial(2);
3 * 2 * factorial(1);
3 * 2 * 1 * factorial(0);
3 * 2 * 1 * 1;
3 * 2 * 1
3 * 2;
6;
Умножение не происходит пока мы спускаемся до базового случая функции factorial(0). А затем мы возвращаемся наверх, производя одно умножение за один шаг.

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

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

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

Ваша очередь. Переходите к тестам и упражнениям, создайте свою рекурсивную функцию. Процесс может оказаться немного каверзным, но помните: вам нужно описать две вещи — как углубляться и когда остановиться. Удачи!
Выводы
О функциях
  • Можно представить функции как черные коробки: коробка забирает объект, производит внутри какие-то действия, а потом выплевывает что-то новое
  • Некоторые функции ничего не забирают (не принимают аргументы), некоторые вообще ничего не делают (они пустые), некоторые не возвращают значения.
  • Наш surfaceAreaCalculator принимает один аргумент (radius), вычисляет площадь поверхности и возвращает результат этого вычисления.
  • Функции могут вызывать другие функции
  • surfaceAreaCalculator может вызывать функцию square, чтобы получить радиус, возведенный в квадрат, вместо того, чтобы умножать радиус на радиус.
  • Мы пишем функции, чтобы облегчить жизнь:
         • такой код легче понимать
         • функции могут переиспользоваться несколько раз

Сравните:

const surfaceOfMars = surfaceAreaCalculator(3390);  // это "ЧТО", в таком виде легче понять суть
const surfaceOfMars = 4 * 3.14 * 3390 * 3390;       // это "КАК"
Тесты
Пройти тест
Я написал рекурсивную функцию, запустил ее, но программа зависла: она не останавливается и работает, кажется, бесконечно. В чем, скорее всего, причина этой проблемы?

Верно!
Неверно
Неверно
Дальше
Проверить
Завершить тест
Может ли функция сначала вызвать другую функцию, а потом вызвать саму себя?
Неверно
Верно!
Дальше
Проверить
Завершить тест
Дан следующий код:

const factorial = (n) => {
if (n === 1) {
  return 1;
  } else {
return n * factorial(n);
  }
};

const result = factorial(12);

Что можно сказать о нем?
Неверно
Верно!
Неверно
Неверно
Дальше
Проверить
Завершить тест
Возможно ли написать рекурсивную функцию, которая вычисляет сумму серии чисел? (например, сумму чисел от 1 до 1000)
Неверно
Верно!
Дальше
Проверить
Завершить тест
Возможно ли наличие нескольких терминальных условий?
Верно!
Неверно
Дальше
Проверить
Завершить тест
Проанализируйте определения функций sum1 и sum2:

const sum1 = (n) => {
  if (n === 1) {
    return 1;
  }

  return n + sum1(n - 1);
};

const sum2 = n => (n === 1) ? 1 : n + sum2(n - 1);

Эти функции совершают одни и те же операции, просто в sum2 использован "укороченный" синтаксис. Верно ли это утверждение?
Неверно
Верно!
Дальше
Проверить
Завершить тест
Функция-однострочник sum принимает целое положительное число n и возвращает сумму всех чисел, входящих в интервал [0, n]:

const sum = n => (n === 0) ? 0 : n + sum(n - 1);

Есть ли в этом определении терминальное условие? Выберите правильное утверждение
Неверно
Неверно
Верно!
Дальше
Проверить
Завершить тест
Ниже приведено определение функции product, которая принимает на вход целое положительное число n, меньшее или равное 5, и возвращает произведение всех чисел, входящих в интервал [n, 5].

const product = (n) => {
  // if (n === 5) {
  // return n;
  // }

  return n * product(n + 1);
};

/*
* вычисление: 2 * 3 * 4 * 5 * 6 * 7 * ...
* RangeError: Maximum call stack size exceeded
*/
product(2);

Однако её вызов приводит к ошибке. Почему функция работает некорректно?
Верно!
Неверно
Неверно
Неверно
Дальше
Проверить
Завершить тест
Пройти еще раз
Пройти еще раз
Пройти еще раз
Пройти еще раз
Две функции вместе

const surfaceAreaCalculator = (radius) => {
  return 4 * 3.14 * square(radius);
}

const square = (num) => {
  return num * num;
}
Функции, которые вызывают сами себя
  • Определение функции — это описание коробки
  • Оригинал коробки формируется при вызове функции
  • Когда функция вызывает сама себя, создается новая идентичная коробка
Перестановки:
  • Количество способов перестановки n объектов равно n! (перестановки)
  • n! определяется таким способом: если n = 0, то n! = 1; если n > 0, то n! = n * (n-1)!
Функция, вычисляющая факториал:

const factorial = (n) => {
  if (n === 0) {
    return 1;
  }
  else {
    return n * factorial(n - 1);
  }
}

const answer = factorial(3);
Требования рекурсии
  1. Простой базовый случай, или терминальный сценарий, или терминальное условие. Простыми словами, когда остановиться. В нашем примере это был 0: мы остановили вычисление факториала, когда достигли 0.
  2. Правило передвижения по рекурсии, углубление. В нашем случае, это было n * factorial(n-1).
Ожидание умножения
Ничего не умножается, пока мы спускаемся к базовому случаю factorial(0). Затем мы начинаем подниматься обратно, по одному шагу.

factorial(3);
3 * factorial(2);
3 * 2 * factorial(1);
3 * 2 * 1 * factorial(0);
3 * 2 * 1 * 1;
3 * 2 * 1
3 * 2;
6;
Примечание
Заметьте, что 0! это 1, а простой базовый случай для n! это 0! В этом уроке мы пропустили такой случай, чтобы сократить рекурсию на один вызов и на одну коробку, поскольку 1 * 1 — это, в любом случае — 1.
Просто ради забавы
У программистов есть одна шутка: "Чтобы понять рекурсию, нужно понять рекурсию". Google, кажется, любит такие шутки. Попробуйте погуглить "рекурсия" и зацените верхний результат поиска ;-)
Дополнительные материалы
Упражнение
Допишите (с использованием рекурсивного процесса) функцию sequenceSum(), которая находит сумму последовательности целых чисел. Последовательность задается двумя значениями: begin - начало последовательности, end - конец последовательности. Например: begin = 2 и end = 6 дают нам такую последовательность 2, 3, 4, 5, 6. Сумма такой последовательности будет: 20.

import sequenceSum from './sequenceSum';
 
sequenceSum(1, 5); // 1 + 2 + 3 + 4 + 5 = 15
sequenceSum(4, 10); // 4 + 5 + 6 + 7 + 8 + 9 + 10 = 49
sequenceSum(-3, 2); // (-3) + (-2) + (-1) + 0 + 1 + 2 = -3

Подсказки
  • Последовательность, в которой begin > end, не содержит ни одного числа, т.е. является "пустой". Вычислить сумму чисел такой последовательности не представляется возможным, в этом случае возвращаем NaN
  • Сумма чисел последовательности, в которой begin === end, равна begin (или end)

// NaN (т.к. это "пустая" последовательность)
sequenceSum(7, 2);
 
// 0 (т.к. это единственное число, входящее в последовательность)
sequenceSum(0, 0);
// 6 (т.к. это единственное число, входящее в последовательность)
sequenceSum(6, 6);

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