资源描述：
《递归算法工作栈的变化详解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递给被调用函数保存;b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口. 从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数.所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的. ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存就要设置多少个栈,而且最重要的一点是:控制所
2、有这些栈的栈顶指针都是相同的,否则无法实现同步. 下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行?回到上面说的树的三种遍历方式,抽象出来只有三种操作:访问当前结点,访问左子树,访问右子树.这三种操作的顺序不同,遍历方式也不同.如果我们再抽象一点,对这三种操作再进行一个概括,可以得到:a)访问当前结点:对目前的数据进行一些处理;b)访问左子树:变换当前的数据以进行下一次处理;c)访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式). 下面以先序遍历来说明: voidpreorder_rec
3、ursive(BitreeT) /*先序遍历二叉树的递归算法*/ { if(T){ visit(T); /*访问当前结点*/ preorder_recursive(T->lchild); /*访问左子树*/ preorder_recursive(T->rchild); /*访问右子树*/
4、 } } visit(T)这个操作就是对当前数据进行的处理,preorder_recursive(T->lchild)就是把当前数据变换为它的左子树,访问右子树的操作可以同样理解了. 现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:a)确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用树的"左子树"和"右子树"c)确定这个递归调用树何时返回,即确定什
5、么结点是这个递归调用树的"叶子结点".二）.三个例子 好了上面的理论知识已经足够了,下面让我们看看几个例子,结合例子加深我们对问题的认识.即使上面的理论你没有完全明白,不要气馁,对事物的认识总是曲折的,多看多想你一定可以明白(事实上我也是花了两个星期的时间才弄得比较明白得). 1)例子一: f(n)=n+１; (n<２) =f[n/2]+f[n/4](n>=2); 这个例子相对简单一些,递归程序如下: int f_recu
6、rsive(intn) {intu1,u2,f; if(n<2) f=n+1; else{ u1=f_recursive((int)(n/2)); u2=f_recursive((int)(n/4)); f=u1*u2;
7、 } returnf;} 下面按照我们上面说的,确定好递归调用树的结构,这一步是最重要的.首先,什么是叶子结点,我们看到当n<2时f=n+1,这就是返回的语句,有人问为什么不是f=u1*u2,这也是一个返回的语句呀?答案是:这条语句是在u1=exmp1((int)(n/2))和u2=exmp1((int)(n/4))之后执行的,是这两条语句的父结点.其次,什么是当前结点,由上面的分析,f=u1*u2即是父结点.然后,顺理成章的u1=exmp1((in
8、t)(n/2))和u2=exmp1((int)(n/4))就分别是左子树和右子树了.最后,我们可以看到,这个递归函数可以表
