文档介绍：递归的概念
直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。
由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。
分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。
下面来看几个实例。
例1 阶乘函数
阶乘函数可递归地定义为:
边界条件
递归方程
边界条件与递归方程是递归函数的二个要素,递归函数只有具备了这两个要素,才能在有限次计算后得出结果。
例2 i数列
无穷数列1,1,2,3,5,8,13,21,34,55,……,i数列。它可以递归地定义为:
边界条件
递归方程
i数可递归地计算如下:
int i(int n)
{
if (n <= 1) return 1;
return i(n-1)+i(n-2);
}
例3 Ackerman函数
当一个函数及它的一个变量是由函数自身定义时,称这个函数是双递归函数。Ackerman函数A(n,m)定义如下:
本例中的Ackerman函数却无法找到非递归的定义。
例4 排列问题
设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。
设R={r1,r2,…,rn}是要进行排列的n个元素,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)构成。
template<class type>
void perm(type list[], int k, int m)
{ if (k==m)
//输出一个排列
else
for (int i=k ; i<=m; i++)
{ swap(list[k], list[i]);
perm(list, k+1, m);
swap(list[k], list[i]);
}
}
eg: list[]={1, 2, 3, 4}
k
输出结果:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
……
函数调用: perm(list, 0, n-1)。求n个元素的排列,应有n!种,输出n!种排列时间性能nn!
template<class type>
void perm(type list[], int k, int m)
1 { if (k==m)
//输出一个排列
else
4 for (int i=k ; i<=m; i++)
5 { swap(list[k], list[i]);
6 perm(list, k+1, m);
7 swap(list[k], list[i]);}
9 }
eg: list[]={1, 2, 3, 4}
perm({1, 2,3,4})
//*perm(list,1,4) k=1,m=4
i=1 k=1; list[1]list[1] {1,2,3,4}
1 perm({2,3,4}) k=k+1=2
i=2 list[2]list[2]
2 perm({3,4}) k=k+1=3
i=3 k=3 list[3]list[3]
3 perm({4}) k=k+1=4
k=m: 输出; perm({4}) 结束;
退栈;返回执行7语句
list[3]list[3]
i=i+1=4, k=3 list[3]list[4]
4 perm({3}) k=k+1=4
k=m: 输出; perm({4}) 结束;
退栈;返回执行7语句
list[3]list[4]
i=i+1=5, i>m for 结束,即perm({3,4})结束
list[2]list[2]
i=i+1=3 list[2]list[3]
3 perm({2,4}) ……
i=i+1=4 list[2]list[4]
4 perm({3,2}) ……
i=i+1=2 list[1]list[2] {2,1,3,4}
i=i+1=2 list[1]list[2] {2,1,3,4}
2 perm({1,3,4}) k=k+1=2
i=k=2 list[2]list[2]
1 perm({3,4}) k=k+1=3
……
list[2]lis