Возведение в степень
Следуем рекуррентной формуле и останавливаемся при нулевом показателе.
Как к ней подойти
Потренируйтесь выделять повторяющуюся логику в функцию и находить условие остановки рекурсии.
Функция получает аргументы и возвращает результат через return. Рекурсия разбивает задачу на меньшую такую же задачу; без базового случая вызовы не остановятся. Проверьте, что каждый шаг действительно приближает к нему.
Каждый вызов уменьшает показатель на единицу; при возврате выполняется умножение.
Проверьте перед запуском
- Для больших n оба варианта достигают предела глубины рекурсии Python; n=0 возвращает 1.
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Прямая рекурсия
Каждый вызов уменьшает показатель на единицу; при возврате выполняется умножение.
def power(a, n):
if n == 0:
return 1
return a * power(a, n - 1)
print(power(float(input()), int(input())))
Время: O(n). Память: O(n) стек.
Другой способ: Рекурсия с накопителем
Произведение переносится в аргумент следующего вызова. Циклов и операции степени нет; Python не устраняет хвостовые вызовы.
def power(a, n):
def multiply(k, product):
if k == 0:
return product
return multiply(k - 1, product * a)
return multiply(n, 1)
print(power(float(input()), int(input())))
Время: O(n). Память: O(n) стек.