Визуализация рекурсивного процесса

https://goo.gl/gWCcgm

Конспект урока

Представляем функции

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

Сравните:

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;
}

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

  • Определение функции — это описание коробки
  • Оригинал коробки формируется при вызове функции
  • Когда функция вызывает сама себя, создаётся новая идентичная коробка

Перестановки:

  • Количество способов перестановки n объектов равно n! (permutations)
  • n! определяется таким способом: если n = 1, то n! = 1; если n > 0, то n! = n * (n-1)!

Функция, вычисляющая факториал:

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

const answer = factorial(3);

Требования рекурсии

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

Ожидание умножения

Ничего не умножается, пока мы спускаемся к базовому случаю factorial(1). Затем мы начинаем подниматься обратно, по одному шагу.

factorial(3);
3 * factorial(2);
3 * 2 * factorial(1);
3 * 2 * 1;
3 * 2;
6;

Примечание

Заметьте, что 0! это 1, а простой базовый случай для n! это 0! В этом уроке мы пропустили такой случай, чтобы сократить рекурсию на один вызов и на одну коробку, поскольку 1 * 1 — это, в любом случае — 1.

Просто ради забавы

У программистов есть одна шутка: "Чтобы понять рекурсию, нужно понять рекурсию". Google, кажется, любит такие шутки. Попробуйте погуглить "рекурсия" и зацените верхний результат поиска ;-)

Рекомендуем посмотреть

Опциональный текст

Опциональные видео


Транскрипт урока

У нас уже есть функция 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 оно известно как n.

square хочет умножить n на n и сделать возврат. Ей никто не мешает и она делает это умножение и возврат. Мы снова внутри 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 равно 1, тогда факториал — 1, это просто. Но если n не равно 1, тогда факториал — n*(n-1)!

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

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

const answer = factorial(3);

Это может показаться странным. Мы вызываем функцию из функции, но… это та же самая функция!

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

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

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

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

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

Фуух!

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

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

Давайте проследим шаги ещё раз, но с другой точки зрения, не заглядывая в ящики. Вот как это выглядит пошагово:

factorial(3);
3 * factorial(2);
3 * 2 * factorial(1);
3 * 2 * 1;
3 * 2;
6;

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

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

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

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

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

Для продолжения нужно перейти в курс и вступить в него.