Рекурсию можно использовать разными способами: тот, который мы рассматривали в предыдущем уроке, называется рекурсивным процессом. Данный урок будет более понятен, если вы уже разобрались с предыдущей темой и выполнили упражнение.
Другой способ использования рекурсии в коде называется итеративным процессом. Название запутывает: и рекурсивный и итеративный процесс — оба описывают рекурсию.
Помните наборы вызовов из предыдущего урока? Каждый новый созданный экземпляр, или ящик функции factorial(), ожидает от следующего экземпляра, что тот сделает возврат какого-нибудь значения. Никакого вычисления не производится, пока мы не спустимся до конца, к базовому случаю. Только тогда мы получим 1 и начнем выполнять умножения в обратном порядке: 1 умноженная на 2 — это 2, затем 3 умножается на два, получается 6.
С факториалом 3 никаких проблем, но представьте, что нужен факториал 100. Программе потребуется хранить в памяти множество чисел из-за откладывания всех операций умножения. Откладывание здесь — ключевое слово: суть рекурсивного процесса в откладывании вычислений до самого конца. Ничего не будет умножаться, пока процесс не спустится к базовому случаю, а если его остановить, программа ничего не будет знать и вы не получите никакой полезной информации, так как не дадите ей полностью закончить задачу. Рекурсивный процесс похож на человека, который выполняет работу за всю неделю в пятницу после обеда.
Вся эта информация о вычислениях называется состоянием. Все, что ваша программа помнит в конкретный момент времени — это состояние: вычисления, константы, функции. И очень часто состояние — это причина самых разных проблем в программировании. Оставлять все дела на пятничный полдень — не лучший способ работать. Способ получше — делать понемногу в понедельник, еще немного во вторник и дальше в том же духе. Это итеративный процесс: когда работа распределяется равномерно на всю неделю. Давайте запишем ту же функцию факториала используя итеративный процесс. Идея в том, чтобы не откладывать умножения, а умножить два числа сразу и передать результат в следующий шаг.
Вот код.
def factorial(n):
if n == 0:
return 1
def 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
В любой момент программе необходимо помнить состояние, но его размер всегда неизменный — всего два числа.
Подобный итеративный процесс в целом может быть описан так:
- Определить начальное состояние. В нашем случае мы делаем первый вызов
iter()сnи 1. Это начальное состояние - Проверить терминальный сценарий. Мы проверяем, не равен ли
counterчислу 1 и останавливаем рекурсию, когда он принимает значение 1 - Определить новое состояние. Это то, как процесс двигается вперед. В нашем случае мы делаем еще один вызов
iter()с уменьшеннымcounterи умноженнымaccumulator. Два этих новых числа определяют новое состояние - Повторить шаг 2
И эта штука повторяется, пока не доберется до терминального сценария.
Давайте повторим вкратце.
- Рекурсия — это когда что-то содержит себя в своем описании
- Рекурсивный процесс — это процесс вычисления с отложенными вычислениями
- Итеративный процесс — это процесс вычисления, когда состояние может быть описано фиксированным количеством значений
Обратите внимание, что условие в функции iter() не включает ветвь else. Поэтому, если условие (counter == 1) не удовлетворяется, происходит переход к следующей строке и выполняется return iter(counter - 1, counter * acc).
def iter(counter, acc):
if counter == 1:
return acc
return iter(counter - 1, counter * acc)
Это работает, потому что когда инструкция return исполнена, экземпляр функции выплевывает значение и исчезает. Больше ничего не будет происходить после того, как выполнится return.
Поэтому, когда условие удовлетворяется, происходит выполнение return acc, а второй возврат уже не происходит.
Вот еще пример:
def some_function(a):
return 100
return a
return 4123123
Эта функция будет всегда возвращать 100. Две других возвращаемых инструкции никогда не выполнятся, потому что экземпляр функции уничтожается после исполнения первого возврата. Только один возврат может производиться в любом конкретном экземпляре функции.
Резюме
Вызовем функцию из предыдущего урока:
factorial(3) # ничего не происходит, вычисляем множители
3 * factorial(2) # ничего не происходит, вычисляем множители
3 * 2 * factorial(1) # ничего не происходит, вычисляем множители
3 * 2 * 1 # наконец начинаем умножение
3 * 2
6
Процесс вычисления, который создает эта функция, называется рекурсивным процессом. Основная его идея — откладывание вычисления до самого конца.
Вся информация о вычислениях, обо всем, что запоминает программа в любой конкретный момент (вычислениях, константах, функциях), называется состоянием. Множество проблем в программировании рождается из необходимости справиться с состоянием.
Суть итеративного процесса — вычисление с фиксированным количеством состояний.
def factorial(n):
if n == 0:
return 1
def iter(counter, acc):
if counter == 1:
return acc
return iter(counter - 1, counter * acc)
return iter(n, 1)
Идея:
- Считаем от n до 1
- Берем число из предыдущего шага
- Умножаем это число на текущее число
- Передаем его в новый шаг
- Когда 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
Дополнительные материалы
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
- Статья «Как учиться и справляться с негативными мыслями»
- Статья «Ловушки обучения»
- Статья «Сложные простые задачи по программированию»
- Вебинар «Как самостоятельно учиться»
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
