我對電源遞歸功能感到困惑

我很困惑，它看起來像每一個問題劃分爲一個子問題，每個大小兩個人，一個是因爲，通常是一個遞歸「樹」，你需要兩個遞歸調用它沒有形成一個樹。只有一次遞歸調用就像一個簡單的列表。但它是一個遞歸函數，階乘和許多其他遞歸函數形成樹，並且它們的遞歸看起來相同。

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

來源

2013-06-21 Charlie

'階乘等衆多遞歸函數形成trees'錯誤 – SLaks

1.你在說什麼？ – SLaks

@SLaks所以它沒有形成一棵樹？ – Charlie

當你想計算GetPower（2,6）你想爲2^6.Imagine你喜悅的答案，如果你給出的答案爲2^3的8.現在你只需乘以2^3 * 2^3 = 8 * 8 = 64。

這是所使用的邏輯。

對於奇數權力，如：

2^5

我們計算的2^2的答案和做：

2 * 2^2 * 2^2

很簡單的把戲，但改變從O（N）的時間複雜度到爲O（log N）其中ñ是權力。

來源

2013-06-21 18:35:03 Aravind

是的，這是創建一個隱藏的樹，它是橫貫只有一條路徑

來源

2013-07-25 18:13:51

我對電源遞歸功能感到困惑

回答

相關問題