BreezyValley BreezyValley
关注数: 8 粉丝数: 4 发帖数: 308 关注贴吧数: 42
由非递归到递归:从汉诺塔谈起 2007-05-18 16:47一切源于书中的一段话: 系统栈是一块特殊的存储区。当一个函数被调用时,系统为改函数的本次调用创建一个活动记录(activation record),也称栈帧(stack frame),并将其置于栈顶。所以,系统栈的元素是栈帧。活动记录通常包含一下信息: (1)形式参数:...; (2)局部变量:...; (3)上一帧指针:指向调用函数活动记录的指针; (4)返回地址:被调函数执行完毕,返回调用函数被中断处的指令地址,即调用函数中紧随调用指令的下一条指令的地址; (5)函数返回值:...;说到递归,最著名的当属汉诺塔问题了。下面以其为例说明:void hanoi(int num, char A, char B, char C){ if(num==1) move(A,C); else { hanoi(num-1,A,C,B); move(A,C); hanoi(num-1,B,A,C); }}从提高效率的角度考虑,我们很自然的想到可以把形参改为全局变量。结果如下:int num;char A,B,C;void hanoi(){ if(num==1) move(A,C); else { num--; swap(B,C); hanoi(); swap(B,C); num++; move(A,C); num--; swap(A,B); hanoi(); swap(A,B); num++; }} 没有参数的递归调用,这确实让人感觉有点奇怪!但也给人以希望。那么,我们能不能用某种方式,把hanoi()调用消去呢? 由于函数原本就没有返回值、局部变量,上面又消去了形参,很自然的我们就会想,能不能把“(3)上一帧指针”和“(4)返回地址”也给消去呢?如果能的话,我们的函数不就变成了非递归的了吗?! 经过思考,我用数组flag[]来存储表示(4),用n来存储表示(3);程序如下。int num;int flag[100]=0;int n=0;char A,B,C;void hanoi(){ head: if(num==1) move(A,C); else { num--; swap(B,C); flag[++n]=1; goto head; loop1: swap(B,C); num++; move(A,C); num--; swap(A,B); flag[++n]=2; goto head; loop2: swap(A,B); num++; } if(flag[n]==1) {n--; goto loop1;} /* 返回上一次调用处;由 */ /* flag[]的值知道上一次的返回地址 */ if(flag[n]==2) {n--; goto loop2;} return; /* 当flag[]不为1、2(即为0时),返回主函数 */}到此,函数已经没有递归调用了。如果你喜欢,可以把全局变量变成局部变量和形式参数。经过修改、优化,完整的程序如下:#include"stdio.h"#define swap(x,y) {x+=y; y=x-y; x-=y;}void move(char A,char B){ printf("\n%c->%c",A,B);}void hanoi(int num){ int flag[100]={0}; int n=0; char A='a',B='b',C='c'; head: if(num==1) move(A,C); else { num--; swap(B,C); flag[++n]=1; goto head; loop1: swap(B,C); move(A,C); swap(A,B); flag[++n]=2; goto head; loop2: swap(A,B); num++; } switch(flag[n--]) { case 1: goto loop1; case 2: goto loop2; default:return; }}void main(){puts("\n");hanoi(3);}举一反三,依此类推,把任何递归函数改为非递归的,都不是什么难事的了。下面再举一例,计算阶乘:n!递归算法:int jc(int num){ if(num==1) return 1; return num*jc(num-1);}非递归算法:int jc(int num){ int n=0; int temp; int retv[1000]; /* 保存返回值的数组,由于(4)返回地址只有一 */ /* 个,所以不需要用数组存储 */ head: if(num==1) retv[n]=1; else { num--; n++; goto head; loop: temp=retv[n]; n--; num++; retv[n]=num*temp; } if(n) goto loop; return retv[n];}
1 下一页