Re: [問題] 關於遞迴加快速度的迷思?
※ 引述《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 的情況
要怎樣做到相同效果?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 223.19.45.228
→
09/05 22:50, , 1F
09/05 22:50, 1F
推
09/05 23:08, , 2F
09/05 23:08, 2F
→
09/05 23:09, , 3F
09/05 23:09, 3F
→
09/06 09:01, , 4F
09/06 09:01, 4F
討論串 (同標題文章)