Как работает эта рекурсивная инструкция?

Question

У меня есть два рекурсивных утверждения, которые делают то же самое, я понимаю, как работает первый, но я запутался во втором случае.

1)

def recurPower(base, exp): 
''' 
base: int or float. 
exp: int >= 0 

returns: int or float, base^exp 
''' 
# Base case is when exp = 0 
if exp <= 0: 
    return 1 

# Otherwise, exp must be > 0, so return 
# base* base^(exp-1). This is the recursive case. 
return base * recurPower(base, exp - 1) 

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

2)

def recurPowerNew(base, exp): 
''' 
base: int or float. 
exp: int >= 0 

returns: int or float; base^exp 
''' 
# Base case is when exp = 0 
if exp <= 0: 
    return 1 

# Recursive case 1: exp > 0 and even 
elif exp % 2 == 0: 
    return recurPowerNew(base*base, exp/2) 

# Otherwise, exp must be > 0 and odd, so use the second 
# recursive case. 
return base * recurPowerNew(base, exp - 1) 

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

do параметры возвращают значение, если в методе нет тела?

Answer 1

Первые параметры не возвращают значения, функции выполняются.

Во-вторых, я вижу, где вы можете запутаться с рекурсивной проблемой. Рекурсия не требует, чтобы была включена переменная. Пока рекурсия дойдет до базового случая, она вернет значение.

Например, это бесполезная рекурсивная функция, которая возвращает 1 для любого целого числа.

def foo(n): 
    if n <= 1: 
    return 1 
    else: 
    return foo(n-1) 

Foo возвращает 1 для любого целого п, поскольку в конечном итоге путем вычитания одного из целого числа мы достигнем основного случая п < 1.

С рекурсивными задачами ключа думать о базе и убедитесь, что вы приближаетесь к базовому регистру на каждой итерации.

В обеих ваших рекурсивных функциях базовый регистр является показателем нуля. Вторая рекурсивная формула просто принимает ярлык для базового случая всякий раз, когда n четно. Для каждой четной мощности вы можете просто вычислить квадрат основания и вырезать мощность пополам, потому что x^n = (x^2)^(n/2)

Работа через пример может дать понять.

Staring с

recurPowerNew(2, 10) 

, потому что ехр = 10, что даже, первое возвращаемое значение будет:

recurPowerNew(2 * 2, 5) 

это, пользуясь тем, что 2^10 = (2^2)^5. Теперь мы должны оценить новую функцию возврата. Несмотря на то, что мы только сгенерировали новую функцию, мы продвинулись к базовому случаю exp = 0. Поэтому в итоге мы ожидаем получить ответ.

Теперь у нас есть нечетная база, так что возвращаемое значение будет:

4 * recurPowerNew(4, 4) 

Теперь мы снова имеет функцию, что мы должны оценить, но это даже так он просто возвращает новую функцию.

4 * recurPowerNew(4 * 4, 2) 

Еще раз.

4 * recurPowerNew(16 * 16, 1) 

Нечетная функция, поэтому мы получаем еще один фактор.

4 * (256 * recurPowerNew(256, 0)) 

А теперь мы находимся в базовом корпусе и больше нет рекурсии.

4 * 256 * 1 

и мы можем оценить результат и получить

1024 

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

Answer 2

Давайте рассмотрим пример:

print recurPowerNew(3, 4) 

base так это 3 и exp равно 8. Это будет падать в случае вы обеспокоены, и называют:

return recurPower(9, 2) 

... который будут также попадать в один и тот же случай, а также позвонить по телефону

return recurPower(81, 1) 

ah-ha! Это странный случай. Так что это будет вызывать:

return 81 * recurPower(81, 0) 

Второй член умножения 1, так что мы возвращаем 81 весь путь стек. Если вы будете следовать этому, он также будет работать для чисел, которые не являются сильными из двух.

Дело в том, что это много более эффективно, чем первый метод. Он будет создавать один или два кадра стека на бит экспонента. Первый метод будет производить exponent стоп-кадров!

Кстати, второй пример может быть еще более эффективным, заметив, что в случае, когда показатель нечетно, вычитая одно даст еще показатель, таким образом, мы можем просто обрабатывать, которые непосредственно:

 return base * recurPowerNew(base*base, exp // 2) 

(используйте / вместо // при использовании Python 2).