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

Question

以下是获得权力的代码（数学）。

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

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

是的，它正在创建一棵隐藏的树，它只穿过一条路径

Answer 2

当您想要计算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是幂。