SICP. Простые процессы

В прошлой статье мы превратили функцию в чёрный ящик, теперь поговорим о его выполнении.

Когда функция вызывается из основного потока, она создаёт процесс для своего выполнения.
Прописывая функцию, мы пишем def something(a, b), то есть делаем шаблон с местами для подстановки фактических значений. В основном потоке вызываем something(9, 3), начинает выполняться код из определения этой функции.

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

Рекурсивный процесс

Для примера возьмём поиск факториала. Его математическое определение выглядит так:
n! = n × (n − 1) × (n − 2) ... 2 × 1. Если перевести это в код, то получится такая функция

Она описана декларативно, как и определение в математике.
Код можно писать в декларативном и императивном стиле, мы писали статью про эти стили и чем они отличаются.

При запуске функция создаст рекурсивный процесс для вычисления факториала.

Процесс начинает сворачиваться когда вызвана последняя функция

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

Вычисление факториала можно переписать в императивном стиле. Тогда при запуске функция будет создавать итеративный процесс.

Итеративный процесс

Код в императивном стиле будет использовать аккумулятор, это переменная где будем хранить значение факториала на каждом шаге.

Алгоритм такой:

  1. Проверяем значение n, если оно равно 1 — возвращаем значение acc, иначе вызываем функцию ещё раз и уменьшаем n на 1
  2. Умножаем текущее значение n на acc. Пайтон работает с аппликативным порядком вычислений, поэтому значение acc умножится на n, а не на n − 1
    Аппликативный и нормальный порядок вычислений мы разбирали в первой статье по СИКПу.

Чтобы вычислить факториал, функция создаст итеративный процесс.

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

Термины связанные с рекурсией

Когда начинаешь разбираться с рекурсией, то тонешь в куче терминов: рекурсия, рекурсивная функция, рекурсивный процесс. Сейчас поясним:
Рекурсия — математическая концепция. Она объясняет, что объекты могут состоять сами из себя. Посмотрите примеры в статье про рекурсивный и итеративный процесс.
Рекурсивная функция — функция, которая в своём теле вызывает сама себя. Если говорят, что функция рекурсивна, значит в её коде есть вызов самой себя. Например, рекурсивный поиск чисел Фибоначчи
Рекурсивный и итеративный процесс — процессы которые создаёт рекурсивная функция. Какой процесс получится, зависит от кода функции.

Для примера возьмём нашу функцию factorial_iter, её можно описать так: «рекурсивная функция factorial_iter создаёт итеративный процесс». Теперь по-человечески:

  • «рекурсивная функция», значит в теле factorial_iter она вызывает сама себя
  • «создаёт итеративный процесс», каждый раз функция вызывает себя с двумя переменными: они описывают состояние на каждом шаге, ещё в теле функции описаны условие выхода и изменение переменных между шагами.

Итеративному процессу нужно намного меньше памяти, чем рекурсивному, но в некоторых ЯП это не так из-за хвостовой рекурсии.

Хвостовая рекурсия

Некоторые реализации ЯП сделаны так, что итеративный и рекурсивный процесс тратят одинаковый объём памяти, поэтому компиляторы таких языков переписывают код итеративных процессов через циклы, например так делает Пайтон.

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

Древовидная рекурсия

Древовидная рекурсия — процесс, который при выполнении становится похож на дерево. Хороший пример такого процесса — рекурсивное вычисление чисел Фибоначчи.
Древовидную рекурсию можно отнести к рекурсивному процессу, но мы решили выделить её отдельно.

При выполнении этого кода, процесс вычислений разрастётся как дерево. Функции вызываются слева направо: на каждом вызове сначала выполняется левая ветка, потом правая.

Картинка красивая, но она показывает неэффективный код: много бессмысленных повторений, которые забивают память

Попробуйте вычислить на таком алгоритме 43 число Фибоначчи, у нас ушло на это почти семь минут. Мы писали статью про числа Фибоначчи и разные способы их вычисления, почитайте как можно улучшить алгоритм поиска.

Функция вызывалась почти полтора миллиарда раз чтобы вычислить число, на это она потратила 410 секунд

Древовидная рекурсия небесполезная.
Она медленно и неэффективно работает с числами, но если натравить её на иерархические объекты, то она прекрасно справится.

Поделиться
Отправить
Запинить
 25   21 д   sicp
Популярное