Re: [討論] 遞迴要如何鍛鍊
※ 引述《ripple0129 (perry tsai)》之銘言：
: 大家覺得遞迴是很吃天份的東西嗎，
: 怎樣的鍛鍊方式能夠讓使用遞迴得心應手？
: 小弟是個費式數列都寫不出來的遞迴白癡，
: 有請大大分享心得。
: 或是建議不要寫遞迴這種鬼東西？
要用遞迴，要習慣遞迴是一種 "各自擊破" 的做法
這是思考方式的問題，抄 code 不一定抄得來
例如葉問一個打十個，用遞迴來講就是"先打一個，然後打剩下的"
然後遞迴必須要給一個"好了打完了收工"的條件，不然會沒完沒了
以下虛擬碼
-----------------------
yeh.fightWith = func(array enemies) {
// 沒人就不用打了
if (0 === enemies.length) {
return
}
// 挑一個打，然後打剩下的
mob = enemies.pop()
this.punch(mob)
this.fightWith(enemies)
}
-----------------------
而費式數列的第 N 個，規則是這樣
- N = 0 為 0
- N = 1 為 1
- N>= 2 為 F(N-1) + F(N-2)
換句話說是"我先算前兩個，然後算我自己"
而那前兩個又可以各自分解成他們自己的前兩個
以下虛擬碼
-----------------------
func F(int n) {
// 小於 0 會爆炸
if (n < 0) {
throw Exception("最好 n 是小於 0 啦 凸-.-凸")
}
// 第零個跟第一個是 0 跟 1
if (n <= 1) {
return n
}
// 先算前兩個然後加起來
return F(n - 1) + F(n - 2)
}
-----------------------
"不會用遞迴"的問題會在於能不能想到各個擊破的點
能想到的話遞迴大概就寫得出來了
但"該不該用遞迴"則是另外一個問題，而且會扯到資料結構的底層實做
例如上面一個打十個的例子，他有可能產生十個中間陣列(enemies.pop())
葉問如果打很多人的時候會很浪費記憶體
然後 function call 本身也是個成本
遞迴深度很大的時候 stack 會滿出來(那我就漫出來了)
不是說遞迴不好，只是隱含要考量的實做細節很多
這是把妖刀，不一定合用...
--
Sent from my little pony
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.27.89.111
※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1471766222.A.6BF.html
→
08/21 16:26, , 1F
08/21 16:26, 1F
推
08/21 16:50, , 2F
08/21 16:50, 2F
推
08/21 17:36, , 3F
08/21 17:36, 3F
推
08/21 19:45, , 4F
08/21 19:45, 4F
→
08/21 23:19, , 5F
08/21 23:19, 5F
→
08/22 00:03, , 6F
08/22 00:03, 6F
→
08/22 02:52, , 7F
08/22 02:52, 7F
→
08/22 02:53, , 8F
08/22 02:53, 8F
我的錯，0是第零個...
Let me 改改
※ 編輯: GALINE (114.27.89.111), 08/22/2016 03:02:04
推
08/22 17:42, , 9F
08/22 17:42, 9F
→
08/22 17:43, , 10F
08/22 17:43, 10F
→
08/23 02:45, , 11F
08/23 02:45, 11F
→
08/23 02:47, , 12F
08/23 02:47, 12F
→
08/23 02:53, , 13F
08/23 02:53, 13F
討論串 (同標題文章)
Soft_Job 近期熱門文章
40
131
PTT職涯區 即時熱門文章
75
212