递归指数运算器的输出和复杂度

Question

def exp3(a,b): 
     if b == 1: 
      return a 
     if (b%2)*2 == b: 
      return exp3(a*a, b/2) 
     else: return a*exp3(a,b-1) 

这是一个递归指数运算程序。

问题1：

如果b为偶数，它将exceute（B％2）2 ==湾如果b为奇数，它会exceute一个 EXP3（A，B-1）。我的程序没有问题。如果b为4，（4％2）* 2 = 0，和0是不等于b。所以我无法理解如何计算偶数时的b值。

问题2：

我想calucate在程序步数。所以根据我的教科书，我可以得到如下的形式。 B还送吨（B）= 6 + T（B/2） b奇数T（B）= 6 + T（B-1） 为什么是第一数目6？我怎样才能在开始时得到数字3？

Answer 1

你(b%2)*2 == b测试是不正确的。我想你想b % 2 == 0测试是否b是偶数。该代码仍然得到正确的答案，因为另一个递归案例（仅适用于奇数b值）也适用于偶数（这只是效率较低）。

至于你的其他问题，我不知道那里的6无论从未来。这很大程度上取决于你计算的“步骤”。通常，根据“大O”值而不是具体数字来讨论性能是非常有用的。