前言
本文開始前，先簡單介紹一下費式數列。以下列出費式數列的前15項內容。
1、1、2、3、5、8、13、21、34、55、89、144、233、377、610
可以發現，除了前兩項固定為1，之後的數列都是前面兩個數字相加
例如：
F(3) = F(1) + F(2) = 1+1 = 2
F(5) = F(3) + F(4) = 2+3 = 5
本篇將使用"遞迴"方式，讓程式可以計算出指定的費式數列。
方式一(遞迴)
使用function，自己呼叫自己的方式，即為遞迴
遞迴（Recursion）
是指在函式中使用函式自身的方法。遞迴函式必須有終止條件，才能被計算。
是指在函式中使用函式自身的方法。遞迴函式必須有終止條件，才能被計算。
遞迴是什麼? 舉例如下：
Function add(x As Integer)
If x = 1 Then
Return 1
Else
Return add(x - 1) + 1
End If
End Function
If x = 1 Then
Return 1
Else
Return add(x - 1) + 1
End If
End Function
先宣告一個函式add(x)
可以看出函式內部，一直在呼叫add自己，直到x=1時才會Return 1(停止呼叫自己，"x=1"為終止條件)
實際上呼叫此函式時，比方說Msgbox(add(3))，就會看到提示視窗顯示「3」
這是因為：
add(3)會執行Return add(3-1)+1
add(2)會執行Return add(2-1)+1
add(1)會執行Return 1
由最後的add(1)，逆推回去add(3)，會發現其實Return add(3)等同於Return 1+1+1，因此回傳「3」
這就是遞迴的基本應用。
至於應用在費式數列當中，寫法則為：
Function Fibo(x As Integer)
If x <= 2 Then '費式數列前兩項都是1
Return 1
Else
Return Fibo(x - 1) + Fibo(x - 2)
End If
End Function
If x <= 2 Then '費式數列前兩項都是1
Return 1
Else
Return Fibo(x - 1) + Fibo(x - 2)
End If
End Function
這個程式碼，單純依賴人腦去逆推比較困難，因此我將計算過程記錄在Textbox裡面觀察
以Fibo(12)為例，計算出費式數列第12項：
答案144，是正確的
但是執行時間居然超過5秒
往上看一下計算過程，發現重複計算的部分很多
Fibo(3)、Fibo(2)、Fibo(1)出現了好多次，這些重複的部分都會造成效能浪費
導致執行時間大幅上升
這種計算方式叫做"迭代法"
迭代法（Iterative method）
重複使用計算出來的結果，就叫迭代法。
重複使用計算出來的結果，就叫迭代法。
雖然程式碼撰寫方便，也比較直觀
但是浪費效能的確是個硬傷
猜猜看Fibo(15)要花多少時間呢?
超過54秒，快要1分鐘了
這個費式數列也太費事了吧
想想看，有沒有辦法改進程式的執行效能。
方式二(記憶法)
其實還是有辦法解決的
既然拖垮效能的元凶是"重複計算"
那只要宣告一個陣列，把運算過的值存起來
以後再遇到，就不必計算第二次，這個稱之為"記憶法"
記憶法（Memoization）
將計算的結果保存起來，以備下次遇到同樣問題時使用。
將計算的結果保存起來，以備下次遇到同樣問題時使用。
程式碼範例如下：
Public fiArray(200) As Integer '費式數列(陣列)
Function Fibo(x As Integer)
If x <= 2 Then '費式數列前兩項都是1
Return 1
ElseIf fiArray(x) = 0 then '這個位置尚未計算過，才會使用遞迴計算
fiArray(x) = Fibo(x - 1) + Fibo(x - 2) '存進fiArray陣列，提供下次使用
End If
Return fiArray(x) '回傳fiArray陣列
End Function
Function Fibo(x As Integer)
If x <= 2 Then '費式數列前兩項都是1
Return 1
ElseIf fiArray(x) = 0 then '這個位置尚未計算過，才會使用遞迴計算
fiArray(x) = Fibo(x - 1) + Fibo(x - 2) '存進fiArray陣列，提供下次使用
End If
Return fiArray(x) '回傳fiArray陣列
End Function
宣告陣列fiArray(200)，用來存放已經計算完成的費式數列
馬上來檢視一下，改善後的程式效能吧。
試試看Fibo(15)：
執行時間0.12秒，成功改善效能。
至於運算過程，經過效能提升，省去了多餘的重複計算之後，總算是簡化成人腦也能看懂的程度了
例如Fibo(10)：
可以試著推算看看，能夠抓到程式執行的流向，才能搞懂"遞迴"是怎麼一回事。
程式碼分享
底下提供VB.NET程式碼
開新專案，在空白處點兩下，進入後端
後端清空程式碼，並直接複製貼上底下的程式碼，即可執行。
(前端留白就好，不需新增控制項)
Public Class Form1
Public fiArray(200) As Integer '費式數列(陣列)
Public TextBox1 As New TextBox '宣告前端控制項
Public Button1 As New Button
Public Button2 As New Button
Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
'前端控制項屬性設定
Me.Size = New Size(326, 660)
Button1.Name = "Button1"
Button1.Text = "使用遞迴"
Button1.Location = New Point(55, 586)
Me.Controls.Add(Button1)
AddHandler Button1.Click, AddressOf Button1_Click
Button2.Name = "Button2"
Button2.Text = "遞迴+陣列"
Button2.Location = New Point(165, 586)
Me.Controls.Add(Button2)
AddHandler Button2.Click, AddressOf Button2_Click
TextBox1.Name = "TextBox1"
TextBox1.Location = New Point(12, 12)
TextBox1.Size = New Size(286, 550)
TextBox1.Multiline = True
TextBox1.ScrollBars = ScrollBars.Both
Me.Controls.Add(TextBox1)
AddHandler TextBox1.TextChanged, AddressOf TextBox1_TextChanged
End Sub
Function Fibo(x As Integer)
TextBox1.Text += "Fibo(" & x & ") start."
TextBox1.Text += vbNewLine
If x <= 2 Then '費式數列前兩項都是1
TextBox1.Text += "Return 1"
TextBox1.Text += vbNewLine
Return 1
Else
TextBox1.Text += "Return Fibo(" & x - 1 & ") + Fibo(" & x - 2 & ")"
TextBox1.Text += vbNewLine
Return Fibo(x - 1) + Fibo(x - 2)
End If
End Function
Function Fibo2(x As Integer)
TextBox1.Text += "Fibo2(" & x & ") start."
TextBox1.Text += vbNewLine
If x <= 2 Then '費式數列前兩項都是1
TextBox1.Text += "Return 1"
TextBox1.Text += vbNewLine
fiArray(x) = 1
ElseIf fiArray(x) <> 0 Then '已運算過此步驟，直接回傳數值
TextBox1.Text += "Return fiArray(" & x & ") = " & fiArray(x)
TextBox1.Text += vbNewLine
Else
TextBox1.Text += "Return Fibo2(" & x - 1 & ") + Fibo2(" & x - 2 & ")"
TextBox1.Text += vbNewLine
fiArray(x) = Fibo2(x - 1) + Fibo2(x - 2)
End If
Return fiArray(x)
End Function
Private Sub Button1_Click(sender As Object, e As EventArgs)
Dim dteStart As DateTime = Now '記錄開始的時間
TextBox1.Text = "" 'textbox初始化
TextBox1.Text += "費式數列第12項(使用遞迴): "
TextBox1.Text += vbNewLine
TextBox1.Text += "計算過程:"
TextBox1.Text += vbNewLine
Dim ans As Integer = Fibo(12)
TextBox1.Text += vbNewLine
TextBox1.Text += "答案: " & ans.ToString
TextBox1.Text += vbNewLine
Dim TS As TimeSpan = Now.Subtract(dteStart) '計算執行時間
TextBox1.Text += "執行時間: " & TS.TotalSeconds & " 秒"
TextBox1.Text += vbNewLine
End Sub
Private Sub Button2_Click(sender As Object, e As EventArgs)
Dim dteStart As DateTime = Now '記錄開始的時間
For i = 0 To fiArray.Length - 1 '陣列初始化
fiArray(i) = 0
Next
TextBox1.Text = "" 'textbox初始化
TextBox1.Text += "費式數列第12項(使用遞迴+陣列): "
TextBox1.Text += vbNewLine
TextBox1.Text += "計算過程:"
TextBox1.Text += vbNewLine
Dim ans As Integer = Fibo2(12)
TextBox1.Text += vbNewLine
TextBox1.Text += "答案: " & ans.ToString
TextBox1.Text += vbNewLine
Dim TS As TimeSpan = Now.Subtract(dteStart) '計算執行時間
TextBox1.Text += "執行時間: " & TS.TotalSeconds & " 秒"
TextBox1.Text += vbNewLine
End Sub
Private Sub TextBox1_TextChanged(sender As Object, e As EventArgs)
TextBox1.SelectionStart = TextBox1.Text.Length
TextBox1.ScrollToCaret()
End Sub
End Class
Public fiArray(200) As Integer '費式數列(陣列)
Public TextBox1 As New TextBox '宣告前端控制項
Public Button1 As New Button
Public Button2 As New Button
Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
'前端控制項屬性設定
Me.Size = New Size(326, 660)
Button1.Name = "Button1"
Button1.Text = "使用遞迴"
Button1.Location = New Point(55, 586)
Me.Controls.Add(Button1)
AddHandler Button1.Click, AddressOf Button1_Click
Button2.Name = "Button2"
Button2.Text = "遞迴+陣列"
Button2.Location = New Point(165, 586)
Me.Controls.Add(Button2)
AddHandler Button2.Click, AddressOf Button2_Click
TextBox1.Name = "TextBox1"
TextBox1.Location = New Point(12, 12)
TextBox1.Size = New Size(286, 550)
TextBox1.Multiline = True
TextBox1.ScrollBars = ScrollBars.Both
Me.Controls.Add(TextBox1)
AddHandler TextBox1.TextChanged, AddressOf TextBox1_TextChanged
End Sub
Function Fibo(x As Integer)
TextBox1.Text += "Fibo(" & x & ") start."
TextBox1.Text += vbNewLine
If x <= 2 Then '費式數列前兩項都是1
TextBox1.Text += "Return 1"
TextBox1.Text += vbNewLine
Return 1
Else
TextBox1.Text += "Return Fibo(" & x - 1 & ") + Fibo(" & x - 2 & ")"
TextBox1.Text += vbNewLine
Return Fibo(x - 1) + Fibo(x - 2)
End If
End Function
Function Fibo2(x As Integer)
TextBox1.Text += "Fibo2(" & x & ") start."
TextBox1.Text += vbNewLine
If x <= 2 Then '費式數列前兩項都是1
TextBox1.Text += "Return 1"
TextBox1.Text += vbNewLine
fiArray(x) = 1
ElseIf fiArray(x) <> 0 Then '已運算過此步驟，直接回傳數值
TextBox1.Text += "Return fiArray(" & x & ") = " & fiArray(x)
TextBox1.Text += vbNewLine
Else
TextBox1.Text += "Return Fibo2(" & x - 1 & ") + Fibo2(" & x - 2 & ")"
TextBox1.Text += vbNewLine
fiArray(x) = Fibo2(x - 1) + Fibo2(x - 2)
End If
Return fiArray(x)
End Function
Private Sub Button1_Click(sender As Object, e As EventArgs)
Dim dteStart As DateTime = Now '記錄開始的時間
TextBox1.Text = "" 'textbox初始化
TextBox1.Text += "費式數列第12項(使用遞迴): "
TextBox1.Text += vbNewLine
TextBox1.Text += "計算過程:"
TextBox1.Text += vbNewLine
Dim ans As Integer = Fibo(12)
TextBox1.Text += vbNewLine
TextBox1.Text += "答案: " & ans.ToString
TextBox1.Text += vbNewLine
Dim TS As TimeSpan = Now.Subtract(dteStart) '計算執行時間
TextBox1.Text += "執行時間: " & TS.TotalSeconds & " 秒"
TextBox1.Text += vbNewLine
End Sub
Private Sub Button2_Click(sender As Object, e As EventArgs)
Dim dteStart As DateTime = Now '記錄開始的時間
For i = 0 To fiArray.Length - 1 '陣列初始化
fiArray(i) = 0
Next
TextBox1.Text = "" 'textbox初始化
TextBox1.Text += "費式數列第12項(使用遞迴+陣列): "
TextBox1.Text += vbNewLine
TextBox1.Text += "計算過程:"
TextBox1.Text += vbNewLine
Dim ans As Integer = Fibo2(12)
TextBox1.Text += vbNewLine
TextBox1.Text += "答案: " & ans.ToString
TextBox1.Text += vbNewLine
Dim TS As TimeSpan = Now.Subtract(dteStart) '計算執行時間
TextBox1.Text += "執行時間: " & TS.TotalSeconds & " 秒"
TextBox1.Text += vbNewLine
End Sub
Private Sub TextBox1_TextChanged(sender As Object, e As EventArgs)
TextBox1.SelectionStart = TextBox1.Text.Length
TextBox1.ScrollToCaret()
End Sub
End Class