Введение в программирование
Итеративный процесс
В видео есть неточность: в формуле вычисления факториала и в коде, который на ней основан, не учитывается, что для 0 (нуля) тоже можно вычислить факториал — он равен 1 (единице). Исправленный код есть ниже в конспекте.
Транскрипт урока
Рекурсию можно использовать разными способами: тот, который мы рассматривали в предыдущем уроке, называется рекурсивным процессом. Сегодняшний урок будет более понятен, если вы уже разобрались с предыдущей темой и выполнили упражнение.

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

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

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

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

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

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

Вот код.

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

  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, 3 * 1);
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. Итеративный процесс — это процесс вычисления, когда состояние может быть описано фиксированным количеством значений.
Теперь, после короткого тестового задания будет вероятно самое сложное упражнение этого курса. Но я уверен, что вы его раскусите. А когда вы это сделаете, вы почувствуете себя немного героем, как это было со мной.
Дополнение к уроку
Обратите внимание, что условие в 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) => {
  if (n === 0) {
    return 1;
  }

  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, 3 * 1);
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. Итеративный процесс — это процесс вычисления, когда состояние может быть описано фиксированным количеством значений.
Дополнительные материалы
  1. Визуализация итеративного процесса
Тесты
Пройти тест
Выберите все верные утверждения:

(нужно выбрать все корректные ответы)

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

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

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

Как мы знаем из видео, при рекурсивном процессе формируется цепочка отложенных вычислений. Эта цепочка окончательно формируется при достижении терминального условия, после чего она ("цепочка") вычисляется в конкретное значение, которое и возвращается в качестве результата выполнения функции.

sum(5);

Выберите выражение, соответствующее тому, как будет выглядеть цепочка отложенных вычислений при вызове sum(5).
Неверно
Неверно
Верно!
Дальше
Проверить
Завершить тест
Проанализируйте определения функций sum1 и sum2:

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

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

Эти функции совершают одни и те же операцию.

sum1(4); // 4 + (3 + (2 + 1))
sum2(4); // ((1 + 2) + 3) + 4

Выберите верные утверждения:

(нужно выбрать все корректные ответы)
Неверно
Верно!
Дальше
Проверить
Завершить тест
Функция-однострочник sum принимает целое положительное число n и возвращает сумму всех чисел, входящих в интервал [0, n]:

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

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

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

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

Есть ли в этом определении терминальное условие? Выберите правильное утверждение
Верно!
Неверно
Неверно
Дальше
Проверить
Завершить тест
Пройти еще раз
Пройти еще раз
Пройти еще раз
Пройти еще раз
Упражнение
Реализуйте тело функции smallestDivisor(), используя итеративный процесс. Функция должна находить наименьший делитель заданного числа. Число, передаваемое в функцию, больше нуля.

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

Например, наименьший делитель числа 15 это 3.

smallestDivisor(15); // 3
smallestDivisor(17); // 17
Идея алгоритма:
  1. Попробуйте разделить число на 2.
  2. Если число делится без остатка, то это наименьший делитель.
  3. Если нет, то попробуйте следующий делитель.
  4. Если ничего не делит число без остатка, то переданное число является простым, так что его наименьший делитель — оно само (не считая 1)
Подсказки

Вспомните про оператор % (modulus or остаток от деления) из урока 5. Он вычисляет остаток от деления одного операнда на другой. Например, 11 % 5 это 1, а 10 % 2 это 0.

Так что если x % y это 0, то y делит x без остатка.