递归

分类

• 直接递归 函数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;
}