1.1 數學中的遞迴 vs 程式中的遞迴
數學中的遞迴
在高一數學課時，學習到使用遞迴解決數學上的問題，以下幾個是簡單的範例
-
有一位小朋友要走樓梯上樓，他一次可以往上走一階或一次走兩階，問你若要走 $n$ 階，共有幾種走法?
- 在此我們可以藉由上一階、上兩階的特性，將問題轉換成，若我要走到第 $i$ 階，則他必是從 $i - 1$ 和 $i - 2$ 階走過來的，下一步，就可以列成遞迴關係式
\[F(x)= \begin {cases} F(x-1)+F(x-2) & \text{if }x>1 \\ 1 & \text{if } x\leq 1\end{cases}\]
-
請將一個等差數列 $F(x)=3x+5$ 傳換成遞迴關係式
- 很容易的第一項需要特別定義 $F(0)$，接下來的這一項就會式上一項再加3，列成關係式 \[F(x)= \begin {cases} F(x-1)+3 & \text{if }x>0 \\ 5 & \text{if }x=0\end{cases}\]
典型利用遞迴來找到解決問題的方法
- 當遇到一個不易解決的問題時，試著找出分割這個問題的模式(建立遞迴關係式)
- 找到之後藉由分割來將這個問題不斷地縮小
- 當問題縮小到一定的大小時，我們可以直接解決該問題(決定終止條件)
- 最後合併各個已解決小問題的答案即得到原問題的答案。(設計遞迴函式)
程式中的遞迴
在上面的一些例子中，都是使用學過的數學遞迴來解決一些數學上的問題，若是請你將上述問題變成程式問題，作法跟數學一模一樣，可以想像成$F(x)$就是程式當中的呼叫函數，換句話說，只需要藉由呼叫同一個函數的前幾項，就可以找到答案。接下來我們將上面兩個問題轉換成程式：