На этом шаге мы рассмотрим особенности такой реализации рекурсивной функции.

Существует возможность реализовать более эффективные алгоритмы вычисления степени за логарифмическое время, если на этапе декомпозиции разбить задачу пополам - на две подзадачи в половину размера исходной. Поскольку n - неотрицательное целое число, нам понадобятся две схемы в зависимости от четности n. Если n - чётное, то согласно рекурсивному подходу процесс можно представить следующим образом:

Таким образом, чтобы получить bⁿ, результат подзадачи нужно возвести в квадрат. И наоборот, если n - нечётное, следует рассмотреть подзадачу с целочисленным размером (n - 1)/2. Её схема:

В этом случае результат подзадачи тоже возводится в квадрат, после чего нужно умножить его на основание b. С этими рекурсивными условиями и тривиальным начальным условием рекурсивная функция выглядит следующим образом:

               1,                    если n = 0,
    f (b,n)  = f(b, n/2)²,           если n > 0 и n - чётное,
               f(b, (n - 1)/2)² * b, если n > 0 и n - нечётное.

Правильная реализация линейно-рекурсивной функции показана в примере 4.3. Целочисленное деление (//) вместо вещественного деления (/) не обязательно и применено, чтобы подчеркнуть, что второй входной параметр - целое число. Кроме того, если n - нечётное, то (n - 1)//2 = n//2. Однако в коде используется первое выражение, поскольку оно математически точнее.

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

1
2
3
4
5
6
7

def power_logarithmic(b, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return power_logarithmic(b, n // 2) ** 2
    else:
        return b * (power_logarithmic(b, (n - 1) // 2) ** 2)

Архив с файлом можно взять здесь.

Время выполнения можно определить как:

           1,            если n = 0
    T(n) =            
           T(n / 2) + 1, если n > 0

где T(n) = 2 + log₂n для n > 0. Таким образом, T(n) ∈ Θ(log n). Высокая производительность достигается за счёт деления размера задачи пополам на этапе декомпозиции. При этом функция в каждом рекурсивном условии должна выполнить только один рекурсивный вызов. Например, код в примере 4.4 не выполняется за логарифмическое время, несмотря на то что декомпозиция делит задачу пополам. Проблема здесь в том, что он вычисляет результат одной и той же подзадачи дважды, используя два идентичных, но совершенно ненужных рекурсивных вызова.

Пример 4.4. Неэффективная реализация степенной функции с линейным временем выполнения

1
2
3
4
5
6
7
8

def power_alt(b, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return power_alt(b, n // 2) * power_alt(b, n // 2)    
    else:
        return (power_alt(b, (n - 1) // 2)
                * power_alt(b, (n - 1) // 2) * b)

Архив с файлом можно взять здесь.

Временная стоимость выполнения этой функции:

           1,            если n = 0
    T(n) =            
           2T(n / 2) + 1, если n > 0

где T(n) = n + 1 ∈ Θ(n). Отметим, что она аналогична времени выполнения (4.1) функции в примере 4.1. Таким образом, сверхпроизводительность, которую можно было бы получить за счёт деления размера задачи пополам, здесь утрачивается из-за двух идентичных рекурсивных вызовов в рекурсивном условии.

На следующем шаге мы рассмотрим медленное сложение.

Предыдущий шаг Содержание Следующий шаг