递归的过程:

递归能够解决问题的两个要素:

• 结束条件:  在递归到多少层之后结束递归
• 接近条件: 每次递归,都更接近结束条件.
• 附加条件: 子问题重叠问题,当递归算法中有重叠子问题,则效率往往极低,(指数时间复杂度).如求斐波那契数.

 

递归算法设计注意点:

• 分支:每次递归产生几个子问题(当含多个子问题,往往每层递归都会带有循环)
  • 当产生多个分支时(事实大多数情况为多个分支),考虑该分支的结束条件和对哪条分支进行递归的递归条件.
  • 当产生单条分支时,分支结束条件即整个问题的结束条件,每次都对这条分支进行递归,但是需要计算出对子问题进行递归起始位置.如(字符串末尾匹配算法:my_strrchr(str+1, ch)):此处,需要计算合理的str.

 

• 方向: 问题的解决是在递归过程中解决,还是满足递归限制条件后回收.
  • 第二种情况往往需要对递归结果进行回收.
  •  

递归算法实例分析:

 

 

字符匹配算法

问题描述: 找出字符串中最后一个与待匹配字符匹配的位置.

分析: 1.结束条件,字符串末尾  2.每次递归调用都接近字符串末尾

代码:

char *my_strrchr(char const *string, char ch)

{

  char const *str = string;

while(*str != '\0') //结束条件,字符串末尾

{

if(*str == ch)    //递归条件

 return my_strrchr(str+1, ch); //递归返回一次后,直接全部退出.

else 

{   

  str++;  //计算str,确定下一次递归调用的子问题.

}

}

return string;

}

 

 

八皇后问题

问题描述:

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上. 

解决思路:

• 按行进行递归,按列进行循环.每当在i行找到满足条件的落子处后,递归到i+1行,利用循环,对该行每列进行判断,是否有满足条件的落子处,当能找到8行都满足条件的落子,则为选出了一种合法的落子方式.
• 当在某一行遍历所有列都不满足落子条件时,已经不可能找出8行满足的落子方式,因此直接退出递归.回到上一层递归,使用循环,找出该行下一个满足条件的落子点.若依然没有合适的落子点,则再次返回上一层递归.

算法设计:

• 方向: 在递归过程中解决问题
• 分支:每次至多产生8个分支,至少产生0个分支.
  • 分支结束条件: 本层无满足合法落子位置
  • 分支递归条件: 本层存在合法落子位置

代码:

void eight_queen(int row, int n, int (*chess)[8])

{

 

/*1.赋值临时数组,因为每一次递归都有失败的风险,当失败的时候便舍弃掉临时数组.*/

int chess2[8][8];

int i, j;

for( i = 0; i < 8; i++ )

for( j = 0; j < 8; j++ )

chess2[i][j] = chess[i][j];

/*2.结束条件1,当结束条件成功,便成功找到了一次八皇后的置放方式

结束条件2,当已经没有安全的列,也会导致递归调用结束,返回上一级递归*/

if( row == 8 )  //成功找到一种放置方式,打印棋盘,返回到上一层递归,继续查找

{

printf( "\n" );   

for( i = 0; i < 8; i++ )  //打印棋盘

{

for( j = 0; j < 8; j++ )   

{

printf( "%2d", chess2[i][j]);

}

printf( "\n" );

}       

}

/*3.递归的主要功能实现,*/

else

{ 

for( i = 0; i< n; i++ ) //对本次递归的行的列依次进行安全检测,找到可以放置皇后的点.

{

if( !safety( row, i, chess ) )     //安全检测的数组需要是数组为原始数组chess而不是chess2,因为chess2可能被修改

{

for( j = 0; j < 8; j++ )

chess2[row][j] = 0; //先清空本列,可能由于本层递归失败的分支已经改变了本层的chess2数组,因此将本列清0

chess2[row][i] = 1;     //当chess2[row][i]安全时,将chess2数组的当前位置放置皇后  ,即设置为1 

eight_queen( row+1, n, chess2 );//递归调用下一行

}

 //若遍历本列,没有找到合法的落子点,则返回上一级递归,上一级继续循环,查找合法的落子点.

}   

}

}

 

 

算法设计与分析实验课3-2

 

解决思路:

循环在矩阵中找到待匹配字符串的第一个字符,找到后,对该元素的四个方向进行判断,找到是否存在下一个待匹配字符.若找到,则进行下一层递归,若没有找到,返回上一层递归,在矩阵中,循环开始步骤.

递归条件:

• 结束条件(找到满足字符串匹配路径或者无路可走)
• 每次都接近结束条件

 

算法设计:

• 分支:最多四条分支.最少0条分支.
  • 分支的结束判断为该分支四周无匹配点或无路可走.
  • 分支的递归条件为该方向满足下一个匹配点.
• 方向:在递归过程中解决