Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

1 В видео есть неточность: в формуле вычисления факториала и в коде, который на ней основан, не учитывается, что для 0 (нуля) тоже можно вычислить факториал - он равен 1 (единице). Исправленный код есть ниже в конспекте.

2 <h2>Транскрипт урока</h2>

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

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

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

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

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

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

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

10 Вот код.

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

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

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

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

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

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

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

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

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

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

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

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

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

24 <ol><li>Определить начальное состояние. В нашем случае мы делаем первый вызов iter с n и 1. Это начальное состояние.</li>

25 <li>Проверить терминальный сценарий. Мы проверяем, не равен ли counter числу 1 и останавливаем рекурсию, когда он принимает значение 1.</li>

26 <li>Определить новое состояние. Это то, как процесс двигается вперед. В нашем случае мы делаем еще один вызов iter с уменьшенным counter и умноженным accumulator. Два этих новых числа определяют новое состояние.</li>

27 <li>Повторить шаг 2.</li>

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

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

30 <ol><li>Рекурсия- это когда что-то содержит себя в своем описании.</li>

31 <li>Рекурсивный процесс- это процесс вычисления с отложенными вычислениями.</li>

32 <li>Итеративный процесс- это процесс вычисления, когда состояние может быть описано фиксированным количеством значений.</li>

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

34 <h2>Примечание</h2>

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

36 <h2>Дополнение к уроку</h2>

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

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

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

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

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

42 <h2>Выводы</h2>

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

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

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

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

47 Идея:

48 <ol><li>Считаем от n до 1</li>

49 <li>Берем число из предыдущего шага</li>

50 <li>Умножаем это число на текущее число</li>

51 <li>Передаем его в новый шаг</li>

52 <li>Когда counter достигает 1, число передается из предыдущего шага в ответ</li>

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

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

55 <h3>Итеративный процессв целом:</h3>

56 <ol><li>Определить начальное состояние. В нашем случае мы делаем первый вызов iter с n и 1. Это начальное состояние.</li>

57 <li> Проверить терминальный сценарий. Мы убеждаемся, что counter это 1 и останавливаем рекурсию, когда он достигает значения 1.</li>

58 <li> Определить новое состояние. Это то, как продвигается процесс. В нашем случае мы делаем еще один вызов iter с уменьшенным counter и умноженным accumulator. Два этих новых числа определяют новое состояние.</li>

59 <li>Повторить шаг 2. </li>

60 </ol><h3>Резюме</h3>

61 <ol><li>Рекурсия- это когда что-то содержит себя в своем описании.</li>

62 <li>Рекурсивный процесс- это процесс обработки данных с отложенными вычислениями.</li>

63 <li>Итеративный процесс- это процесс вычисления, когда состояние может быть описано фиксированным количеством значений.</li>

64 </ol>