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

看板C_and_CPP作者Feis (永遠睡不著 @@)時間12年前 (2013/09/04 13:07)推噓11(11推 0噓 21→)

留言32則, 14人參與討論串2/10 (看更多)

※ 引述《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

09/04 21:21, , 1^F

09/04 21:21, 1^F

→

a27417332

09/04 21:23, , 2^F

09/04 21:23, 2^F

→

Feis

09/04 21:24, , 3^F

09/04 21:24, 3^F