首页 > 代码库 > 栈与递归的实现
栈与递归的实现
对于栈有些问题还不是很熟悉，所以暂时需要些时间去理解，需要多写些代码去体会，，栈还有一个重要应用是在程序设计语言中实现递归，所以这次主要是讲递归的实现，大家熟悉的阶乘函数，2阶Fibonacci数列和Ackerman函数等，其次还有的数据结构，如二叉树、广义表等，由于结构本身固有的递归特性，则它们的操作可递归的描述，另外还有一类问题，虽然问题本身没有明显的递归结构，但是递归求解比迭代求解更简单，如八皇后问题、Hanoi塔问题等。
递归是一种数学上分而治之的思想，它将大型复杂问题转化为与原问题相同但规模较小的问题进行处理，数学表示如下：
下面我以一个八皇后问题来说一下这儿的递归问题，在一个8X8国际象棋中，有8个皇后，每个皇后占一格，要求皇后间不会出现相互“攻击”的现象，即不能有两个皇后处在同一行，同一列或者同一对角线上。那么怎么来实现这个想法呢?下面是我的算法思路：先给两个了、变量i,j赋值为1，从第i行开始，恢复j的当前值，判断第j个位置。1、位置j可放入皇后，标记位置(i,j)，i++，j = 1； 2、位置j不可放入皇后，j++,i = 1； 3、当j>8时候，j--,继续上述循环； 4、第八行有位置可以放入皇后。
实现代码如下：
1 #include <stdio.h> 2 #define N 8 3 4 typedef struct _tag_Pos 5 { 6 int ios; 7 int jos; 8 } Pos; 9 10 static char board[N+2][N+2];11 static Pos pos[] = { {-1, -1}, {-1, 0}, {-1, 1} };12 static int count = 0;13 14 void init()15 {16 int i = 0;17 int j = 0; 18 for(i=0; i<N+2; i++)19 {20 board[0][i] = ‘#‘;21 board[N+1][i] = ‘#‘;22 board[i][0] = ‘#‘;23 board[i][N+1] = ‘#‘;24 } 25 for(i=1; i<=N; i++)26 {27 for(j=1; j<=N; j++)28 {29 board[i][j] = ‘ ‘;30 }31 }32 }33 34 void display()35 {36 int i = 0;37 int j = 1; 38 for(i=0; i<N+2; i++)39 {40 for(j=0; j<N+2; j++)41 {42 printf("%c", board[i][j]);43 } 44 printf("\n");45 }46 }47 48 int check(int i, int j)49 {50 int ret = 1;51 int p = 0; 52 for(p=0; p<3; p++)53 {54 int ni = i;55 int nj = j; 56 while( ret && (board[ni][nj] != ‘#‘) )57 {58 ni = ni + pos[p].ios;59 nj = nj + pos[p].jos; 60 ret = ret && (board[ni][nj] != ‘*‘);61 }62 }63 64 return ret;65 }66 67 void find(int i)68 {69 int j = 0; 70 if( i > N )71 {72 count++; 73 printf("Solution: %d\n", count); 74 display(); 75 getchar();76 }77 else78 {79 for(j=1; j<=N; j++)80 {81 if( check(i, j) )82 {83 board[i][j] = ‘*‘; 84 find(i+1); 85 board[i][j] = ‘ ‘;86 }87 }88 }89 }90 91 int main()92 {93 init();94 find(1);95 96 return 0;97 }
编译结果如下图：
当不断按Enter的时候，会陆续出现Solution一直到Solutioin92,再按Enter会退出了。如下图
小结：
递归是一种将问题分而治之的思想，解决问题的时候首先就要建立递归的模型；
如上图到Solution92的时候就结束了，所以解决递归问题首先要有边界条件，否则将死循环；
栈与递归的实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。