冪遞歸

Question

我學習這個冪遞歸算法，它工作得很好。 但我不明白爲什麼這個工程？ 因爲我希望總是返回1,1,1 ......如果n甚至因爲沒有在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這樣下去else分支：

factor = recPower(3, 2//2) 

那就是：

recPower(3, 1) 

在這個遞歸步驟n != 0我們遵循第一個else分支，1%2 != 0，所以我們遵循第二個else分支。因此，該因子爲1，a ==因此3.

該步驟的返回值是：

factor * factor * a 

或

1 * 1 * 3