看板Soft_Job
想學遞迴？找個 pure functional programming language 就解決了，
語言本身不給迴圈，只能用遞迴XD
遞迴其實並沒有那麼難，只要了解遞迴的思考模式，任何人都可以寫出來
1. 首先思考邊際情況，也就是可能出現錯誤的情況，或是可以直接回答出答案，
不需要使用遞迴的例子。
2.想一個比邊際情況還要難一點點的例子，
然後想辦法將問題用遞迴拆解出邊際情況的組合。
3.順利的話，再來將一般的情況用遞迴拆解（有時2.跟3.是一氣呵成的）
會覺得遞迴很難的應該是因為把思考的順序弄反，（3. => 2. => 1.）
以費氏數列為例，假設 fib(1) = 1, fib(2) = 1, fib(3) = 2, ...
千萬不要一開始就從 fib(100) 開始思考
而是先從 fib(n) n 什麼時候會有錯誤開始？
先確認 n 為正整數或零，如果不是就丟例外，
確定錯誤情況被排除之後，
再來思考可以直接回答的情況（或者是遞迴無法使用的情況）
根據定義有兩個 fib(0) = 0 跟 fib(1) = 1
再來思考需要使用遞迴的例子
fib(2) = fib(1) + fib(0)
fib(3) = fib(2) + fib(1)
...
最後推到一般的情況
fib(n) = fib(n-1) + fib(n-2)
然後把整個拼湊起來
大概是這樣子，只要是遞迴的演算法都會有這樣子的 pattern
比方說 merge sort 跟 quick sort 也是
不要一開始就考慮所有的情況，而是先從特例開始
（此外 bug 一般都是發生在特例情況，從特例開始有助於避免程式錯誤的好處）
也就是元素只有 0,1,2 ...開始
然後再慢慢修正到可以處理所有的情況
思考模式來說和數學上的自然歸納法很類似。
--
你說的沒錯的沒錯，中間舉例簡單例子的時候我應該多做說明一下
假設特例的部份解決了，目前函數的樣子是
function fib(n)
{
if( n == 0 ) return 0;
if( n == 1 ) return 1;
}
接下來 n = 2 的情況
根據定義要推寫出 fib(2) 應該可以寫成 fib(1) + fib(0)
接下來根據fib(2) = fib(1) + fib(0) 思考要如何改寫原函數來滿足這個關係
function fib(n)
{
if( n == 0 ) return 0;
if( n == 1 ) return 1;
//下面需要 return 的結果是 fib(2)
//也就是說 n = 2 帶入的話，會是return fib(1) + fib(0)
//至於要怎麼寫出來就需要多一點練習了
return fib(n-1) + fib(n-2);
}
函數到這裡其實已經完成了
寫遞迴的時候，如果遞迴關係正確，
只要寫出特例跟最簡單的一般例就結束了。
例一個數學上的例子是階乘 n!
其實只要寫出 n = 0 的特例，以及用 n = 0 來表示 n = 1 的情況
其他情況也都會被一併解決。
pattern matching 可讀性真的好許多
※ 批踢踢實業坊(ptt.cc), 來自: 36.231.31.147※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1471783684.A.481.html
→ bibo9901: 通常費式數列是定義, 不是用觀察的orz 08/22 00:32
→ bibo9901: 氏 08/22 00:33
推 CoNsTaR: 遞迴特例通常都是極端 08/22 01:18
推 frouscy: 找pure functional language來練正解XD 08/22 02:09
→ frouscy: 特別是大部份functional langauge有pattern matching 08/22 02:10
→ frouscy: 用pattern matching可讀性常常比用if-else來得高 08/22 02:12
→ dnabossking: 是說，各位的離散數學都沒教 Recurrence Relations? 08/22 12:57