如何把下面的程序改为基于递归

求助怎么把下面的程序改为基于递归
本帖最后由 a747050097 于 2013-06-12 13:34:59 编辑

#include <stdio.h>
#define MAX_ROW 5
#define MAX_COL 5
struct point { int row, col; } stack[512];
int top = 0;
void push(struct point p)
{
        stack[top] = p;
        top++;
}
struct point pop(void)
{
        top--;
        return stack[top];
}
int is_empty(void)
{
        return top == 0;
}
int maze[MAX_ROW][MAX_COL] = {
        {0, 1, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 1, 0}
};
void print_maze(void)
{
        int i, j;
        for (i = 0; i < MAX_ROW; i++) {
                for (j = 0; j < MAX_COL; j++)
                        printf("%d ", maze[i][j]);
                putchar('\n');
        }
        printf("*********\n");
}
struct point predecessor[MAX_ROW][MAX_COL] = {
        {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
        {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
        {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
        {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
        {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}
};
void visit(int row, int col, struct point pre)
{
        struct point visit_point = { row, col };
        maze[row][col] = 2;
        predecessor[row][col] = pre;
        push(visit_point);
}
int main(void)
{
        struct point p = { 0, 0 };
        maze[p.row][p.col] = 2;
        push(p);        
        
        while (!is_empty()) {
                p = pop();
                if (p.row == MAX_ROW - 1  /* goal */ 
 
                    && p.col == MAX_COL - 1)
                        break;
                if (p.col+1 < MAX_COL     /* right */
                    && maze[p.row][p.col+1] == 0)
                        visit(p.row, p.col+1, p);
                if (p.row+1 < MAX_ROW     /* down */
                    && maze[p.row+1][p.col] == 0)
                        visit(p.row+1, p.col, p);
                if (p.col-1 >= 0          /* left */
                    && maze[p.row][p.col-1] == 0)
                        visit(p.row, p.col-1, p);
                if (p.row-1 >= 0          /* up */
                    && maze[p.row-1][p.col] == 0)
                        visit(p.row-1, p.col, p);
                print_maze();
        }
          if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) {
                printf("(%d, %d)\n", p.row, p.col);
                while (predecessor[p.row][p.col].row != -1) {
                        p = predecessor[p.row][p.col];
                        printf("(%d, %d)\n", p.row, p.col);
                }
        } 
        else
                printf("No path!\n");
        return 0; 
 
}

以上代码是Linux+C编程一站式学习的代码，求高手帮帮忙。 C 栈
[解决办法]
大致思路如下：

bool findWay(int row, int col)
{
    maze[row][col] = 2;
    if (row == MAX_ROW - 1 && col == MAX_COL - 1)
        return true;
    if (col + 1 < MAX_COL && 0 == maze[row][col + 1] && findWay(row, col + 1))
        return true;
    if (row + 1 < MAX_ROW && 0 == maze[row + 1][col] && findWay(row + 1, col))
        return true;
    if (col - 1 >= 0 && 0 == maze[row][col - 1] && findWay(row, col - 1))
        return true;
    if (row - 1 >= 0 && 0 == maze[row - 1][col] && findWay(row - 1, col))
        return true;

    maze[row][col] = 0;
    return false;
}

[解决办法]
“给定一个小点的输入，完整单步跟踪(同时按Alt+7键查看Call Stack里面从上到下列出的对应从里层到外层的函数调用历史)一遍。”是理解递归函数工作原理的不二法门！
递归函数关注以下几个因素
·退出条件
·参数有哪些
·返回值是什么
·局部变量有哪些
·全局变量有哪些
·何时输出
·会不会导致堆栈溢出

[解决办法]
把main函数替换成：

struct point search_path(struct point p)
{
if(is_empty()) return p;
p = pop();
if (p.row == MAX_ROW - 1  /* goal */
&& p.col == MAX_COL - 1)
return p;
if (p.col+1 < MAX_COL     /* right */
&& maze[p.row][p.col+1] == 0)
visit(p.row, p.col+1, p);
if (p.row+1 < MAX_ROW     /* down */
&& maze[p.row+1][p.col] == 0)
visit(p.row+1, p.col, p);
if (p.col-1 >= 0          /* left */
&& maze[p.row][p.col-1] == 0)
visit(p.row, p.col-1, p);
if (p.row-1 >= 0          /* up */
&& maze[p.row-1][p.col] == 0)
visit(p.row-1, p.col, p);
print_maze();

return search_path(p);
}

int main(void)
{
struct point p = { 0, 0 };
maze[p.row][p.col] = 2; 
 
push(p);        
p=search_path(p);

if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) {
printf("(%d, %d)\n", p.row, p.col);
while (predecessor[p.row][p.col].row != -1) {
p = predecessor[p.row][p.col];
printf("(%d, %d)\n", p.row, p.col);
}
} 
else
printf("No path!\n");

return 0;
}

查看更多 下一篇