Экспоненциальный рекурсивный

Question

Я изучаю это возведение в степень Рекурсивный алгоритм, он работает хорошо. Но я не понимаю, почему это работает? Потому что я ожидаю, что всегда возвращает 1,1,1 ... если n даже потому, что a не умножается на return.
Когда я пытаюсь recPower(3,2) и печати шаг за шагом фактор, это будет так:

Но почему 3 выйдет?

def recPower(a, n): 
    # raises a to the int power n 
    if n == 0: 
     return 1 
    else: 
     factor = recPower(a, n//2) 
     if n%2 == 0: # n is even 
      return factor * factor 
     else:  # n is odd 
      return factor * factor * a 

Answer 1

Просто следуйте шаг за шагом:

recPower(3, 2) 

n != 0 так идти вниз еще ветвь:

factor = recPower(3, 2//2) 

Который является:

recPower(3, 1) 

В этом шаге рекурсии n != 0 мы следуем за ветвями else else, 1%2 != 0, поэтому мы следуем за веткой второго. Поэтому коэффициент равен 1, и a == 3.

возвращаемое значение этого шага, следовательно:

factor * factor * a 

или

1 * 1 * 3