递归与栈的转化（迷宫+n皇后+汉诺塔）

参考：

《数据结构教程》第五版 李春葆

⼀，递归到⾮递归的转换1，递归的分类

　　递归可分为尾递归和⾮尾递归2，尾递归

　　① 如果⼀个递归过程会 递归函数中的递归调⽤语句是最后⼀条语句，则称这种递归调⽤为尾递归　　② ⼀般情况下，尾递归可以通过循环或者迭代⽅式转化为等价的⾮递归算法。3，⾮尾递归

　　① 对于⾮尾递归算法 ，在理解递归调⽤实现过程的基础上可以⽤栈来模拟递归执⾏过程。4，总结

　　尾递归需要只⽤到递归函数的搜索功能，所以可以⽤循环替换；

　　⽽⾮尾递归除了循环部分，还⽤到了递归函数的回溯功能，所以只能⽤栈模拟。

⼆，⼀个栈帧只有⼀个递归函数的递归转化1，迷宫寻路递归：

#define _CRT_SECURE_NO_WARNINGS#include#include#define N 1111int n, m, cnt;int map[N][N];

int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };struct Node{

int x, y;}way[N];void show(){

printf(\"(0,0)\");

for (int i = 0; i < cnt; i++)

printf(\"->(%d,%d)\", way[i].x, way[i].y); puts(\"\");}

void DFS(int a, int b){

if (a == n - 1 && b == m - 1) {

show(); return; }

for (int i = 0; i < 4; i++) {

if (a + dx[i] < 0 || b + dy[i] < 0 || a + dx[i] >= n || b + dy[i] >= m) continue;

if (map[a + dx[i]][b + dy[i]] == 0) {

map[a][b] = 1;

way[cnt].x = a + dx[i], way[cnt].y = b + dy[i]; cnt++;

DFS(a + dx[i], b + dy[i]);

cnt--;

map[a][b] = 0; } }}

int main(void){

// ⼊⼝是 map[0][0], 出⼝是 map[m-1][n-1] while (scanf(\"%d%d\", &n, &m) != EOF) {

for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf(\"%d\", &map[i][j]); cnt = 0; DFS(0, 0); }

system(\"pause\"); return 0;}/*

测试数据第⼀组6 5

0 0 1 1 10 0 0 0 11 0 1 0 1

1 0 1 0 11 1 1 0 11 0 1 0 0结果

(0,0)->(0,1)->(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)(0,0)->(1,0)->(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)第⼆组6 5

0 0 1 1 10 0 0 0 11 0 1 0 11 0 1 0 11 0 1 0 11 0 0 0 0结果

(0,0)->(0,1)->(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)(0,0)->(0,1)->(1,1)->(2,1)->(3,1)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)(0,0)->(1,0)->(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)(0,0)->(1,0)->(1,1)->(2,1)->(3,1)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)*/

View Code 栈：

#define _CRT_SECURE_NO_WARNINGS#include#include#define N 101

#define MaxSize 10086

int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };int map[N][N];typedef struct Box{

int x, y;

int di; // 点的编号}bx;

typedef Box any; // 可修改数据类型typedef struct SqStack // 顺序栈{

#define MaxSize 666 any a[MaxSize];

int pt; // 栈顶指针 SqStack() { pt = -1; }

void push(any e) { // ⼊栈 a[++pt] = e; }

void pop() { // 出栈 pt--; }

any top() { // 取栈顶元素 return a[pt]; }

bool empty() { // 判断栈是否为空 return pt == -1; }

int size() { // 返回栈的⼤⼩ return pt + 1; }}st;

void show(st s){

st t;

while (!s.empty()) {

bx v = s.top(); s.pop(); t.push(v); }

int cnt = 0;

while (!t.empty()) {

bx v = t.top(); t.pop();

if (cnt++ == 0)

printf(\"(%d,%d)\", v.x, v.y); else

printf(\"->(%d,%d)\", v.x, v.y); }puts(\"\");}

int n, m;

void dfs(int xi, int yi){

st s; // 定义栈 bx start = { xi,yi,0 }; map[xi][yi] = -1;

s.push(start); // 起点进栈

int cnt = 1; // 记录路径数 while (!s.empty()) {

// 1，取栈顶元素，相当于函数形参 bx vertex = s.top();

// 2，找到终点，回溯（关键点：消除搜索的痕迹） if (vertex.x == n - 1 && vertex.y == m - 1) {

show(s); s.pop();

map[vertex.x][vertex.y] = 0; continue; }

// 3，如果有路可⾛，就继续搜索

int find = 0; // find = 1 表⽰下⼀步可⾛，0 表⽰下⼀步不可⾛ for (int i = vertex.di; i < 4; i++) {

bx next{ vertex.x + dx[i], next.y = vertex.y + dy[i] ,0 }; if (next.x < 0 || next.y < 0 || next.x >= n || next.y >= m) continue;

if (map[next.x][next.y] == 0) {

find = 1;

vertex.di = i + 1; // 标记这个⽅块 已经⾛过的⽅向，⼿动确定回溯时不会重复回溯。 s.pop();

s.push(vertex);

// 继续搜索 s.push(next);

map[next.x][next.y] = 1;

break; // ⼀次只⼊栈⼀个元素，同⼀层的其他元素在回溯时再⼊栈 } }

// 4，⾛到死胡同，回溯（关键点：消除搜索的痕迹） if (!find) {

s.pop();

map[vertex.x][vertex.y] = 0; } }}

int main(void){

while (scanf(\"%d%d\", &n, &m) != EOF) {

for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf(\"%d\", &map[i][j]); dfs(0, 0); }

system(\"pause\"); return 0;}/*

测试数据第⼀组6 5

0 0 1 1 10 0 0 0 11 0 1 0 11 0 1 0 11 1 1 0 11 0 1 0 0结果

(0,0)->(0,1)->(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)(0,0)->(1,0)->(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)第⼆组6 5

0 0 1 1 10 0 0 0 11 0 1 0 1

1 0 1 0 11 0 1 0 11 0 0 0 0结果

(0,0)->(0,1)->(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)(0,0)->(0,1)->(1,1)->(2,1)->(3,1)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)(0,0)->(1,0)->(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)(0,0)->(1,0)->(1,1)->(2,1)->(3,1)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)*/

View Code

2，⼋皇后递归：

#define _CRT_SECURE_NO_WARNINGS#include#include

int queen[10]; // queen[i] 代表第 i ⾏的皇后的位置int vis[10]; // vis[i] 代表第 i 列的皇后位置是否确认int n, cnt;

bool judge(int n){

for (int i = 1; i < n; i++) // ⽐较 任意两个皇后的位置 {

for (int j = i + 1; j <= n; j++)

if (i - j == queen[i] - queen[j] || j - i == queen[i] - queen[j]) return false; }

return true;}

void show(){

printf(\"第%d种情况：\\n\", ++cnt); for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) if (j == queen[i]) printf(\"Q \"); else

printf(\". \"); puts(\"\"); }puts(\"\");}

void DFS(int k) // 循环⾏{

if (!judge(k-1)) { // 剪枝 return; }

if (k > n) { show(); return; }

for (int i = 1; i <= n; i++) // 循环列 {

if (vis[i] > 0) continue;

vis[i] = 1; queen[k] = i; DFS(k + 1);

vis[i] = queen[k] = 0; }}

int main(void){

while (scanf(\"%d\", &n) != EOF) {

cnt = 0; DFS(1); }

return 0;}

View Code栈：

#define _CRT_SECURE_NO_WARNINGS#include#include#define N 66int n, cnt;

int queen[N], vis[N];typedef struct Position{

int row; // 标记循环到第⼏⾏ int col; // 标记循环到第⼏列

}pi;

typedef Position any; // 可修改数据类型typedef struct SqStack // 顺序栈{

#define MaxSize 666 any a[MaxSize];

int pt; // 栈顶指针 SqStack() { pt = -1; }

void push(any e) { // ⼊栈 a[++pt] = e; }

void pop() { // 出栈 pt--; }

any top() { // 取栈顶元素 return a[pt]; }

bool empty() { // 判断栈是否为空 return pt == -1; }

int size() { // 返回栈的⼤⼩ return pt + 1; }}st;

bool judge(int n){

for (int i = 1; i < n; i++) // ⽐较 任意两个皇后的位置 {

for (int j = i + 1; j <= n; j++)

if (i - j == queen[i] - queen[j] || j - i == queen[i] - queen[j]) return false; }

return true;}

void show(){

printf(\"第%d种情况：\\n\", ++cnt); for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) if (j == queen[i]) printf(\"Q \"); else

printf(\". \"); puts(\"\"); }puts(\"\");}

void DFS(){

st s;

s.push({1, 1}); // 起始于第⼀⾏第⼀列 while (!s.empty()) {

// 1，取栈顶元素，相当于函数形参 pi vertex = s.top(); // 取上⼀次搜索的元素 s.pop(); pi last = {}; if (!s.empty()) last = s.top(); s.push(vertex);

// 2，剪枝，，回溯（关键点：消除搜索的痕迹）

if (s.size() > 1 && !judge(last.row)) // 已经确定了⼤于⼀个皇后的位置再检查 {

s.pop();

vis[last.col - 1] = 0; queen[last.row] = 0; continue; }

// 3，搜索完毕，回溯（关键点：消除搜索的痕迹） if (vertex.row > n) // 判断是否符合⼋皇后的条件 {

show();

s.pop();

vis[last.col - 1] = 0;

queen[last.row] = 0; continue; }

// 4，如果有路可⾛，就继续搜索 int find = 0;

for (int i = vertex.col; i <= n; i++) // col 初始化为 1 {

pi next = { vertex.row + 1, 1 }; if (vis[i] == 1) continue;

find = 1; s.pop();

s.push({ vertex.row, i + 1 }); // 标记这个⾏ 已经⾛过的列数，⼿动确定回溯时不会重复回溯。

vis[i] = 1;

queen[vertex.row] = i; s.push(next); // 继续搜索 break; }

// 5，⾛到死胡同，回溯（关键点：消除搜索的痕迹） if (s.size() > 1&&!find) {

s.pop();

vis[last.col - 1] = 0; queen[last.row] = 0; continue; } } }

int main(void){

while (scanf(\"%d\", &n) != EOF) {

cnt = 0; DFS(); }

system(\"pause\"); return 0;}

View Code

3，总结

　　问题 ①：

　　　　栈⾥要存放的元素如何确定？　　解决办法：

　　　　栈⾥存放的元素应是递归函数的形参，以便在搜索与回溯时能提取上⼀栈帧的信息。

　　问题 ②：

　　　　递归函数可以返回上⼀栈帧，利⽤当前栈帧独有的信息从⽽控制在回溯后不会发⽣重复搜索；　　　　但栈在使⽤出⼊栈模拟回溯时，却⽆法利⽤上⼀栈帧独有的信息，如何解决？　　解决办法：

　　　　将某⼀栈帧⾥控制回溯后不会发⽣重复搜索的变量保存在栈⾥。

　　　　如在迷宫寻路中，对于每⼀个⽅块结构体元素。我们增加⼀个变量 di 进⾏标记：　　　　　　di 取值 0，1，2，3，分别代表上，左，下，右。　　　　　　表⽰该位置的⽅块此时应该向哪个⽅向搜索。

　　　　　　⽽ 0123 的顺序限定了⽅块的搜索⽅向顺序，di 从 0 开始，每次加 1，到 di > 3 就代表遍历结束。　　　　这样⼦，在回溯时就不会⾛上次⾛过的路了。

　　问题 ③：

　　　　为什么每次⼊栈时也只能⼊栈⼀个元素？　　因为：

　　　　由于回溯时需要⽤到该路径上的所有元素，所以搜索时为了信息的完整，需要控制元素不能出栈，只有回溯时元素才能出栈。

　　　　⼜因为元素不能出栈，所以每次⼊栈时也只能⼊栈⼀个元素，不然就会错乱不同路径的元素。（就像递归函数⼀样，每次只调⽤⼀次⾃⾝）

　　问题 ④：

　　　　为什么⼋皇后中，需要取出栈顶下⾯的第⼆个元素？　　因为：

　　　　在迷宫寻路中，我们需要要标记的是下⼀个要搜索的元素，所以可以在下⼀栈帧要搜索的元素，就是标记过的元素；　　　　⽽在⼋皇后中，我们需要标记的是当前栈帧的元素，所以在下⼀栈帧中要搜索的元素再上⼀个元素，才是标记过的元素。

三，⼀个栈帧有多个递归函数的递归转化1，汉诺塔

#define _CRT_SECURE_NO_WARNINGS#include#include

typedef struct ElemType{

int n;

char a, b, c; bool flag;

}et;

typedef struct SqStack{

#define N 666 et data[N]; int ptop; SqStack() {

ptop = -1; }

bool push(et e) {

if (ptop + 1 == N) return false; data[++ptop] = e; return true; }

bool pop() {

if (ptop == -1) return false; ptop--; return true; }

et top() {

return data[ptop]; }

bool empty() {

return ptop == -1; }}st;

void Hanoi1(int n, char A, char B, char C){

if (n == 1)

printf(\"将第%d个盘⼦从%c移动到%c.\\n\", n, A, C); else {

Hanoi1(n - 1, A, C, B);

printf(\"将第%d个盘⼦从%c移动到%c.\\n\", n, A, C); Hanoi1(n - 1, B, A, C); }}

void Hanoi2(int n, char A, char B, char C){

if (n <= 0) return; st s;

et e = { n,A,B,C,false }; s.push(e);

while (!s.empty()) {

et vertex = s.top(); s.pop();

if (vertex.flag == false) // 注意栈是先进后出的，所以顺序要反过来 {

// 相当于 Hanoi1(n - 1, B, A, C);

et next3 = { vertex.n - 1,vertex.b,vertex.a,vertex.c,false }; if (next3.n == 1) next3.flag = true; s.push(next3);

// 相当于 move(n, A, C);

et next2 = { vertex.n,vertex.a,vertex.b,vertex.c,true }; s.push(next2);

// 相当于 Hanoi1(n - 1, A, C, B);

et next1 = { vertex.n - 1,vertex.a,vertex.c,vertex.b,false }; if (next1.n == 1) next1.flag = true; s.push(next1); } else

printf(\"将第%d个盘⼦从%c移动到%c.\\n\", vertex.n, vertex.a, vertex.c); }}

int main(void){

//printf(\"\\n⽤递归算法可得：\\n\"); //Hanoi1(4, 'A', 'B', 'C');

printf(\"⽤⾮递归算法可得汉诺塔的移动顺序为：\\n\"); Hanoi2(4, 'A', 'B', 'C');

system(\"pause\"); return 0;}

View Code转化过程：

　　注意点 ①：

　　　　在递归函数中，调⽤函数的语句即代表⼊栈成功，出栈完成的语句。所以，其出栈顺序是 Hanoi(n-1, a, c, b)，move(n, a, c)，Hanoi(n-1, b, a, c)　　　　那么，反映在⾮递归的栈⾥，其⼊栈顺序就是 Hanoi(n-1, b, a, c)，move(n, a, c)，Hanoi(n-1, a, c, b)。　　　　因为，出⼊栈的顺序是反着来的。　　注意点 ②：

　　　　因为⼊栈的既有 Hanoi，⼜有 move，所以需要另设⼀个变量区分两者，即代码中的 flag。

============================================

梦想是注定孤独的旅⾏，路上少不了质疑和嘲笑，但那⼜怎样，哪怕遍体鳞伤，也要活的漂亮