2021年递归算法2.ppt

分治法的设计思想是，将一个难以直接解决的大问题，
分割成一些规模较小的相同问题，以便各个击破，
分而治之。
凡治众如治寡，分数是也。
----孙子兵法
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
2021/1/15
1
递归算法2
直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。
分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
2021/1/15
2
递归算法2
递归的概念
例1 阶乘函数
阶乘函数可递归地定义为：
边界条件
递归方程
边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。
Int Factorial(int n)
{ if(n==0) return 1;
return n* Factorial(n-1);
}
2021/1/15
3
递归算法2
例2 Fibonacci数列
无穷数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。它可以递归地定义为：
边界条件
递归方程
第n个Fibonacci数可递归地计算如下：
int fibonacci(int n)
{
if (n <= 1) return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
2021/1/15
4
递归算法2
例3 排列问题
设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。
设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}表示R去掉元素ri后所剩元素构成的集合。
集合X中元素的全排列记为perm(X)。
(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下：
当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；
当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。
见程序事例
2021/1/15
5
递归算法2
1
2
3
4
1
2
4
3
1
3
2
4
1
3
4
2
1
4
2
3
1
4
3
2
2
1
3
4
2
1
4
3
2
3
1
4
2
3
4
1
2
4
1
3
2
4
3
1
3
2
1
4
3
2
4
1
3
1
2
4
3
1
4
2
3
4
2
1
3
4
1
2
1
2
3
4
1 ↔ 2
2
1
3
4
2
1
3
4
1 ↔ 2
1
2
3
4
1
2
3
4
1 ↔ 3
3
2
1
4
3
2
1
4
1 ↔ 3
1
2
3
4
1
2
3
4
1 ↔ 4
4
2
3
1
2021/1/15
6
递归算法2
Template <class type>
void Prem(Type list[], int k, int m)
{//
if(k==m)
{//
for(int i=0;i<=m; i++)
cout <<list[i];
cout <<endl;
}
else //
for( int i=k ; i<=m ;i++)
{
Swap(list[k],list[i]);
Prem(list,k+1,m);
Swap(list[k],list[i]);
}
}
template < class Type>
inlink void Swap(Type &a,Type &b)
{
Type temp=a; a=b; b=temp;
}
2021/1/15
7
递归算法2
例4 Hanoi塔问题
设a,b,c