分类
- 直接递归 函数F的代码直接包含了调用F的语句
- 间接递归 函数F调用了函数G，G又调用了H，如此下去一直到F又被调用
定义
- 递归必须包含一个基本部分，对于n的一个或者多个值，f（n)必须是直接定义的。
- 递归部分，右侧所出现的所有f的参数都必须有一个比n小的一边重复运用递归部分来改变右侧f，直至出现f的基本部分。
归纳证明
- 归纳初值 （induction base）
对于n的一个或者多个值，要证明的公司是成立的 - 归纳假设 （induction hypothesis）
然后假定当n属于0-m的时候公式是成立的，其中m是任意整数（大于等于验证索取的最大值） - 归纳步证明（induction step)
如果能够证明对于n的下一个值（m+1)公式也成立，那么就可以确定该公式是成立的。
练习
- 计算阶乘
int factorial(int n)
{
if(n<=1) return 1;
else return n*factoral(n-1);
}
- 求和
累加
templeate<class T>
T sum(T a[],int n)
{
T tsum=0;
for (int i=0;i<n;i++)
{
tsum+=a[I];
}
retuan tsum;
}
递归运算
T rsum(T a[],int n)
{
if (n>0)
return rsum(a,n-1)+a[n-1];
return 0;
}
-
排列组合
排列.png
组合.png
template<class T>
void perm(T list[],int k,int m)
{//生成list[k:m]的所有排列
int i;
if (k==m){//输出一个排列方式
for( i = 0; i<=m;i++)
cout<<list[i];
cout<<endl;
}
else//list[k:m]有多个排列方式，递归的产生这些排列方式
{
for ( i = k; i<=m;i++)
{
swap(list[k],list[I]);
perm(list,k+1,m);
swap(list[i],list[k]);
}
}
}
inline void swap(T& a, T&b)
{//交换a和b
T temp = a;
a=b;
b=temp;
}
