Re: [問題] 關於遞迴加快速度的迷思？

[Feis (永遠睡不著 @@)]

※ 引述《crazycat2 (浪無定所)》之銘言：
<deleted>
: 但因使用方式，還是以遞迴為主。
: 不經好奇若將遞迴改成static或是marco會更快嗎？

  最近也對遞迴有些疑惑, 趁此機會來跟大家討教一下, 以下是我自己的觀點跟想法:

  遞迴與迭代這兩個觀念可以在三個層次上遇到：

  1. 抽象層次: 遞迴關係 (recurrence) 與迭代關係 (iteration)
  2. 語言層次: 遞迴函式呼叫 (recursive function call) 與迴圈 (looping)
  3. 底層實作: 呼叫 (call) 與跳躍 (jump) [一般呼叫的實作會包括跳躍]

  其中這三個層次有一個直觀的串連關係。例如, 如果有一個題目在抽象層次具有遞迴關
  係, 我們就可以依照該遞迴關係去寫語言層次的遞迴函式並呼叫他。這遞迴函式呼叫在
  編譯時, 編譯器可以直觀的使用底層呼叫 (call) 類的指令去實作。遞迴關係、遞迴函
  式呼叫與底層呼叫這三個不同層次的詞可以有這樣一個直觀的串連關係。相對地，迭代
  關係、迴圈與跳躍也可以發現有類似的串連關係。只是這些串連關係並不具有強制性，
  像是迴圈也可以用來實作遞迴關係，跳躍也可以用來實作遞迴呼叫，只是可能會有一些
  其他的限制或多餘的步驟。不過大致上我們可以具有一個選擇的標準：我們希望在語言
  層次可以寫簡短且容易了解維護的程式碼, 同時希望在編譯後於底層實作上具有高的運
  作效率。

  首先，要認知在這樣的前提上，已經接受在抽象層次上我們要解決的題目是具有直觀的
  遞迴關係的，要不然我們沒必要討論這個問題 (就不要用遞迴就好)。 常見的例子像是
  要求得 Fibonacci  數列中某項的值。Fibonacci 數列最直觀的定義就是使用遞迴關係
  來表示:

    f(n) == f(n-1) + f(n-2),   (n >  1)  [遞迴關係]
    f(n) == n              ,   (n <= 1)  [邊界條件]

  因為具有遞迴關係，所以在語言層次上我們依照這樣的遞迴關係去定義一個遞迴函式並
  呼叫是再直觀不過的實作方法：

    int f(int n) {
      if (n <= 1)   return n;        // [邊界條件]
      else return f(n-1) + f(n-2);   // [遞迴關係]
    }

  但是我們也知道 Fibonacci  數列中每一項的值可以使用迴圈型的演算法算出，因為遞
  迴關係可以反向地看成是迭代關係：

    n == f(n)              ,   (n <= 1)   [初始條件]
    f(n-1) + f(n-2) == f(n),   (n >  1)   [迭代關係]

  所以當我們說『遞迴的效率比迴圈差』這個論述時，指的是在語言層次使用遞迴函式呼
  叫實作會比使用迴圈實作效率要來得差，而不是說具有遞迴關係的題目本身就象徵著效
  率不會好。

  那為什麼在語言層次使用遞迴函式呼叫實作感覺上會比使用迴圈實作差？

  最常見的範例就是跟計算 Fibonacci 數列的某項值時一樣，遞迴函式呼叫時會『重複』
  呼叫具有相同參數值的同名函式。例如要計算 f(10) 時， f(8) 就會在計算 f(10) 跟
  f(9)時都被呼叫並重新計算一次。這個會造成效率指數性的下降，也就是我們直觀地使
  用遞迴函式呼叫去實作遞迴關係時踩到的效率陷阱。

  那為什麼迴圈會是擺脫這個效率陷阱的救星呢？

    // 下面的程式碼為了做好的對應，我並沒做最簡化

    // 如果要求取 f(10) 的值:
    int main() {
      int F[10+1];
      for (int i = 0; i <= 10; ++i) {
        if (i <= 1) F[i] = i;
        else F[i] = F[i-1] + F[i-2];
      }
      // 此時 F[10] 的值就是我們要的 f(10) 的值
      printf("%d\n", F[10]);
      return 0;
    }

  這個迴圈確確實實不多不少執行了 10+1 次，看起來要比使用遞迴函式呼叫少執行了很
  多次計算 (因為我們沒有重複計算到) 。但是關鍵其實是因為這裡偷偷做了一個類似快
  取的機制 (空間換取時間)。也就是說，我們也可以依樣畫葫蘆地把遞迴函式呼叫改成:

    int f(int n, int *F, bool *visited) {
      if (visited[n]) return F[n];
      visited[n] = true;
      if (n <= 1) {
        F[n] = n;
      } else {
        F[n] = f(n-1, F, visited) + f(n-2, F, visited);
      }
      return F[n];
    }

    int main() {
      int F[10+1];
      bool visited[10+1] = {};
      printf("%d\n", f(10, F, visited));
      return 0;
    }

  我們維持了語法中的遞迴函式呼叫機制，並且通過類似快取的機制避免了重複計算，但
  是也必須為此付出一些代價：我們需要記錄是否已經計算過 (visited)。但是相對地，
  為什麼迴圈可以不用跟這裡一樣要付出記錄的代價？原因是因為遞迴關係如果要有解 (
  也就是遞迴函式呼叫如果要確定能夠結束) ，那所有遞迴函式的呼叫可以依照呼叫者跟
  被呼叫者的關係畫成一個樹的結構。我們只要確保在樹枝中比較接近樹葉的函式呼叫比
  比較接近樹根的函式呼叫先計算，那最後的結果就會正確。也就是說，我們可以將他寫
  成迴圈形式而不用記錄執行過哪些函式是因為存在一個計算的順序可以確保過程中被呼
  叫者的值會比呼叫者先被算出來。例如只要確保迴圈中 f(6) 比 f(7) 跟 f(8) 先求出
  就可以了。

  那遞迴函式呼叫難道就不能做嗎？顯然不是：

    void f(int n, int *F, int i = 0) {
      if (n < i) return;
      if (i <= 1) F[i] = i;
      else F[i] = F[i-1] + F[i-2];
      f(n, F, i+1);
    }

    int main() {
      int F[10+1];
      f(10, F);
      // 此時 F[10] 的值就是我們要的 f(10) 的值
      printf("%d\n", F[10]);
      return 0;
    }

    (確實有更簡單的方式來寫這個題目，不過跟這裡要討論的差異無關就不細寫。)

  如果這樣寫的話，在語言層次，我們保留了遞迴函式呼叫的機制，但似乎有一些多餘的
  代價，只是並不那麼地明顯，至少直觀上沒有顯著會慢很多的理由。此時我們可以開始
  討論底層實作的層面。在具有遞迴函式呼叫的程式碼經過編譯器編譯後，一般的硬體結
  構要實作呼叫 (call) 會比單純的跳躍 (jump) 要複雜，簡單的理由就是每次呼叫要記
  得回傳時回來的位址，還有要儲存目前函式內部變數的狀態，以免到時回傳回來後原本
  的資料都遺失了。因為這種遞迴的形式是將遞迴呼叫放在遞迴函式定義的最後一行 (且
  只有一次)，也就是所謂的尾端遞迴 (tail recursion) 或尾端呼叫 (tail call) 。事
  實上我們不必去儲存每次呼叫回傳時要回來的位址，因為最後回傳時都會經過一連串的
  回傳後回傳到第一個呼叫者，所以我們只需要記得第一個呼叫者的位置。同時我們也不
  用在呼叫後還儲存著目前函式內部變數的狀態，因為回傳回來後除了繼續回傳回去也不
  會做任何事。

  現代的編譯器在你適當的表示成上述尾端呼叫的程式碼時，可以幫你做尾端呼叫最佳化
  (tail call optimization)，避免在底層實作時使用呼叫 (call) ，所以原則上可以做
  到跟迴圈幾乎無差別的效率。甚至如果你迴圈寫得不好 (例如不良的使用迭代器)， 反
  而寫得好的遞迴會比較快。

  以上是假設遞迴關係本身是獨立的計算，不牽涉到外部操作 (例如使用 cout)，也就是
  我們不用去保證不同樹枝之間呼叫的先後關係。這在實務上其實很少遇到，一般我們遇
  到的是像漢諾 (Hanoi)  塔這類的遞迴關係，也就是遞迴函式執行的順序會影響最後的
  結果。所以為了保證執行順序，在使用迴圈實作遞迴關係時，我們會需要使用類似堆疊
  的結構來模擬，此時遞迴跟迴圈的效率優劣就更難說，反而會與你是否有好好的寫程式
  碼有比較大的關係。此外，用迴圈實作遞迴關係是在我們對於參數值有個好的順序 (例
  如從 0 算到 10) 的情況下，才容易使用類似快取的機制。如果參數空間太大，而實際
  上使用的參數值組合不多，快取機制會更難做而沒效率。不過這都是後話, 我想我有空
  再補完.....

  結論，在語言層次實作遞迴關係時用遞迴函式呼叫跟迴圈哪個方式好還是跟你的寫法和
  編譯器有關。用迴圈實作會 "大幅地" 改進效率通常是因為我們偷偷在其中增加了其他
  機制與特性，而這些機制與特性其實遞迴函式呼叫也都可以用只是你沒用，也就是你用
  了一個比較聰明的方法去欺負一個比較簡單的方法。

--

  寫一寫發現好像大部分是常識, 我錯了...

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.217.49
→ fireslayer:DP
→ a27417332:DP是指dynamic programming嗎0.0
→ Feis:是阿.
→ diabloevagto:好像繞口令，看得我都暈了...
→ coal511464:其實現在硬體都夠強悍了.....
→ coal511464:遇到萬行以上的 想改快點腦袋真的會很頭痛....
→ Feis:即使是硬體夠強悍, 很多不良的遞迴或迴圈用法依然會爆炸
→ Feis:晚點我可以舉些例子. 只是可能都太簡單
推 LPH66:這篇正好把 DP, memoization 跟原本的遞迴都講到了
→ LPH66:memoization 就是中間算完把值記下來的那個方法
推 karaokstar:推講解詳細
推 littleshan:這不能算是「有些疑惑」吧...
推 BlazarArc:最近剛好有用到 memorization 的方法
推 LPH66:樓上, memoization 沒有 r 喔 XD 它是從 memo 一字衍伸來的
→ LPH66:沒有 r 的這個字是專門用在這裡指稱這種「筆記」法的
推 BlazarArc:(嚇) 還真的耶...這太像了XDDD
推 rebaudiana:我覺得需要用遞迴的狀況大部分屬於「計算順序不明確」
→ rebaudiana:或者是有時候狀態的表示太複雜了所以丟給遞迴做…
推 ousapas:同樣是DFS 自己用stack做就硬是比直接遞迴快很多
→ Feis:ousapas: 那可以分享一下你的 DFS 是怎麼寫的嗎?
推 ousapas:只是之前寫過一個題目 用遞迴會超時 stack就剛好能過
→ ousapas:印象頗深刻XD
推 crazycat2:受教了！
→ Feis:ousapas: 效率會受到寫法、編譯器跟硬體影響.
→ Feis:用迴圈寫某層面來說是我們幫編譯器做自以為的最佳化.
→ Feis:如果我們比編譯器聰明, 更了解運作平台, 當然可能更有效率
→ Feis:但是也可能剛好相反.
→ adrianshum:這裡說成iteration要用空間換取效率，可是明明可以不用
→ adrianshum:呀，iterative不必存每個已算的f(n)...
→ Feis:確實，那就是我在文中提到有更簡單做法的原因
→ Feis:不過已經有人回應了～
※ 編輯: Feis            來自: 140.112.217.49       (09/06 12:14)
推 christianSK:推!!
> -------------------------------------------------------------------------- <

作者: Feis (永遠睡不著 @@) 看板: C_and_CPP
標題: Re: [問題] 關於遞迴加快速度的迷思？
時間: Fri Sep  6 12:04:55 2013

※ 引述《LPH66 (f0VMRgEBA)》之銘言：
<deleted>
: 雖然有點像在模仿 GCD 的 "GCD(a,b) = GCD(b,a%b)"
: 不過確實是另一條思路...

  確實，通常當我們可以用更簡單的形式來表示時，也意味著有一種
  更高階或不同角度的解釋法。

  之前我的回應是著重在『遞迴比迴圈效率要差』的論述上，也就是
  當問題具有遞迴關係時，在語言實作中使用遞迴函式呼叫是否比使
  用迴圈效率還要差。所以我使用一個比較單純的例子跟寫法來說明
  其中的關鍵點。不過看來有人對於一些技巧有點興趣，所以我試著
  將之前的回應導到這個問題上，看看大家有沒有什麼不同的想法 (
  雖然實際上我在講的可能就是動態規劃 (DP) 常用來減少記憶體使
  用的手法)。

  這是我在之前回應中寫的最後一個遞迴版本：

    void f(int n, int *F, int i = 0) {
      if (n < i)  return;

      if (i <= 1) F[i] = i;
      else        F[i] = F[i-1] + F[i-2];

      f(n, F, i+1);
    }

    int main() {
      int F[10+1];
      f(10, F);
      printf("%d\n", F[10]);
      return 0;
    }

  現在的問題變成是：我們一定需要這麼大的快取空間 (int F[10+1])
  嗎？

  其實這件事情會跟計算的順序有很大的關係。

  在把遞迴函式呼叫中呼叫者跟被呼叫者的關係描述成樹後，我上一
  個回應提到的快取機制 (也就是 memoization) 做的事情是避免具
  有相同參數值的遞迴函式重複計算造成多餘的遞迴展開。

  因為在這棵樹上只要其中一個具有某組參數值的函式呼叫被遞迴展
  開計算完後，其他具有相同參數值的函式呼叫就不需要去做同樣的
  遞迴展開。

  概念上，我們是用這個快取機制把這棵樹上的一些子樹剪掉而降低
  計算量。至於哪些遞迴展開 (子樹) 會被省略掉 (剪掉)， 就會跟
  我們計算的順序有關。

  之前的快取機制是剪完這棵樹後以參數值當鍵值把所有節點都儲存
  起來，而這篇要解決的問題是在於是否一定要『同時』記得所有節
  點？換句話說，我們最少需要準備多大的快取空間？

  在快取機制中，我們清除快取最好的時機是在確保將來都不可能會
  再用到的時候。換句話說，在快取空間中，只要該組參數值組合不
  會再被存取我們就不用去保留該筆資料。

  Fibonacci 數列的例子中，清除快取的手法可以透過對快取空間做
  滑動的技巧來達成：

    // 用不停更新 F[2], F[1], F[0] 去儲存 F[i], F[i-1], F[i-2];

    void f(int n, int *F, int i = 0) {
      if (n < i) return;

      // 利用滑動來減少快取空間的使用
      F[0] = F[1];
      F[1] = F[2];

      if (i <= 1) F[2] = i;
      else        F[2] = F[1] + F[0];

      f(n, F, i+1);
    }

    int main() {
      // 如果計算順序好，我們只需要三個空間 (F[i] = F[i-1] + F[i-2])
      int F[3];
      f(10, F);
      // 此時 F[2] 的值就是我們要的 f(10) 的值
      printf("%d\n", F[2]);
      return 0;
    }

  當然，事實上我們可以用更小的 F 來實現滑動, 只是可能會覺得不直覺：

    void f(int n, int *F, int i = 0) {
      if (n < i) return;
      // 原本滑動做的事情:
      // ( 這裡 F[i] 表示原本快取的資料，F[i] 表示新的值 )
      // F[0] = F[1]
      // F[1] = F[2]
      // F[2] = F[1] + F[0];

      // 這時我們要省略一個，所以改成同時做下面兩個述句:
      // F[0] = F[1]
      // F[1] = F[1] + F[0]

      // 注意這裡 F[i] 與 F[i] 值不同,
      // 直接依上述述句做的話, 會有 F[i] 值已經被取代不見的問題

      // 因此跟實作變數交換一樣，我們需要一個額外的區域變數 old_F1
      //  來暫存

      int old_F1 = F[1];

      if (i <= 1) F[1] = i;
      else        F[1] = F[1] + F[0];

      F[0] = old_F1;

      f(n, F, i+1);
    }

    int main() {
      int F[2];
      f(10, F);
      printf("%d\n", F[1]);
      return 0;
    }

  因為需要的快取空間夠小且固定大小，可以將他在參數列展開：

    void f(int n, int &F1, int &F0, int i = 0) {
      if (n < i) return;

      int old_F1 = F1;

      if (i <= 1) F1 = i;
      else        F1 = F1 + F0;

      F0 = old_F1;

      f(n, F1, F0, i+1);
    }

    int main() {
      int F[2];
      f(10, F[1], F[0]);
      printf("%d\n", F[1]);
      return 0;
    }

  其中 F0 的參考又可以被移掉：

    void f(int n, int &F1, int F0 = 0, int i = 0) { // 這裡 F0 初始值不重要
      if (n < i) return;

      int old_F1 = F1;

      if (i <= 1) F1 = i;
      else        F1 = F1 + F0;

      f(n, F1, old_F1, i+1);
    }

    int main() {
      int F1;
      f(10, F1);
      printf("%d\n", F1);
      return 0;
    }

  接下來我們可以用回傳值來替代參考的功能，同時我們可以將邊界條件當做快
  取資料的初始值：

    int f(int n, int F1 = 1 int F0 = 0, int i = 2) { // F0, F1 和 i 初始值很重要
      if (n <= 1) return n;
      if (n < i)  return F1;
      return f(n, F1+F0, F1, i+1);
    }

    int main() {
      printf("%d\n", f(10));
      return 0;
    }

  我們最後可以簡化到上面這樣 (但是效率跟泛用性不一定比一開始
  的版本好)

  [編輯] 板友 DJWS 覺得我原本不適當的用英文詞彙強調一些中文名詞可能會
         誤導其他板友，所以我將比較不正式或我不確定正確用法的英文名詞
         都移除。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.217.49
推 s3748679:嗯XD 好多字 要看~ (被毆)
推 c2251393:是說可以構造矩陣((1, 1),(1, 0))來加速www
推 joshua5201:樓上國手
→ Feis:我所知道最快的應該是用矩陣乘法加上 doubling
→ s3748679:痾.. 據我所知最快的應該是公式解吧.. (直接代入公式-3-)
→ Feis:公式解印象中效率是差不多的
推 joshua5201:公式照理說是O(1)? 不過那些根號電腦不好算吧
→ Feis:O(1) 要看你的單位是什麼. 實際上還是跟項次有關
→ Feis:根號 (無理數) 會有精度問題. 不過應該可以展開避免.
→ s3748679:.... 被打臉了~ (臉紅) 原以為會萬無一失說 orz..
→ Feis:我也是道聽塗說. 上次寫快速 Fibonacci 應該十幾年前了.
→ Feis:你有興趣可以寫寫看. 再跟大家分享一下~
推 c2251393:公式解的話有個^n，要計算的話還是快不了吧
→ c2251393:(是說再深入下去感覺會離題XDD
※ 編輯: Feis            來自: 140.112.217.49       (09/07 23:37)