作者GALINE (天真可愛CQD)
看板Soft_Job
標題Re: [討論] 遞迴要如何鍛鍊
時間Sun Aug 21 15:56:58 2016
※ 引述《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
→ MOONY135: 看起來很潮的用法 08/21 16:26
推 typepeter: 生動 08/21 16:50
推 lucky1lk: 兩個凸 給你推 08/21 17:36
推 GameHeven: 比喻不錯 08/21 19:45
→ DeathWatch: 要寫遞迴要先把條件搞懂，把問題拆分成小問題 08/21 23:19
→ viper9709: 葉問打很多人會很累XD 08/22 00:03
→ dnabossking: 請問為什麼1是0？ 08/22 02:52
→ dnabossking: 不是1、1、2、3、5、8嗎？ 08/22 02:53
我的錯，0是第零個...
Let me 改改
※ 編輯: GALINE (114.27.89.111), 08/22/2016 03:02:04
推 konanno1: (f=(a,b,n)=>{n==0?b:console.log(b)&f(b,a+b,--n)})(0, 08/22 17:42
→ konanno1: 1,12) //費式，JavaScript 一行極限了 08/22 17:43
→ recorriendo: 這種寫法如果編譯沒優化的話 stack是指數級增長的 08/23 02:45
→ recorriendo: 記得以前試過n大概在五六十就整個爆了 08/23 02:47