→ iForests:怎麼大家遞迴的例子都舉這麼北七的 XD 10/09 22:08
→ sa072686:舉太高級並不會幫助理解啊XD 10/09 22:15
推 ggm5566:56友情推 10/09 22:18
推 csftwpt5566:5566 友情推 10/09 22:22
雖然強者森林已經發文了，不過看到遞迴還是頗為手癢啊。
畢竟小時候相當喜歡遞迴，當然現在也是。
---- 前情提要結束 ----
遞迴，便是將原問題，切成相同但規模較小的問題，一一解決後便知原問題的答案了。
至於如何去解決，便是靠規模夠小、無法再分割時的答案，而這也是我們已知的。
而函數呢，看它是什麼型態，便可以將其視為該型態的一個數值，
其數值則視傳入參數與運算方式等等而定。
舉個老例子，計算 n! 為何。
已知 n! = (n-1)! * n，因此我們只要知道 (n-1)!，就可以知道 n! 的答案。
假設 f(i) 可以正確求出 i! 的值，於是在計算 n! 時，
只要先用 f() 計算 (n-1)! 的值，再將其乘上 n，即為所求。
這時會將切割後的子問題 (n-1)! 當作一個相同，但規模較小的獨立問題來做。
而這個獨立問題，設 m = n-1，則等同於求 f(m)，即 m! 的值。
這又會求 (m-1)! 的答案，以算出 m!，所以變成了一樣的問題。
但是前面只是假設正確，它真的正確嗎？
已知 0! = 1，而若 i! 正確，(i+1)! = i! * (i+1) 也會是正確的，
所以這樣寫是正確的。
而實際程式在執行時，流程是這樣子的：
假設我們呼叫了…不要太大，f(4) 就好。還和某首 debug 神歌有異曲同工之妙。
/* 以下 code 省略一些不太重要的東西 */
main()
{
printf("%d\n", f(4));
}
可是要輸出之前，必須先算出 f(4) 的值為何。因此，main() 會呼叫 f(4)，
並等待其算完，否則無法繼續下去。
f(n)
{
if(n == 0) return 1;
return f(n-1) * n;
}
現在要計算 f(4)，而 main() 正在等待結果。
想像你正在對抗強大的使徒，卻孤立無援，只好求助於平日好朋友 f(4)。
這裡你可能會質疑我，說不定強者我同學就會了，那幹嘛繼續遞迴下去？
想像你的朋友會解你問題的大部份，卻有一些小地方不懂得怎麼解；
於是他再去問他朋友他不懂的地方，而他朋友在他不懂的地方也有一些不會解，
只好再去問朋友，…
將這些朋友依序由大到小編號 4~0 好了。
直到問到最後一個人 0，他成功把所有小疑問解答出來了，
則 1 問到這些小細節後，他也把 2 所提的問題全解答出來了。
2 問到他所不會的小地方後，也把 3 問他的全解出來了。
在 3 告訴了 4 怎麼解 4 卡住的地方後，4 也成功解出你所不會的地方；
於是你就 AC 啦！
運行過程如下：
f(4) <== 現在在這裡想辦法求 f(4)
main()
/* 想像它們疊起來了，而我們得從最上面慢慢處理 */
/* 想像你是 main()，正等著 f(4) 解出你的問題，並告訴你。 */
但我們不知道 4!，幸好我們知道可以先求 3!。
想像 4 在你提問的問題中，有一些不會解，只好問 3。
於是變成這樣：
f(3) <== 現在在這裡
f(4) <== 等待 f(3)
main() <== 等待 f(4)
可是 3 也必須求助於 2 才行，所以只好…
f(2) <== 現在在這裡
f(3)
f(4)
main()
可是 2 也還不知道呢…不拖戲，直接繼續：
f(1) <== 現在在這裡
f(2)
f(3)
f(4)
main()
於是求助於 1
f(0) <== 現在在這裡
f(1)
f(2)
f(3)
f(4)
main()
f(0) 終於所有問題都會，而不用再去問其它朋友啦！
於是 f(0) 將答案告訴 f(1)，而 f(0) 的答案是 1。
f(1) <== f(0) 告訴他卡住的地方怎麼解後，就秒殺了，再告訴 f(2)
f(2)
f(3)
f(4)
main()
當 f(1) 告訴 f(2) 怎麼解 f(2) 所卡住的部份後，也就完全解決了 f(3) 的問題。
f(2) <== 在這裡解決後，告訴 f(3)
f(3)
f(4)
main()
接著換 f(3) 問到卡住的地方後，解決了 f(4) 的問題了。
f(3) <== 也解決了，告訴 f(4)。
f(4)
main()
f(4) 在問過 f(3) 他卡住的一小部份後，也把你發問的問題給全部解決啦。
f(4) <== 解決，告訴你。
main()
於是回到 main()，而你在得到解答後便 AC 啦。
在這裡，f() 的規模越來越小，但都是相同的。
可能你一開始有 10 題不會，但到後面可能只剩 3 題、1 題、…，直到被全解。
也許 f(4) 只去問了 f(3) 共 7 題，但不先問到，也沒辦法完全解開；
f(3) 只需要會那 7 題，但可能有個 4 題不會，也得先問到才算完全解開。
也許 f(0) 只需要會 1 題就好，但那是極關鍵。知道它後，連帶的可以知道許多；
遞迴的運行，差不多就是這樣子的。
另外丟個小問題給大家玩玩看好了。
如果告訴你 n 並給你 n 個數，怎麼求最小值為何呢？
以下附解答，慎入。
已知這 n 個數的最小值，要嘛在第 n 個數，要嘛在前 n-1 個數中。
於是我們可以將前 n-1 個數求最小值，看作一個新的 n 數求最小值問題。
已知若 n 為 1，則最小值即為該數；由此可知遞迴式如下：
（設此 n 數為 a[1] ~ a[n]）
f(1) = a[1];
f(n) = min(a[n], f(n-1));
貼心文末防雷空頁。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.240.202