Рекурсивное экспонирование

Question

Я пытаюсь написать небольшую программу, которая вычисляет показатели рекурсивно, и я немного застрял. Это домашнее задание, и нас попросили иметь базовый случай, когда показатель степени является нечетным числом, а показатель степени является четным. Пока у меня есть это:

def quick_power(x,n):
    if n == 0:
        return 1
    elif n % 2 != 0:
        return x * quick_power(x, n-1)
    elif n % 2 == 0:
        return quick_power(quick_power(x, n//2), 2)

И я знаю, что строка с n % 2 == 0 не такая, какой она должна быть. Любая помощь приветствуется. Благодарю.

Answer 1

Допустим, мы оцениваем quick_power(1234, 2), Оценка идет так:

1. quick_power(1234, 2)
2. quick_power(quick_power(1234, 1), 2)
3. quick_power(1234 * quick_power(1234, 0), 2)
4. quick_power(1234 * 1, 2)
5. quick_power(1234, 2)

... как вы можете видеть, он в конечном итоге начинает оценивать то, с чего мы начали, и в итоге вы получаете бесконечную рекурсию. Не давая вам решения, я советую вам подумать: если у нас есть постоянный показатель (здесь, 2), есть ли способ, которым вы можете вычислить это без необходимости делать это рекурсивно?

Answer 2

def quick_power(x,n)

if n == 0:
    return 1
elif n % 2 == 0:
    return quick_power(x * x, n / 2)
else:
    return x * quick_power(x * x, (n - 1) / 2)

Answer 3

Расширяя, что выше:

У рекурсивного алгоритма есть случаи рекурсии и базовые случаи (где вместо другой рекурсии возвращается определенный результат), как вы, вероятно, знаете...

Для этой ситуации вы рассмотрели базовые случаи n=0 и n=1. Но из ответа @icktoofay есть другой базовый случай, n=2.

Таким образом, ваш код может быть написан:

def quick_power(x,n):
    if n == 0:
        return 1
    elif n == 1:
        return x
    elif n == 2:
        return x * x
    elif n % 2 != 0:
        return x * quick_power(x, n-1)
    elif n % 2 == 0:
        return quick_power(x,n//2) * quick_power(x,n//2)

Последняя строка, как предполагается, должна быть более эффективной за счет уменьшения максимальной глубины рекурсии (до log2(n) рекурсий).