算法设计与分析之循环与递归

前言：

    循环与递归可以说是算法设计中最基本但却也是最重要的工具方法。循环和递归对于学习过高级程序设计语言的人来说都并不陌生，但还是有必要仔细的探究一下循环和递归之间的相似和区别。循环与递归最大的相似之处莫不是在于他们在算法设计中的工具作用，它们都起到了“以不变应万变”的作用。“不变应万变”不正是程序设计的核心内容吗？正因为如此，更有必要探究一下这两种不同的设计工具的区别。本文先从利用循环和递归工具设计算法时的设计要点来认识循环和递归，然后再给出几个具体的实例来说明循环和递归的差异和优劣。

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();
}

    最后对递归说明一点，递归可以说是一种算法策略，也可以说是一种算法设计的工具，不管从哪一方面来看对算法设计都是很好的帮助。递归在很多算法策略中得以运用，如分治策略、动态规划、图的搜索等算法策略。有很多数据结构都是具有递归定义的，如链表，队列，栈，二叉树。