分類

• 直接遞歸 函數(shù)F的代碼直接包含了調(diào)用F的語句
• 間接遞歸 函數(shù)F調(diào)用了函數(shù)G，G又調(diào)用了H，如此下去一直到F又被調(diào)用

定義

• 遞歸必須包含一個基本部分，對于n的一個或者多個值，f（n)必須是直接定義的。
• 遞歸部分，右側(cè)所出現(xiàn)的所有f的參數(shù)都必須有一個比n小的一邊重復(fù)運用遞歸部分來改變右側(cè)f，直至出現(xiàn)f的基本部分。

歸納證明

• 歸納初值 （induction base）
  對于n的一個或者多個值，要證明的公司是成立的
• 歸納假設(shè) （induction hypothesis）
  然后假定當n屬于0-m的時候公式是成立的，其中m是任意整數(shù)（大于等于驗證索取的最大值）
• 歸納步證明（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]有多個排列方式，遞歸的產(chǎn)生這些排列方式
    {
        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;
}