[程式] 遞迴只應天上有，凡人應當用迴圈

這句話的原文是這樣：

To iterate is human, to recursive, divine!

recursive 確實可以讓一些演算法變得更加簡潔
但要如何理解一個遞迴的做法確實有點違背普通人的思考方法
(不知道這有沒有心理學相關的實驗可供證明?)
只是對於一個資訊人來說，這確實是個必備的技能
因此如何理解一個遞迴式，甚至教導別人理解確實是個難題




第一次看到這句話時，也許是程式也寫了一段時間
對於遞迴的理解已經有一定程度了，心裡的感觸並不多
但這幾天對這句話有著非常深的感觸...

起因自我這學期擔任的 "駐點助教" 一職
這工作簡單來說就是每個禮拜固定一個時間去系上的計中坐檯等著被人問問題
其中有一個程度非常差，所以每周固定來光顧的學生
這周他問的問題是：請教他遞迴以及怎麼寫河內塔
乍看之下並不是什麼很困難的問題
遞迴我最常看到的範例就是 Fibonacci Series 了
這是個直接把數學式寫出來也很快就能被接受的好範例
程式碼因為可以直接對應數學式，在理解上也很容易
但當天講解河內塔時，讓我發現一件事：
Fibonacci 的範例其實是個無法讓初學者好好理解遞迴的威力的範例!

以當天教河內塔的情況來說，該學生完全光是理解這段話就花了一段時間：
"要把 N 個盤子從 A 移到 C，我們必須要先把 A 上面 N-1 個盤子移到 B，然後把 A 最下面的盤子移到 C，再把 B 那 N-1 個盤子移到 C"
上面這段話是河內塔遞迴的精神所在，但是當時對那位學生來說，他為了好好理解為什麼可以把 N-1 個盤子從 A 移到 B 這點就花了至少有 30 分鐘。但這一點，卻是之所以可以採用遞迴關鍵之一。但更關鍵的在後頭：他終於理解並接受了這點後，他無法把這個想法跟程式碼結合：

void Hanoi (int N, char start, char mid, char target)
{
     if (N == 0) return;
     Hanoi (N-1, start, target, mid);
     printf ("move from %c to %c\n", start, target);
     Hanoi (N-1, mid, start, end);
}

他的問題在於：為什麼寫 Hanoi (N-1, start, target, mid); 就代表把 start 上面 N-1 個盤子移到 mid ? 到了此時，我覺得我可以理解為什麼會說 "遞迴只應天上有了"，因為他的思考方式並不直覺，因此對於一般人來說，理解能力會變差。而且我第一次寫遞迴是看老鼠走迷宮時，當時自己也被那個遞迴式搞了很久才搞通那遞迴的意思。但我想倒也不必矯枉過正到盡量避免使用遞迴，只是說必要的註解與說明倒是萬萬不可少，不然我想不用過多久連自己都要下個註解是 Magic! Don't Touch! 了。

備註：其實我到現在也還是想不出來究竟要怎麼講解遞迴會是比較容易被理解的...