algorithm - 我对幂函数中的递归感到困惑

Question

以下是获得权力的代码(数学)。

1. > 我很困惑，看起来每个问题都被分成一个子问题，每个子问题的大小都是两个，所以它没有形成一棵树，因为通常对于递归“树”你需要两次递归调用。只有一次递归调用，它就像一个简单的列表。 .但它是一个递归函数，阶乘和许多其他递归函数形成树，它们的递归看起来是一样的。

2.如果是一棵树，那么它是遍历所有路径还是单条路径？

     public int GetPower(int k, int n)
     {
     if (n == 0)
     {
      return 1;
     }
     else {
         int t = GetPower(k, n / 2);
          if((n%2)==0)
          {
            return t*t;                
           }
          else{
            return k*t*t;  
           }
         }
     }

请帮助我，我的困惑需要一些解释。

编辑

              (2,20)    ->    (2,10)  ->     (2,5)  ->    (2,2)   ->  (2,1)  ->   (2,0)
    1048576 <- 1024     <-     32     <-     2^4*2  <-      2*2   <-    2    <-     1

Answer 1

当您想计算 GetPower(2,6) 时，您需要 2^6 的答案。想象一下，如果您得到 2^3 的答案是 8，您会很高兴。现在您只需乘以 2^3 * 2^3 =8*8=64。

这是使用的逻辑。

对于奇数幂，例如:

2^5

我们计算 2^2 的答案并执行:

2 * 2^2 * 2^2

非常简单的技巧，但将时间复杂度从 O(N) 更改为 O(log N)，其中 N 是幂。