算法設計與分析之循環與遞歸

前言：

    循環與遞歸可以說是算法設計中最基本但卻也是最重要的工具方法。循環和遞歸對于學習過高級程序設計語言的人來說都并不陌生，但還是有必要仔細的探究一下循環和遞歸之間的相似和區別。循環與遞歸最大的相似之處莫不是在于他們在算法設計中的工具作用，它們都起到了“以不變應萬變”的作用。“不變應萬變”不正是程序設計的核心內容嗎？正因為如此，更有必要探究一下這兩種不同的設計工具的區別。本文先從利用循環和遞歸工具設計算法時的設計要點來認識循環和遞歸，然后再給出幾個具體的實例來說明循環和遞歸的差異和優劣。

1.循環設計要點

    循環設計的要點可以概括為三個部分：效率、正向思維、具體到抽象。下面以不同的具體實例來討論這三個要點。

1.1效率

    例1.1 求1/1!-1/3!+1/5!-1/7!+....+(-1)^(n+1)/(2n-1)!

    算法1：使用二重循環實現，循環不變式為：s(n)=s(n-1)+(-1)^(n+1)/(2n-1)!。這樣的算法的時間復雜度為O(n^2)。針對本題有沒有時間復雜度為O(n)的算法呢？

    算法2：循環不變式：s(n)=s(n-1)+(-1)^(n+1)A(n); A(n)=A(n-1)*1/((2*n-2)*(2*n-1))。這個算法的時間復雜度為O(n)。其C++代碼實現如下：   

#include <iostream>
using namespace std;

int main(void){
 int n;
 cout<<"Please input a number:"<<endl;
 cin>>n;
 float sum=1; //存儲結果
 float t=1;// 存儲階乘
 int sign=1; //存儲負號

 //循環
 for(int i=2; i<=n; i++){
  sign=-sign;
  t=t*(2*i-2)*(2*i-1);
  sum+=sign/t;
 }
 cout<<"Result is: "<<sum<<endl; 
}

1.2正向思維

    正向思維的方法是從全局到局部、從概略到詳細的設計方法。是對一個問題由整體到分解和細化的方法。這也是循環設計的一般方法。下面求完數的例子可以說明正向思維設計要點的過程。

    例1.2  一個數如果恰好等于它的因子之和（包括1但不包括這個數本身），這個數就成為完數。

    1）頂層算法

        for（i=1; i<=n; i++){

            判斷i是否為完數；

            是完數，輸出；

        }

    2）判斷i是否為完數的算法

        for(j=2; j<i; j++)

            計算i的因子，并累加；

            如果累加的值為i，輸出i；

    3）進一步細化判斷i是否為完數的算法

        s=1;

        for(j=2; j<i; j++){

            if(i mod j ==0)

                s += j;

        }

        if(s==i)

            輸出i；

1.3具體到抽象

    具體到抽象的方法也可以說成是數學歸納法。數學歸納法可以說是算法設計中非常重要的一種方法。算法設計的本質，可以說就是在看似雜亂無章的信息中總結歸納出一種不變的規律，以不變應萬變。下面的這個打印規則圖形的例子可以說明這點。

    例1.3  打印具有下圖規律的圖形

        1

        5     2

        8     6    3

        10   9    7    4

算法C++實現如下：

#include<iostream>
#define N 10
using namespace std;
int main(void){
 int a[N+1][N+1];
 int k=1;
 for(int i=1; i<=N; i++)
  for(int j=1; j<=N+1-i; j++)
   a[i+j-1][j]=k++;

 for(int i=1; i<=N;i++){
  for(int j=1; j<=i; j++)
   cout<<a[i][j]<<" "; 
  cout<<endl; 
 }  
} 

2.遞歸設計要點

    遞歸設計方法，也可以叫做逆向思維方法（對比與循環設計的正向思維）。遞歸設計通常有以下三個步驟：

    （1）尋找遞歸關系：找出大規模問題于小規模問題的關系，這樣通過遞歸是問題的規模逐漸變小。

    （2）找出遞歸停止的條件，即算法可解的最小規模問題。

    （3）設計函數，確定函數所需參數。

    下面給出一個整數劃分問題的遞歸算法設計：

    列2.1  求一個整數劃分的種類數。列如6有11種劃分如下：

        6

        5+1

        4+2                    4+1+1

        3+3                    3+2+1                    3+1+1+1

        2+2+2                2+2+1+1                2+1+1+1+1

        1+1+1+1+1+1+1

算法描述及C++實現：

/*
*定義一個函數Q(n,m)表示整數n的任何加數都不超過m的劃分數目
*n的所有劃分數目P(n)就應該表示為Q(n,n).
*
*一般Q(n,m)有如下遞歸關系：
*Q(n,n)=1+Q(n,n-1);
*Q(n,m)=Q(n,m-1)+Q(n-m,m)
*右邊第一部分表示不包含m的劃分，第二部分表示包含m的劃分
*那么就意味著剩下的部分就是對n-m進行不超過m的劃分。
*
*遞歸的停止條件：
*Q(n,1)=1,表示當最大的被加數是1時，該整數n只有一種劃分
*Q(1,m)=1,表示整數1只有一個劃分，不管最大被加數的上限
*是多少。
*
*算法的穩健性：
*如果n<m,則Q(n,m)是無意義的，此時Q(n,m)=Q(n,n)
*同樣的當n<1或m<1時，Q(n,m)也是無意義的。 
*/

#include<iostream>
using namespace std;

int Divinteger(int n, int m){

 if( n<1||m<1 )//錯誤條件 
  cout<<"Error input!"<<endl;

 else if( n==1||m==1 )//停止條件 
  return 1;

 else if( n<m )//穩健條件 
  return Divinteger(n, n);

 else if( n==m )// Q(n,n)=1+Q(n,n-1)
  return (1+Divinteger(n, n-1)); 

 else //Q(n,m)=Q(n,m-1)+Q(n-m,m)
  return (Divinteger(n, m-1)+Divinteger(n-m, m));
} 

int main(void){
 int n;
 cout<<"Please input a number:"<<endl;
 cin>>n;
 cout<<"Result is: "<<Divinteger(n,n)<<endl;
}

3.循環與遞歸的比較

    這個部分以不同的例子引出三個結論。

3.1結論1：在具體實現時，方便的情況下應該把遞歸算法轉化成等價的循環結構算法，以提高算法的時空效率。

    例3.1 將一個十進制整數由低位到高位按位輸出。

/*
* 將一個十進制整數從低位到高位逐位輸出 
* 循環不僅在時間而且在空間效率均高于遞
* 歸程序。 
*/

void for_low_to_high(int n){
 while(n){
  cout<<n%M<<" ";
  n=n/M;
 }
 cout<<endl;
}

void f_ltoh(int n){
 if(n<M)
  cout<<n<<endl;
 else{
  cout<<n%M<<" ";
  f_ltoh(n/M);
 }
}

    例3.2 將一個十進制整數由高位到低位按位輸出。

/*
* 將一個十進制整數從高位到低位逐位輸出 
* 循環與遞歸空間效率一樣，雖然時間效率
* 有差異，但遞歸程序間單可讀性好。 
*/ 

void for_high_to_low(int n){

 int i=0;int a[16];
 while(n){
  a[i]= n%M;
  n=n/M;
  i++;
 }
 for(int j=i-1; j>=0; j--)
  cout<<a[j]<<" ";
 cout<<endl;

} 

void f_htol(int n){
 if(n<M)
  cout<<n<<" ";
 else{
  f_htol(n/M);
  cout<<n%M<<" ";
 }
}
3.2結論2：當問題需要后進先出的操作時，還是遞歸算法更有效 。如樹的遍歷和圖的深度優先算法等都是如此。所以不能僅僅從效率上評價兩種控制重復操作機制的好壞。

    例3.3 用2的冪次方表示一個正整數。例如：137=2^7+2^3+2^0,則137可表示為： 2(7)+2(3)+2(0),進一步：7=2^2+2+2^0,3=2+2^0 所以137可表示為：2(2(2)+2+2(0))+2(2+2(0))+2(0) 。

算法的C++實現：

#include<iostream>
using namespace std;

void tryf(int n, int r=0){//n為數，r為深度 
 if(n==1)//遞歸結束條件 
  cout<<"2("<<r<<")";
 else{//n除以2,深度加1 
  tryf(n/2,r+1);
  if(n%2==1)//如果余數不為0輸出2的r冪次 
   cout<<"+2("<<r<<")";
 }
}

void tryff(int n, int r=0){
 if(n==1){
  switch(r){
   case 0:cout<<"2(0)";break;
   case 1:cout<<"2";break;
   case 2:cout<<"2(2)";break;
   default:{cout<<"2(";tryff(r, 0);cout<<")";}
  }
 }else{
  tryff(n/2, r+1);
  if(n%2==1){
   switch(r){
    case 0:cout<<"+2(0)";break;
    case 1:cout<<"+2";break;
    case 2:cout<<"+2(2)";break;
    default:{cout<<"+2(";tryff(r, 0);cout<<")";}
   }//switch
  }//if 
 }//else
}

int main(void){
 int n;
 cout<<"Please input a number:"<<endl;
 cin>>n;
 if(n>1){
  tryf(n);
  cout<<endl;
  tryff(n);
 }else
  cout<<"Inupt Error!"<<endl;
} 

3.3結論3：遞歸是一種強有力的算法設計工具。遞歸是一種比循環更強、更好用的實現重復操作的機制。因為遞歸不需要編程者自己構造循環不變式，而只需找出遞歸關系和最小問題的解。遞歸在很多算法策略中得以運用，如分治策略、動態規劃、圖的搜索等算法策略。

    由下面的例子可以看出遞歸的層次可以控制的，而循環嵌套的層次只能是固定的。

    例3.4 找出n個自然數（1,2,3,4,5,.....,n)中取r個數的組合。

算法C++實現：

#include <iostream>
#define N 5
#define R 3 
using namespace std;

void for_fun1(){
 int t=0;
 for(int i=1; i<=N; i++)
  for(int j=1; j<=N; j++)
   for(int k=1; k<=N; k++)
    if( (i<j) && (j<k) ){
     t++;
     cout<<i<<" "<<j<<" "<<k<<endl; 
    }
 cout<<"Total= "<<t<<endl;
}

//more efficiency
void for_fun2(){
 int t=0;
 for(int i=1; i<=N-R+1; i++)
  for(int j=i+1; j<=N-R+2; j++)
   for(int k=j+1; k<=N-R+3; k++){
    t++;
    cout<<i<<" "<<j<<" "<<k<<endl;
   }
}

//recruisive 
int a[100];
int t=0;
void comb(int n, int r){
 for(int i=n; i>=r; i--){//循環n-r+1次 
  a[r]=i;//n中選r個數，確定第一個數 
  if(r>1){//遞歸深度為r 
   comb(i-1,r-1);
  }
  else{//結束條件為深度r等于1 
   for(int j=a[0]; j>0; j--)
     cout<<a[j]<<" ";
    cout<<endl;
    t++;
  }
 }
} //算法復雜度O(n*r)
void rec_fun(){
 a[0]=R;
 comb(N,R);
 cout<<"Total= "<<t<<endl;
} 

int main(void){
 for_fun1();
 for_fun2();
 rec_fun();
}

    最后對遞歸說明一點，遞歸可以說是一種算法策略，也可以說是一種算法設計的工具，不管從哪一方面來看對算法設計都是很好的幫助。遞歸在很多算法策略中得以運用，如分治策略、動態規劃、圖的搜索等算法策略。有很多數據結構都是具有遞歸定義的，如鏈表，隊列，棧，二叉樹。