Вопрос по рекурсии Python

Question

Подскажите, пожалуйста, почему при выполнении кода на степень:

def power(a, n):
    if n == 0:
        return 1
    else:
        return a * power(a, n - 1)

print(power(4, 8))

Рекурсия работает правильно, а при коде ускоренного возведения в степень (aⁿ = (a²)ⁿ/² при четном n):

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

print(power(4, 8))

Не прекращается после строки if n == 0:. а продолжает прыгать между if elif else, и делить / отнимать n. И вместо "ускоренного возведения" происходит раза в 2 больше рекурсий, чем при простом перемножении.

Answer 1

Проблема в том, что вы 2 раза вызываете функцию (power(a, (n // 2)) * power(a, (n // 2))). Из-за этого они выполняются независимо и весь смысл ускорения теряется. Обычно эта функция выглядит так:

def power(a, n):
    if n == 0: 
        return 1
    if n % 2 == 0: # <--- заменил elif на if
        return power(a*a, (n // 2)) # <---
    # <--- убрал elif
    return a * power(a, n - 1)

Или так:

def power(a, n):
    if n == 0: 
        return 1
    if n % 2 == 0: # <--- заменил elif на if
        return power(a*a, (n // 2)) # <---
    # <--- убрал elif
    return a * power(a*a, (n-1)//2) # <--- изменил вызов

UPD Однако, спасибо Stanislav Volodarskiy, стоит использовать не a*a, а power(..)**2:

def power(a, n):
    if n == 0: 
        return 1
    if n % 2 == 0:
        return power(a, (n // 2))**2
    return a * power(a, n - 1)

def power(a, n):
    if n == 0: 
        return 1
    if n % 2 == 0:
        return power(a, (n // 2))**2
    return a * power(a, (n-1)//2)**2

Answer 2

Анализ производительности. Для простоты примем что n - степень двойки. В этом случае функцию можно упростить до такой:

def power(a, n):
    if n == 1:
        return a
    if n % 2 == 0:
        return power(a, n // 2) * power(a, n // 2)

По времени работы она не отличается от вашей, зато анализировать её проще. Пусть T(k) - время работы для n = 2^k. Тогда:

T(0) = 1
T(k + 1) = 2T(k) + <время умножения> + <мелочи>

Если время умножения и мелочи отбросить, получится:

T(0) = 1
T(k + 1) >= 2^T(k)

По индукции получаем:

T(k) >= 2^k = n

То есть, сложность новой функции линейная (или хуже) по n в случае когда n степень двойки. Для не-степеней двойки доказывается тот же результат.

Переделаем код:

def power(a, n):
    if n == 1:
        return a
    if n % 2 == 0:
        return power(a, n // 2) ** 2

Уравнение для этого случая лишилось множителя двойки:

T(k + 1) = T(k) + <время умножения> + <мелочи>

Если, для простоты, опустить времена умножений, то получим уравнение T(k) >= k = log n. Сложность стала близка к логарифмической!

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

P.S. Быстрый код в вашем стиле выглядел бы так:

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

БЛОГ НА HUSL

Вопрос по рекурсии Python

Ответы (2 шт):