1.1 數學中的遞迴 vs 程式中的遞迴
數學中的遞迴
在高一數學課時，學習到使用遞迴解決數學上的問題，以下幾個是簡單的範例
- 有一位小朋友要走樓梯上樓，他一次可以往上走一階或一次走兩階，問你若要走 $n$ 階，共有幾種走法?
- 在此我們可以藉由上一階、上兩階的特性，將問題轉換成，若我要走到第 $i$ 階，則他必是從 $i - 1$ 和 $i - 2$ 階走過來的，下一步，就可以列成遞迴關係式
\begin {cases} F(x)=F(x-1)+F(x-2),x>1 &\ F(x)=1,x\leq 1\end{cases}
$$ f(x)=\left{
\begin{aligned}
F(x)=F(x-1)+F(x-2),x>1\
F(x)=1,x\leq 1
\end{aligned}
\right.
$$
$$f(x)=
\begin{cases}
0& \text{x=0}\
1& \text{x!=0}
\end{cases}$$
- 將一個等差數列 $F(x)=3x+5$ 傳換成遞迴關係式
- 很容易的第一項需要特別定義$F(0)$，接下來的這一項就會式上一項再加3