vb 分别用递归,递推求斐波那契数列

Private Sub Command1_Click()
Print fbnqDt(20)
Print fbnqDg(20)
End Sub

Rem 递归，自己调用自己，效率没递推的高
Private Function fbnqDg(ByVal n As Integer) As Double
If n = 1 Or n = 2 Then
fbnqDg = 1
ElseIf n > 2 Then
fbnqDg = fbnqDg(n - 1) + fbnqDg(n - 2)
Else
fbnqDg = 0
Exit Function
End If
End Function

Rem 递推，从已知的项递进推导未知的项
Private Function fbnqDt(ByVal n As Integer) As Double
Dim i As Integer
ReDim a(1 To n) As Double
a(1) = 1
a(2) = 1
For i = 3 To n
a(i) = a(i - 1) + a(i - 2)
Next
fbnqDt = a(n)
End Function

再详细解释一下递推和递归的相同点和不同点：
相同点：
两者都可以描述为如下形式：
a(n) = f(a(n-1),a(n-2),...)
不同点：
1，从程序上看，递归是自己调用自己，递推不用这种方式。
2，递归将复杂问题化为简单问题，最终求得结果，是逆向求解的。
递推从简单问题出发，一步步向前发展，最终求得结果。是正向的。
3，递归中，问题的n要求是计算之前就知道的，而递推可以在计算中确定，不要求计算前就知道n。
4，一般来说，如果可以计算，递推的效率高于递归。但有时递推公式很难找，就不好计算了。

递推：先给出第一项数值1、第二项数值1，然后根据A(n)=A(n-1)+A(n-2)的递推公式不断向后算，直到算至要求的第N项为止，这种方法就是递推

递归：先根据A(n)=A(n-1)+A(n-2)的递推公式写出一个可被调用的函数DA(n as long ) as long，在DA函数中，如果n-1>2则调用DA(n-1)函数得到A(n-1)，否则A(n-1)=1，同理得到A(n-2)，这样DA函数就会不断调用自身直到N等于1或2为止，最后就会得到要求的A(N)，这种不断调用自身函数的方法就是递归(有可能也叫迭代，不太确定)。

第一种：
Function fib(ByVal n As Integer) As Long
If n = 1 Or n = 2 Then
fib = 1
Else
fib = fib(n - 2) + fib(n - 1)
End If
End Function

Private Sub Form_Click()
Show
Dim i, s As Integer
i = 0
s = 0
Do While s <= 150
i = i + 1
s = fib(i)
If s <= 150 Then Print s;
Loop
End Sub

第二种：
Function fib(ByVal n As Integer) As Long
Dim f1, f2, f3 As Integer
Dim i As Integer
f1 = 1: f2 = 1
Print f1; f2;
For i = 3 To n
f3 = f1 + f2
f1 = f2
f2 = f3
Print f3;
Next i
End Function

Private Sub Form_Click()
Show
Dim n As Integer
n = 10
fib (n)
End Sub