对于栈有些问题还不是很熟悉,所以暂时需要些时间去理解,需要多写些代码去体会,,栈还有一个重要应用是在程序设计语言中实现递归,所以这次主要是讲递归的实现,大家熟悉的阶乘函数,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、第八行有位置可以放入皇后。
实现代码如下:
![](https://yqfile.alicdn.com/img_1c53668bcee393edac0d7b3b3daff1ae.gif?x-oss-process=image/resize,w_1400/format,webp)
![](https://yqfile.alicdn.com/img_405b18b4b6584ae338e0f6ecaf736533.gif?x-oss-process=image/resize,w_1400/format,webp)
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 else
78 {
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的时候就结束了,所以解决递归问题首先要有边界条件,否则将死循环;