Функции и процессы, которые они генерируют

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

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

3.2.1 Рекурсивные функции

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

Чтобы представить рекурсивную функцию, мы начнём с преобразования английских слов в их эквиваленты на Pig Latin. Pig Latin — это секретный язык: английские слова преобразуются с помощью простого определённого правила, чтобы скрыть их значение. Считается, что Томас Джефферсон был его создателем. Эквивалент английского слова на языке Pig Latin получается путём перемещения начального согласного звука (возможно, пустого) в конец слова и добавления «ay». Таким образом, слово «pun» становится «unpay», «stout» становится «outstay», а «all» становится «allay».

>>> def pig_latin(w):
        """Return the Pig Latin equivalent of English word w."""
        if starts_with_a_vowel(w):
            return w + 'ay'
        return pig_latin(w[1:] + w[0])
>>> def starts_with_a_vowel(w):
        """Return whether w begins with a vowel."""
        return w[0].lower() in 'aeiou'

Идея, лежащая в основе этого определения, заключается в том, что эквивалент на Pig Latin слова с начальным согласным звуком и эквивалент другого слова совпадают: они создаются путём перемещения первой буквы в конец. Таким образом, эквивалент слова «sending» на Pig Latin совпадает с эквивалентом слова «endings» («endingsay»). Эквивалент слова «smother» на Pig Latin совпадает с эквивалентом слова «mothers» («othersmay»). Кроме того, перемещение начального согласного звука в конец создаёт более простую задачу с меньшим количеством начальных согласных звуков. В примере со словом «sending», перемещение «s» в конец приводит к слову, начинающемуся с гласной, и наша задача выполнена.

Даже если функция pig_latin вызывает сама себя в своём теле, определение функции pig_latin является полным и правильным.

>>> pig_latin('pun')
'unpay'

Мы можем понять, как рекурсивная функция использует нашу модель вычислительной среды для успешного вызова. Иллюстрация среды и описание выражения оценки pig_latin ('pun') показаны ниже:

Процесс оценки Python происходит следующим образом:

1. Выполняется оператор def функции pig_latin, где:
   1. Создаётся новый объект функции pig_latin и
   2. Имя pig_latin связывается с этой функцией в текущей (глобальной) среде.
2. Оператор def функции starts_with_a_vowel выполняется аналогичным образом.
3. Вычисляется вызов функции pig_latin («pun»), путём:
   1. Поиска оператора и операндов подвыражения, путём:
      1. Поиска имени pig_latin, связанного с функцией pig_latin
      2. Применения строки «pun» к операнду строкового литерала
   2. Вызова функции pig_Latin с параметром «pun», путём:
      1. Добавления расширенной среды из глобальной среды в локальную среду
      2. Связывания фактического параметра «pun» с формальным параметром w в локальной среде
      3. Выполнения тела функции pig_latin в среде, начиная с начала, где:
         1. Условное выражение в начале не действует, потому что выражение оценивается как False
         2. Возвращается последнее возвращаемое выражение pig_latin (w [1:] + w [0]), путём:
            1. Поиска имени pig_latin, связанного с функцией pig_latin
            2. Применение строки «unp» к операнду выражения
            3. Вызов функции pig_latin с параметром «unp», который будет возвращать ожидаемый результат из тела функции pig_latin после выполнения условного выражения.

Как показано в этом примере, хотя рекурсивная функция имеет циклический характер, она всё равно вызывается правильно. Функция pig_latin вызывается дважды, но каждый раз с разными параметрами. Хотя второй вызов исходит из тела самой функции pig_latin, он успешно разрешается, поскольку имя pig_latin было связано в среде до выполнения тела функции.

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

3.2.2 Анализ рекурсивных функций

Многие тела рекурсивных функций следуют общему шаблону. Тело начинается с базового условия, которое представляет собой условное выражение, определяющее поведение функции для простейшего ввода. В случае pig_latin базовое условие состоит в том, что любое слово, начинающееся с гласного, требует только добавления «ay» к параметру. Некоторые рекурсивные функции имеют несколько базовых условий.

За базовым условием следует один или несколько рекурсивных вызовов. Рекурсивный вызов имеет определённые характеристики: он должен упрощать исходную задачу. В случае pig_latin рекурсивный вызов pig_latin (w[1:] + w[0]) упрощает проблему, применяя её к слову с меньшим начальным согласным звуком — это более простая задача. Каждый успешный вызов pig_latin ещё больше упрощает задачу, пока не будет выполнено базовое условие: слово без начального согласного звука.

Рекурсивные вызовы выражают вычисления путём постепенного упрощения задачи. По сравнению с итерационными методами, которые мы использовали ранее, они обычно решают проблемы по-разному. Рассмотрим функцию fact, которая вычисляет факториал n, где fact (4) вычисляет 4! = 4·3·2·1 = 24.

Естественная реализация с использованием оператора while выполняет умножение каждого положительного числа, меньшего или равного n.

>>> def fact_iter(n):
        total, k = 1, 1
        while k <= n:
            total, k = total * k, k + 1
        return total
>>> fact_iter(4)
24

С другой стороны, факториальная рекурсия может быть выражена как fact (n-1), где fact (1) является базовым условием.

>>> def fact(n):
        if n == 1:
            return 1
        return n * fact(n-1)
>>> fact(4)
24

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

(n − 1)! = (n − 1)·(n − 2)· ... · 1
n！ = n·(n − 1)·(n − 2)· ... · 1
n! = n·(n − 1)!  

Эти две факториальные функции концептуально различны. Итерационная функция строит результат, последовательно умножая каждое выражение от базового условия 1 до окончательного общего количества. С другой стороны, рекурсивная функция непосредственно строит результат из окончательного выражения n и упрощённой задачи fact (n-1).

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

Хотя мы можем использовать нашу модель вычислений для развёртывания рекурсии, обычно рассматривать рекурсивные вызовы как абстракции функций более ясно. То есть нам не нужно беспокоиться о том, как fact (n-1) реализуется в теле функции fact; мы просто предполагаем, что он вычисляет факториал (n-1). Рассматривать рекурсивные вызовы как абстрактные функции называется «leap of faith» рекурсии. Мы определяем функции сами по себе, но полагаемся на то, что более простые случаи будут работать должным образом при проверке правильности функции. В этом примере мы полагаем, что fact (n-1) правильно вычислит (n-1)!; нам нужно только проверить, соответствует ли предположение n! действительности. Таким образом, проверка правильности рекурсивной функции становится формой индуктивного доказательства. Анализ сложности алгоритмов: асимптотические обозначения

Пусть n — параметр, который характеризует масштаб задачи, а R(n) — количество ресурсов, необходимых для решения задачи масштаба n. В предыдущем примере мы рассматривали n, как значение функции, которую нужно вычислить. Но это не единственный вариант. Например, если наша цель — вычислить приближённое значение квадратного корня из некоторого числа, то n будет количеством значащих цифр в ответе.

Обычно у задачи есть характеристики, которые можно использовать для анализа соответствующего процесса. Аналогично, R(n) может использоваться для измерения общего объёма используемой памяти, количества выполненных основных машинных операций и других параметров. Если процесс выполняет фиксированное количество операций за один раз, то время, необходимое для вычисления выражения, прямо пропорционально количеству выполненных базовых машинных операций.

Мы говорим, что R(n) = Θ(f(n)), если существуют независимые от n константы k1 и k2, такие что для достаточно больших значений n:

k1·f(n) <= R(n) <= k2·f(n).

Это означает, что для больших n значение R(n) находится между двумя значениями, пропорциональными f(n):

• нижней границей k1·f(n),
• верхней границей k2·f(n).

Например, количество шагов, необходимых для вычисления факториала n!, растёт линейно с ростом n, поэтому этот процесс имеет сложность Θ(n). Мы также видим, что рекурсивная реализация функции fact требует пространства Θ(n). Напротив, итеративная реализация fact_iter использует примерно такое же количество шагов, но требует постоянного пространства. Здесь мы говорим, что пространство имеет сложность Θ(1).

Количество шагов в нашем рекурсивном алгоритме для вычисления чисел Фибоначчи растёт экспоненциально с увеличением входного значения n. Особенно интересно, что n-е число Фибоначчи является ближайшим целым числом к значению φ^(n-2)/√5, где φ — золотое сечение:

φ = (1 + √5)/2 ≈ 1.6180.

Также мы можем видеть, что количество шагов растёт вместе с возвращаемым значением, поэтому рекурсивный процесс требует Θ(φ^n) шагов, где φ^n — функция, растущая экспоненциально.

Сложность только даёт общее представление о поведении процесса. Например, процессы, требующие n^2 шагов, 1000·n^2 шагов или 3·n^2+10·n+17 шагов, имеют сложность Θ(n^2). В некоторых случаях анализ сложности слишком груб, чтобы сделать выводы о двух возможных реализациях функции.

Однако сложность предоставляет полезный способ предсказать, как изменится поведение процесса при изменении масштаба задачи. Для процессов со сложностью Θ(n) (линейных), удвоение масштаба задачи приводит к удвоению требуемых ресурсов. Для экспоненциальных процессов, каждый шаг увеличения масштаба задачи приводит к увеличению используемых ресурсов в фиксированное число раз. Следующий пример показывает алгоритм со сложностью, равной логарифму, так что удвоение масштаба задачи увеличивает используемые ресурсы на постоянную величину.

3.2.6 Пример: возведение в степень

Рассмотрим задачу возведения числа в степень. Мы хотим иметь функцию, которая принимает основание b и показатель степени n в качестве аргументов и вычисляет b^n. Один из способов — определить это рекурсивно:

b^n = b·b^(n−1)
b^0 = 1

Это можно перевести в рекурсивную функцию:

def exp(b, n):
    if n == 0:
        return 1
    return b * exp(b, n−1)

Этот процесс линейный и требует Θ(n) шагов и пространства. Как и в случае с факториалом, мы можем написать эквивалентную линейную итеративную форму, которая требует аналогичного количества шагов, но только фиксированного пространства.

def exp_iter(b, n):
    result = 1
    for _ in range(n):
        result = result * b
    return result

Можно вычислить степень более эффективно, используя последовательное возведение в квадрат. Например, мы вычисляем b^8 следующим образом:

b·(b·(b·(b·(b·(b·(b·b))))))

Используя три умножения, мы получаем:

b^2 = b·b
b^4 = b^2·b^2
b^8 = b^4·b^4

Этот метод хорошо работает для степеней двойки. Мы можем использовать это правило возведения в степень для ускорения вычислений:

Эту идею можно выразить в виде рекурсивной функции:

def square(x):
    return x*x
def fast_exp(b, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return square(fast_exp(b, n//2))
    else:
        return b * fast_exp(b, n−1)
fast_exp(2, 100)

Функция fast_exp генерирует процесс, сложность которого растёт логарифмически с ростом n. Чтобы понять это, заметим, что использование fast_exp для вычисления b^2n требует только одного дополнительного умножения по сравнению с вычислением b^n. Таким образом, мы можем вычислить степени, которые увеличиваются вдвое при каждой новой операции умножения. Следовательно, количество умножений, необходимых для вычисления показателя степени n, растёт как логарифм n с основанием 2. Этот процесс имеет сложность Θ(log n). Разница между Θ(log n) и Θ(n) становится существенной при больших значениях n. Например, для n=1000 fast_exp требуется всего 14 умножений вместо 1000.