算法--递归策略

本文地址： http://www.cnblogs.com/archimedes/p/algorithm-recursion.html ，转载请注明源地址。

递归的概念与基本思想

一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。

递归的实现方法

递归是借助于一个递归工作栈来实现；递归=递推+回归；

递推：问题向一极推进,这一过程叫做递推；这一过程相当于压栈。

回归：问题逐一解决，最后回到原问题，这一过程叫做回归。这一过程相当于弹栈。

例如：用递归算法求 n!

定义：函数 fact(n)=n!

fact(n-1)=(n-1)!

则有  fact(n)=n*fact(n-1)

已知  fact(1)=1

下面画出了调用和返回的递归示意图：

递归实现的代价是巨大的栈空间的耗费，那是因为过程每向前递推一次，程序将本层的实在变量（值参和变参）、局部变量构成一个“工作记录”压入工作栈的栈顶，只有退出该层递归时，才将这一工作记录从栈顶弹出释放部分空间。由此可以想到，减少每个“工作记录”的大小便可节省部分空间。例如某些变参可以转换为全局变量，某些值参可以省略以及过程内部的精简。

【例题】写出结果

#include<iostream> using namespace std; void rever() {  char c;  cin>>c;  if(c!='!') rever();  cout<<c; } int main( ) {  rever();  system("PAUSE");  return 0; } 

【样例输入】gnauh！        【样例输出】!huang

采用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。

递归算法的类型

递归算法可以分为两种类型：

基于分治策略的递归算法；

基于回溯策略的递归算法。

基于分治策略的递归算法

分而治之（divide-and-conquer）的算法

设计思想：

1.Divide：把问题划分为若干个子问题；

2.Conquer：以同样的方式分别去处理各个子问题；

3.Combine：把各个子问题的处理结果综合起来，形成最终的处理结果。

如何编写基于分治策略的递归程序？

在算法分析上，要建立分治递归的思维方式。

在编程实现上，要建立递归信心（To turst the recursion,  Jerry Cain,  stanford）。

如何建立分治递归的思维方式？

基本原则：目标驱动！

计算n!：n! = n * (n-1)!，且1! = 1。

int  main( ) {  int   n;  printf("请输入一个整数：");  scanf("%d",   &n);  printf("%d!  =  %d /n",   n,   fact(n));  return 0 } int   fact(int  n) {  if(n  ==  1)    return(1);  else     return(n * fact(n-1)); } 

int Max(int a[], int first, int n) {  int  max;  if(first == n-1)  return a[first];  max = Max(a, first+1, n);  if(max < a[first])     return a[first];  else  return max; } 

int bsearch(int b[], int x, int L, int R) {  int mid;  if(L > R) return(-1);  mid = (L + R)/2;  if(x == b[mid])    return mid;  else if(x < b[mid])    return bsearch(b, x, L, mid-1);  else    return bsearch(b, x, mid+1, R); } 

代码如下：

#include  <stdio.h> void   move(int n, char L, char M, char R); int main( ) {  int   n;  printf("请输入一个整数：");  scanf("%d",  &n);  move(n,  'A',  'B',  'C');  return 0; } // L: Left post,  M: Middle post,  R: Right post void  move(int n, char L, char M, char R) {  if(n  ==  1)       printf("move #1 from %c to %c/n",  L,  R);  else  {      move(n-1,  L,  R,  M);      printf("move #%d from %c to %c/n",  n,  L,  R);      move(n-1,  M,  L,  R);  } } 

基于回溯策略的递归

在程序设计当中，有相当一类求一组解、或求全部解或求最优解的问题，不是根据某种确定的计算法则，而是利用试探和回溯（Backtracking）的搜索技术求解。回溯法也是设计递归算法的一种重要方法，它的求解过程实质上是一个先序遍历一棵“状态树”的过程，只不过这棵树不是预先建立的，而是隐含在遍历的过程当中。

例题：分书问题

有五本书，它们的编号分别为1，2，3，4，5，现准备分给 A, B, C, D, E五个人，每个人的阅读兴趣用一个二维数组来加以描述：

希望编写一个程序，输出所有的分书方案，让人人皆大欢喜。

假定这5个人对这5本书的阅读兴趣如下表：

思路：

1、定义一个整型的二维数组，将上表中的阅读喜好用初始化的方法赋给这个二维数组。可定义：

int  Like[6][6] = {{0}, {0, 0,0,1,1,0},                          {0, 1,1,0,0,1},                         {0, 0,1,1,0,1},                          {0, 0,0,0,1,0},                                              {0, 0,1,0,0,1}};

2、定义一个整型一维数组BookFlag[6]用来记录书是否已被选用。用后五个下标作为五本书的标号，被选用的元素值为1, 未被选用的值为0, 初始化皆为0.

int  BookFlag[6] = {0};

3、定义一个整型一维数组BookTaken[6]用来记录每一个人选用了哪一本书。用数组元素的下标来作为人的标号，用数组元素的值来表示书号。如果某个人还没有选好书，则相应的元素值为0。初始化时，所有的元素值均为0。

int  BookTaken[6] = {0};

4、循环变量 i 表示人，j 表示书，i, j  ε{1, 2, 3, 4, 5}

把所有可能出现的分书方案都枚举出来，然后逐一判断它们是否满足条件，即是否使得每个人都能够得到他所喜欢的书。 缺点：计算量太大。

#include<stdio.h> void person(int i); int Like[6][6] = {{0}, {0, 0, 0, 1, 1, 0},          {0, 1, 1, 0, 0, 1},         {0, 0, 1, 1, 0, 1},          {0, 0, 0, 0, 1, 0},          {0, 0, 1, 0, 0, 1}}; int BookFlag[6] = {0}; int BookTaken[6] = {0}; int main( ) {  person( 1 );  return 0; } void  person(int  i) // 尝试给第i个人分书 {   int  j,  k;  for(j = 1;  j <= 5;  j++) // 尝试把每本书分给第i个人  {      if((BookFlag[j] != 0) || (Like[i][j] == 0))   continue; // 失败   BookTaken[i] = j;    // 把第j本书分给第i个人   BookFlag[j] = 1;   if(i == 5){  // 已找到一种分书方案    for(k = 1; k <= 5; k++) printf("%d ", BookTaken[k]);    printf("/n");   }   else{    person(i + 1); // 给第i+1个人分书   }   BookTaken[i] = 0; // 回溯，把这一次分得的书退回   BookFlag[j] = 0;  } } 

例题：八皇后问题

在8×8的棋盘上，放置8个皇后（棋子），使两两之间互不攻击。所谓互不攻击是说任何两个皇后都要满足：

因此可以推论出，棋盘共有8行，故至多有8个皇后，即每一行有且仅有一个皇后。这8个皇后中的每一个应该摆放在哪一列上是解该题的任务。

数据的定义（1）：

i —— 第i行（个）皇后，1 ≤ i ≤ 8；

j —— 第j列， 1 ≤ j ≤ 8；

Queen[i] —— 第i行皇后所在的列；

Column[j]—— 第j列是否安全，{0, 1}；

数据的定义（2）：

Down[-7..7 ]——记录每一条从上到下的对角线，是否安全，{0,1}

Up[2..16]——记录每一条从下到上的对角角线，是否安全，{0,1}

利用以上的数据定义：

当我们需要在棋盘的( i, j ) 位置摆放一个皇后的时候，可以通过Column数组、Down数组和Up数组的相应元素，来判断该位置是否安全；

当我们已经在棋盘的( i, j ) 位置摆放了一个皇后以后，就应该去修改Column数组、Down数组和Up数组的相应元素，把相应的列和对角线设置为不安全。

代码如下：

void TryQueen(int  i); int   Queen[9]   =  { 0 }; int   Column[9]  =  { 0 }; int   Down[15]   =  { 0 }; int   Up[15]  =  { 0 }; int  main( ) {   TryQueen(1);  return 0; } void TryQueen(int i) // 摆放第 i 行的皇后 {  int   j,  k;  for(j = 1;  j <= 8;  j++) // 尝试把该皇后放在每一列  {      if(Column[j] || Down[i-j+7] || Up[i+j-2])   continue; // 失败   Queen[i] = j;  // 把该皇后放在第j列上   Column[j] = 1; Down[i-j+7] = 1; Up[i+j-2] = 1;   if(i  ==  8) // 已找到一种解决方案   {    for(k = 1; k <= 8; k++)   printf("%d  ",   Queen[k]);    printf("/n");   }   else TryQueen(i + 1); // 摆放第i+1行的皇后   Queen[i] = 0; // 回溯，把该皇后从第j列拿起   Column[j] = 0; Down[i-j+7] = 0; Up[i+j-2] = 0;  } } 

例题：过河问题

问题描述：

M条狼和N条狗（N≥M）渡船过河，从河西到河东。在每次航行中，该船最多能容纳2只动物，且最少需搭载1只动物。安全限制：无论在河东、河西还是船上，狗的数量不能小于狼的数量。请问：能否找到一种方案，使所有动物都能顺利过河。如果能，移动的步骤是什么？

问题分析：

如何描述系统的当前状态？

位置：河西岸、河东岸、河；

对象：船、狼、狗。

三元组（W、 D、 B）       （其中：W代表Wolf；D代表Dog；B代表Boat）

例如：(2, 2, W)

(2, 2, W)--> (0, 2, E)--> (1, 2, W)--> (1, 0, E) -->(2, 0, W) -->(0, 0, E)

第一步：带2只狼到E，则W剩下0只狼，2只羊  (0, 2, E)

第二步：带1只狼到W，则W剩下1只狼，2只羊  (1, 2, W)

第三步：带2只羊到E，则W剩下1只狼，0只羊   (1, 0, E)

第四步：带1只狼到W，则W剩下2只狼，0只羊  (2, 0, W)

第五步：带2只狼到E，则W剩下0只狼，0只羊  (0, 0, E)

1.问题实质：在一个有向图中寻找一条路径；

2.状态转换：如何从一个结点跳转到另一个结点；

代码如下：

#include <stdio.h> #define MAX_M   20 #define MAX_N   20 int M, N; struct Status  //构建三元组 {  int W, D, B; }steps[1000]; int s = 0, num = 0; int flags[MAX_M][MAX_N][2] = {0}; void CrossRiver(int W, int D, int B); int IsValid(int w, int d, int b); int main( ) {  scanf("%d %d", &M, &N);  flags[M][N][0] = 1; //初始状态(M,N,W)  steps[0].W = M;  steps[0].D = N;  steps[0].B = 0;  s = 1;  CrossRiver(M, N, 0);  return 0; } void CrossRiver(int W, int D, int B)  {  int i, j, f;  int w, d, b;  if(B == 0) f = -1;  else f = 1;  for(j = 1; j <= 5; j++)  {   switch(j)   {    case 1:  w = W + f*1;  d = D;  break;    case 2:  w = W + f*2;  d = D;  break;    case 3:  d = D + f*1;  w = W;  break;    case 4:  d = D + f*2;  w = W;  break;    case 5:  w = W + f*1;  d = D + f*1; break;   }   b = 1 - B;   if(IsValid(w, d, b))   {    flags[w][d][b] = 1;    steps[s].W = w;    steps[s].D = d;    steps[s].B = b;    s++;    if(w == 0 && d == 0 && b == 1)    {     num ++;     printf("Solutions %d: /n", num);     for(i = 0; i < s; i++) printf("%d %d %d/n", steps[i].W,         steps[i].D, steps[i].B);    }    else  CrossRiver(w, d, b);    flags[w][d][b] = 0;    s--;     }  } } int IsValid(int w, int d, int b) //判断三元组的某一状态是否合法 {  if(w < 0 || w > M) return 0;   if(d < 0 || d > N) return 0;   if(flags[w][d][b] == 1) return 0;    if(d > 0 && w > d)  return 0;     if((N-d > 0) && (M-w > N-d)) return 0;  return 1; } 

例题：排列问题

n个对象的一个排列，就是把这 n 个不同的对象放在同一行上的一种安排。例如，对于三个对象 a,b,c，总共有6个排列：

a   b   c

a   c   b

b   a   c

b   c   a

c   a   b

c   b   a

n 个对象的排列个数就是 n!。

如何生成排列？

基于分治策略的递归算法：

假设这 n 个对象为 1, 2, 3, …, n；

例如：生成1,2,3的所有排列

permutation(3) -> permutation(2) -> permutation(1)

permutation(1)：1

permutation(2)：2  1，1  2

permutation(3)：3  2  1，2  3  1，2  1  3，

3  1  2，1  3  2，1  2  3

基于回溯策略的递归算法：

基本思路：每一个排列的长度为 N，对这N个不同的位置，按照顺序逐一地枚举所有可能出现的数字。

定义一维数组NumFlag[N+1]用来记录1-N之间的每一个数字是否已被使用，1表示已使用，0表示尚未被使用，初始化皆为0；

定义一维数组NumTaken[N+1]，用来记录每一个位置上使用的是哪一个数字。如果在某个位置上还没有选好数字，则相应的数组元素值为0。初始化时，所有元素值均为0；

循环变量 i 表示第 i 个位置，j 表示整数 j，i, j ε{1, 2, …, N}。

代码如下：

#include <stdio.h> #define N 3 void   TryNumber( int  i ); int   NumFlag[N+1]  =  {0}; int   NumTaken[N+1]  =  {0}; int main( ) {  TryNumber( 1 );  return 0; } void TryNumber(int i)  {   int j, k;   for(j = 1;  j <= N;  j++)   {       if(NumFlag[j]  !=  0)   continue;     NumTaken[i] = j;    NumFlag[j] = 1;    if(i == N)    {      for(k = 1; k <= N; k++) printf("%d ", NumTaken[k]);      printf("/n");    }    else  TryNumber(i + 1);    NumTaken[i] = 0;    NumFlag[j] = 0;  } } 

你可能感兴趣的：

递归与尾递归（C语言）

递归练习(C语言)

算法--递推策略

递推求解专题练习

算法--枚举策略