Re: [問題] 關於遞迴加快速度的迷思？
※ 引述《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)
→
09/05 23:36, , 1F
09/05 23:36, 1F
→
09/05 23:37, , 2F
09/05 23:37, 2F
→
09/05 23:37, , 3F
09/05 23:37, 3F
→
09/05 23:38, , 4F
09/05 23:38, 4F
推
09/06 00:07, , 5F
09/06 00:07, 5F
→
09/06 00:10, , 6F
09/06 00:10, 6F
→
09/06 00:11, , 7F
09/06 00:11, 7F
→
09/06 00:13, , 8F
09/06 00:13, 8F
→
09/06 00:14, , 9F
09/06 00:14, 9F
→
09/06 00:24, , 10F
09/06 00:24, 10F
→
09/06 00:35, , 11F
09/06 00:35, 11F
→
09/06 00:51, , 12F
09/06 00:51, 12F
推
09/06 01:25, , 13F
09/06 01:25, 13F
推
09/06 01:43, , 14F
09/06 01:43, 14F
推
09/06 08:14, , 15F
09/06 08:14, 15F
推
09/06 09:05, , 16F
09/06 09:05, 16F
討論串 (同標題文章)