Если видео недоступно для просмотра, попробуйте выключить блокировщик рекламы.

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

https://goo.gl/3ggX0S

Важно понять

Очень важно понять отличия между рекурсией, рекурсивным процессом и итеративным процессом. Вот подробное объяснение в блоге Хекслета.

Важные заметки

Обратите внимание, что условие в iter функции не включает ветвь else. Поэтому, если условие (counter === 1) не удовлетворяется, происходит переход к следующей строке и выполняется return iter(counter - 1, counter * acc).

const iter = (counter, acc) => {
  if (counter === 1) {
    return acc;
  }
  return iter(counter - 1, counter * acc);
};

Это работает, потому что когда инструкция return исполнена, экземпляр функции выплёвывает значение и исчезает. Больше ничего не будет происходить после того, как выполнится return.

Поэтому, когда условие удовлетворяется, происходит выполнение return acc, а второй возврат уже не происходит.

Вот ещё пример:

const someFunction = (a) => {
  return 100;
  return a;
  return 4123123;
};

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

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

Вызовем функцию из предыдущего урока:

factorial(3);           // don't multiply anything here
3 * factorial(2);       // don't multiply anything here
3 * 2 * factorial(1);   // don't multiply anything here
3 * 2 * 1;              // finally start multiplying
3 * 2;
6;

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

Вся информация о вычислениях, обо всём, что запоминает программа в любой конкретный момент (вычислениях, константах, функциях), называется состоянием. Множество проблем в программировании рождается из необходимости справиться с состоянием.

Суть итеративного процесса — вычисление с фиксированным количеством состояний.

const factorial = (n) => {
  const iter = (counter, acc) => {
    if (counter === 1) {
      return acc;
    }
    return iter(counter - 1, counter * acc);
  };

  return iter(n, 1);
};

Идея:

  1. Считаем от n до 1
  2. Берем число из предыдущего шага
  3. Умножаем это число на текущее число
  4. Передаем его в новый шаг
  5. Когда counter достигает 1, число передаётся из предыдущего шага в ответ

Нам нужно с чего-то начать, потому что шаг 2 требует число из предыдущего шага, и мы начинаем с 1, потому что тогда n * 1 будет просто n:

return iter(n, 1);

Вот так выглядят вызовы iter, когда происходит вычисление 3!:

iter(3, 1);   // iter(3 - 1, 1 * 3);
iter(2, 3);   // iter(2 - 1, 2 * 3);
iter(1, 6);   // counter === 1, return 6
6;
Итеративный процесс в целом:
  1. Определить начальное состояние. В нашем случае мы делаем первый вызов iter с n и 1. Это начальное состояние.
  2. ​Проверить терминальный сценарий. Мы убеждаемся, что counter это 1 и останавливаем рекурсию, когда он достигает значения 1.
  3. ​Определить новое состояние. Это то, как продвигается процесс. В нашем случае мы делаем ещё один вызов iter с уменьшенным counter и умноженным accumulator. Два этих новых числа определяют новое состояние.
  4. Повторить шаг 2.​
Резюме
  1. Рекурсия — это когда что-то содержит себя в своём описании.
  2. Рекурсивный процесс — это процесс обработки данных с отложенными вычислениями.
  3. Итеративный процесс — это процесс вычисления, когда состояние может быть описано фиксированным количеством значений.

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

Рекурсию можно использовать разными способами: тот, который мы рассматривали в предыдущем уроке, называется рекурсивным процессом. Сегодняшний урок будет более понятен, если вы уже разобрались с предыдущей темой и выполнили упражнение.

Другой способ использования рекурсии в коде, называется итеративным процессом. Название запутывает: и рекурсивный и итеративный процесс — оба описывают рекурсию.

Помните наборы вызовов из предыдущего урока. Каждый новый созданный экземпляр, или ящик функции factorial ожидает от следующего экземпляра, что тот сделает возврат какого-нибудь значения. Никакого вычисления не производится, пока мы не спустимся до конца, к базовому случаю. Только тогда мы получим 1 и начнём выполнять умножения в обратном порядке: 1 умноженная на 2 — это 2, затем 3 умножается на два, получается 6.

С факториалом 3 никаких проблем, но представьте, что нужен факториал 100. Программе потребуется хранить в памяти множество чисел из-за откладывания всех операций умножения. Откладывание здесь — ключевое слово: суть рекурсивного процесса в откладывании вычислений до самого конца. Ничего не будет умножаться, пока процесс не спустится к базовому случаю, а если его остановить, программа ничего не будет знать и вы не получите никакой полезной информации, так как не дадите ей полностью закончить задачу. Рекурсивный процесс похож на человека, который выполняет работу за всю неделю в пятницу после обеда.

Вся эта информация о вычислениях называется состоянием. Всё, что ваша программа помнит в конкретный момент времени — это состояние: вычисления, константы, функции. И очень часто состояние — это причина самых разных проблем в программировании.

Оставлять все дела на пятничный полдень — не лучший способ работать. Способ получше — делать понемногу в понедельник, ещё немного во вторник и дальше в том же духе. Это итеративный процесс: когда работа распределяется равномерно на всю неделю.

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

Вот код.

const factorial = (n) => {
  const iter = (counter, acc) => {
    if (counter === 1) {
      return acc;
    }
    return iter(counter - 1, counter * acc);
  };

  return iter(n, 1);
};

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

Функция факториала содержит в себе другую функцию. Помните, определения функций — это не сами ящики, а всего лишь их описания. Внутренняя функция iter принимает два аргумента: counter и accumulator. Counter отслеживает движение от n до 1. А accumulator — текущий результат умножения чисел от n до 1. Если counter достигает 1, accumulator возвращается — в этот момент он будет равен конечному ответу.

После того, как функция определена, у нас остаётся единственная строка в функции факториала: вернуть результат вызова функции iter с n и 1 в качестве аргументов.

Давайте запустим factorial(3). Единственная строка, которая на самом деле запускается в функции factorial это return iter(n, 1). Она хочет вернуть и завершиться, но ей нужно получить значение от функции iter.

Создается ящик iter. Он принимает 3 и 1. Внутри ящика iter 3 известно как counter, а 1 как acc. counter не равно 1, поэтому первое условие не выполняется. Затем он хочет сделать возврат, но ему необходимо получить значение от нового экземпляра iter.

Это самая важная часть: новый ящик вызывается с counter уменьшенным на 1, потому что мы прошли один шаг, а accumulator был умножен на counter.

Создаётся новый ящик iter. Он принимает 2 и 3 — counter и accumulator. Counter не равен 1, поэтому он пытается вернуть значение, но не может — ему нужно получить значение от нового экземпляра iter , вызванного с 2 - 1 в качестве первого аргумента, и 2 * 3 в качестве второго. Мы ещё не закончили, но выполнили полезное умножение — 2 * 3 это одно из умножений, необходимых для нахождения 3!

Создаётся новый iter ящик. Он принимает 1 и 6. Теперь первое условие удовлетворено, поэтому этот ящик просто возвращает accumulator, число 6.

Затем значение 6 просачивается в первый iter ящик, затем в ящик факториал, а затем возвращается в виде ответа.

Так выглядят вычисления шаг за шагом:

iter(3, 1); // iter(3 - 1, 1 * 3);
iter(2, 3); // iter(2 - 1, 2 * 3);
iter(1, 6); // counter === 1, return 6
6;

В любой момент программе необходимо помнить состояние, но его размер всегда неизменный — всего два числа.

Подобный итеративный процесс в целом может быть описан так:

  1. Определить начальное состояние. В нашем случае мы делаем первый вызов iter с n и 1. Это начальное состояние.
  2. Проверить терминальный сценарий. Мы проверяем, не равен ли counter числу 1 и останавливаем рекурсию, когда он принимает значение 1.
  3. Определить новое состояние. Это то, как процесс двигается вперед. В нашем случае мы делаем ещё один вызов iter с уменьшенным counter и умноженным accumulator. Два этих новых числа определяют новое состояние.
  4. Повторить шаг 2.

И эта штука повторяется, пока не доберётся до терминального сценария.

Давайте повторим вкратце.

  1. Рекурсия — это когда что-то содержит себя в своём описании.
  2. Рекурсивный процесс — это процесс вычисления с отложенными вычислениями.
  3. Итеративный процесс — это процесс вычисления, когда состояние может быть описано фиксированным количеством значений.

Теперь, после короткого тестового задания будет вероятно самое сложное упражнение этого курса. Но я уверен, что вы его раскусите. А когда вы это сделаете, вы почувствуете себя немного героем, как это было со мной.

Мы учим программированию с нуля до стажировки и работы. Попробуйте наш бесплатный курс «Введение в программирование» или полные программы обучения по Node, PHP, Python и Java.

Хекслет

Подробнее о том, почему наше обучение работает →