2021年递归算法.ppt

在下面二种情况中存在算法调用自己的情况：
若一个算法直接的或间接的调用自己本身，则称这个算法是递归算法。
（1）问题的定义是递推的
阶乘函数的常见定义是：

1
递归算法
2021/1/15
也可定义为：
写成函数形式，则为：
这种函数定义的方法是用阶乘函数自己本身定义了阶乘函数，称上式为阶乘函数的递推定义式。
2
递归算法
2021/1/15
（2）问题的解法存在自调用
一个典型的例子是在有序数组中查找一个数据元素是否存在的折半查找算法。 如下例中查找元素17。
第一次:
下标
0
1
2
3
4
5
6
7
元素值
1
3
4
5
17
18
31
33
↑
↑
↑
low
mid
high
x>a(mid)
第二次:
下标
0
1
2
3
4
5
6
7
元素值
1
3
4
5
17
18
31
33
↑
↑
↑
low
mid
high
x<a(mid)
第三次:
下标
0
1
2
3
4
5
6
7
元素值
1
3
4
5
17
18
31
33
↑
low
high
x=a(mid)
mid
BSrch=4
mid=(low+high)\2，注意是整除“\”
3
递归算法
2021/1/15

例6-1 给出按照阶乘函数的递推定义式计算阶乘函数的递归算法，并给出n = 3时递归算法的执行过程。
设计：按照阶乘函数的递推定义式计算阶乘函数的递归算法如下：
Function Fact(n%) As Double
If n < 0 Then
MsgBox "参数错了！"
Fact = -1
ElseIf n = 0 Then
Fact = 1
Else
Fact = n * Fact(n - 1)
End If
End Function
4
递归算法
2021/1/15
为说明该递归算法的执行过程，设计调用过程如下：
Private Sub Command1_Click()
Dim s As Double
s = Fact(3)
Print s
End Sub
上述代码用实参n = 3调用了递归算法Fact(3)，而Fact(3)要通过调用Fact(2)、Fact(2)要通过调用Fact(1)、Fact(1)要通过调用Fact(0)来得出计算结果。Fact(3)的递归调用过程如下图所示，其中，黑色实线箭头表示函数调用，绿色虚线箭头表示函数返回，此函数在返回时函数名将带回返回值。
5
递归算法
2021/1/15
Sub Command1_Click()
……
s=Fact(3)
……
End Sub
Function Fact (3)
……
Fact=3*Fact (2)
……
End Function
Function Fact (2)
……
Fact=2*Fact(1)
……
End Function
递归调用的执行过程：
Function Fact (1)
……
Fact=1*Fact(0)
……
End Function
Function Fact (0)
……
ElseIf n = 0 Then
Fact=1
……
End Function
6
递归算法
2021/1/15
例6-2 给出在有序数组a中查找数据元素x是否存在的递归算法，并给出折半查找示意图所示实际数据的递归算法的执行过程。
　　设计：算法的参数包括：有序数组a，要查找的数据元素x，数组下界下标low，数组上界下标high。当在数组a中查找到数据元素x时函数返回数组a的下标；当在数组a中查找不到数据元素x时函数返回-1。
7
递归算法
2021/1/15
递归算法如下：
Function BSearch(a() As Integer, x%, low%, high%) A