回复：C语言递归调用转化为栈处理的一般式, 申请精华.

mark

何时才能看懂啊

编辑器好漂亮，请问是哪个。。

马克

留名

马

.......
被吞了... 我艹.
难道是因为我一年多没填坑的原因吗?......
这帖子坑了这么久, ... 实在是 LZ 越来越懒, 俗务缠身...
终于还是决定把这个坑马马虎虎填了吧...
-------------------
就不再说别的了, 直接上例子... 看了这个例子, 就会明白的, 其实就是简单的模拟...
用汉诺塔来说明吧...
#include <stdio.h>
void hanoi(char from, char pass, char to, int n)
{
____if (n == 1) {
________printf("%c ==> %c\n", from, to);
____} else {
________hanoi(from, to, pass, n - 1);
________hanoi(from, pass, to, 1);
________hanoi(pass, from, to, n - 1);
____}
}
int main(void)
{
____int n;
____printf("pls input n: ");
____scanf("%d", &n);
____hanoi('A', 'B', 'C', n);
____return 0;
}
这个树形递归的调用栈帧/活动记录状态如下所示:
3 A B C 表示 n = 3, from = A, pass = B, to = C,
然后, 该函数递归调用自己, 调用时传递参数, 所以第一个被调用的函数其
局部变量的值为 n = 2, from = A, pass = C, to = B,
...
______________________n, from, pass, to
__________________________3 A B C
______________________/______|______\
____________2 A C B________1 A B C ________2 B A C
___________/___|___\________A==>C_________/___|___\
__________/____|____\____________________/____|____\
____1 A B C__1 A C B__1 C A B______1 B C A__1 B A C__1 A B C
_____A==>C___A==>B___C==>B___________B==>A___B==>C____A==>C
关于这个递归函数的执行路径, 和fibonacci递归是类似的,
请参照前面的 fibonacci递归的图...

看一下这个递归.
整个函数里面的局部变量只有 4 个, 就是 from, pass, to, n.
因此我们可以使用一个结构体来记录这四个变量值:
struct data_t {
____char from;
____char pass;
____char to;
____int n;
};
void hanoi(char from, char pass, char to, int n)
{
____if (n == 1) {
________printf("%c ==> %c\n", from, to);
____} else {
________// 这里调用函数, 意味着:
________// 1. 当前函数的状态(所有局部变量的值)需要保存, 以便从被调用函数返回后,
________// 当前函数的状态(所有局部变量的值)恢复到调用前的状态.
________// 2. 给被调用的函数传递参数, 然后转去被调用函数方执行.
________// 3. 当被调用函数返回, 由于我们在这里调用, 所以返回后从标签 ret_addr1: 处
________// 继续执行剩下的代码.
________hanoi(from, to, pass, n - 1);
// ret_addr1:
________// 同理, 只是被调用函数返回后, 从 ret_addr2: 处继续执行.
________hanoi(from, pass, to, 1);
// ret_addr2:
________// 同理, 被调用函数返回后, 从 ret_addr3: 处继续执行.
________hanoi(pass, from, to, n - 1);
// ret_addr3:
____}
// 这里实际上有个隐式的 return;
}
嗯, 当调用函数时, 我们将调用时调用方的状态全部记录下来, 另外, 我们也记录下"返回地址", 以便从被调用方返回后, 知道返回到调用方的哪个 point / addr 继续执行.
因此, 我们设计如下的数据结构:
typedef enum {
____RET_ADDR1,
____RET_ADDR2,
____RET_ADDR3
} ret_addr;
struct data_t {
____char from; // 保存调用方的 from
____char pass; // .............pass
____char to; // ...............to
____int n; // .................n
____ret_addr addr; // 保存调用方的 "返回地址"
};
okay, 准备工作完成, 接下来我们应该怎么做呢?

竟然最后能看到这篇帖子快要结贴又没有结贴的样子。不过这个坑确实挖了好久了。

下面是完整的模拟代码. 是完全的最笨的那种模拟. 任何递归都可以用这种模拟的办法
来完成转换. 当然, 在这种基本模拟的方式上, 有更好的做法, 就可以采用更聪明的办法.
//--------------------------------------------
#include <stdio.h>
#include <stack.h> // 自己实现一个吧...
// "返回地址"
typedef enum {
____RET_ADDR1,
____RET_ADDR2,
____RET_ADDR3
} ret_addr;
// 用来保存调用方的函数所有状态
struct data_t {
____char from;
____char pass;
____char to;
____int n;
____ret_ddr addr;
};
void set_data(struct data_t *data, char from, char pass, char to, int n, int addr)
{
____data->from = from, data->pass = pass, data->to = to, data->n = n,
____data->addr = addr;
}
void hanoi(char from, char pass, char to, int n)
{
____// 创建一个栈, 每个栈上元素的大小为 sizeof(struct data_t)
____stack_t *st = stack_create(sizeof(struct data_t), NULL);
____struct data_t data;
____char tmp;
// start 就是函数的开始咯.
start:
____if (n == 1) {
________printf("%c ==> %c\n", from, to);
____} else {
________// 保存当前函数的状态(包括所有局部变量, 以及"返回地址")
________set_data(&data, from, pass, to, n, RET_ADDR1);
________stack_push(st, &data);
________// 然后给函数传递参数, 并"调用函数"
________// 这几个赋值就相当于传递参数, goto start 就是"调用函数"
________// ret_addr1 标签就是调用函数完了之后的"返回地址"
________// from = from;
________tmp = pass, pass = to, to = tmp, n = n - 1;
________goto start;
ret_addr1:
________// 同上...
________set_data(&data, from, pass, to, n, RET_ADDR2);
________stack_push(st, &data);
________// from = from, pass = pass, to = to;
________n = 1;
________goto start;
ret_addr2:
________// 同上...
________set_data(&data, from, pass, to, n, RET_ADDR3);
________stack_push(st, &data);
________// to = to;
________tmp = from, from = pass, pass = tmp, n = n - 1;
________goto start;
ret_addr3:
________; // 这里有个分号, C语言不允许标签后面没有语句, 所以用个空语句占位.
____}
// 这里就是原来的递归函数的 return 的地方. return 的时候就回到调用方咯
// 如果栈空了, goto exit 即退出.
____if (stack_isempty(st))
________goto exit;
// 弹栈, 弹出调用方的数据(就是说这里是被调用方执行完了, 要返回到调用方继续)
____stack_pop(st, &data);
// 恢复调用方的数据
____from = data.from, pass = data.pass, to = data.to, n = data.n;
// 调用方在哪里调的, 就返回到那个调用处的下面.
____switch (data.addr)
____{
________case RET_ADDR1:
____________goto ret_addr1;
________case RET_ADDR2:
____________goto ret_addr2;
________case RET_ADDR3:
____________goto ret_addr3;
____}
exit:
____// 销毁手工栈.
____stack_destroy(st);
}
int main(void)
{
____int n;
____printf("pls input n: ");
____scanf("%d", &n);
____hanoi('A', 'B', 'C', n);
____return 0;
}
好了. 以上的代码就是模拟的实例... 看懂这个, 别的递归灵活处理即可.

自以为是的样子，知识结构写的真渣，没教材写的好，差评