作者littleshan (我要加入劍道社!)
看板C_and_CPP
標題Re: [問題] 關於遞迴加快速度的迷思？
時間Thu Sep 5 23:28:24 2013
※ 引述《adrianshum (Alien)》之銘言：
: ※ 引述《Feis (永遠睡不著 @@)》之銘言：
: [43]
: 請教一下。
: 你提到,iteration 型式做到的比較有效的方法，其實
: 也可以在 recursive 中做到。這點我有點搞不清楚。
: 比如用 fibbonachi number 做例子，我想一想，其實可以
: 寫成沒快取，也毋需重覆計算的樣子：
: int fib(int n) {
: if (n <= 1) {
: return 1;
: }
: int fn = 1; // f(n)
: int fn_1 = 0; // f(n-1)
: for (int i = 1; i < n; i++) {
: int newFn = fn + fn_1;
: fn_1 = fn;
: fn= newFn;
: }
: return fn;
: }
: 這樣既無快取，也沒有重覆計算。可是recursion 的情況
: 要怎樣做到相同效果？
簡單到莫名奇妙的程度 XD
int fibb(int n, int a = 1, int b = 0)
{
if(n <= 0)
return a;
else
return fibb(n-1, a+b, a);
}
int main()
{
for(int i = 0; i < 10; ++i)
cout << fibb(i) << endl;
return 0;
}
其實把迴圈改成 tail call 是相當有趣的經驗
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 202.39.238.242
※ 編輯: littleshan 來自: 202.39.238.242 (09/05 23:29)
※ 編輯: littleshan 來自: 202.39.238.242 (09/05 23:30)
→ s3748679:(頭暈.. 會不會有點太不直覺了?) 09/05 23:36
→ LPH66:其實不會喔 你可以想一想最大公因數(歐幾里得算法)的遞迴版 09/05 23:37
→ LPH66:它的型式跟這篇的 fibb 非常之像 09/05 23:37
→ LPH66:(雖然計算方向上是一個向上一個向下就是了 XD) 09/05 23:38
→ s3748679:從計算過程上來看 fibb 已經不是遞迴關係式了說 09/06 00:10
→ s3748679:反而比較像是用程式語言的遞迴程序(函數)實現遞迴關係式 09/06 00:11
→ s3748679:的計算過程~ (心得) 09/06 00:13
→ s3748679:咳咳.. 補一下: 所以才會覺得不太直覺就是了~ 09/06 00:14
→ drm343:尾遞迴基本上需要計算參數，所以才讓樓上覺得不像遞迴吧， 09/06 00:24
→ Feis:改法是有規律的，是DP常見手法 09/06 00:35
→ Feis:就是把要記憶的快取空間壓縮後放在參數，迴圈則是放在區域變 09/06 00:51
推 xvid:在函式引數寫賦值 第一次看到這種寫法... 09/06 01:25
推 ck574b027:參數預設值啊，比 overload 有用 09/06 01:43
推 descent:s3748679: 圖解真清楚 09/06 08:14
推 adrianshum:給個讚。我自己太笨了，被原本的遞迴限制了想法 09/06 09:05