讲义一-递归的消除

递归算法具有两个特性：(1) 递归算法是一种分而治之、把复杂问题分解为简单问题的求解问题方法，对求解某些复杂问题，递归算法分析方法是有效的。（2）递归算法的时间效率差，其时间效率低。为此，对求解某些问题时，我们希望用递归算法分析问题，用非递归算法求解具体问题；消除递归原因：其一：有利于提高算法时空性能，因为递归执行时需要系统提供隐式栈实现递归，效率低，费时。其二：无应用递归语句的语言设施环境条件，有些计算机语言不支持递归功能，如FORTRAN、C语言中无递归机制 。 其三，递归算法是一次执行完，这在处理有些问题时不合适，也存在一个把递归算法转化为非递归算法的需求。理解递归机制，是掌握递归程序技能必要前提。消除递归要基于对问题的分析，常用的有两类消除递归方法。一类是简单递归问题的转换，对于尾递归和单向递归的算法，可用循环结构的算法替代。另一类是基于栈的方式，即将递归中隐含的栈机制转化为由用户直接控制的明显的栈。利用堆栈保存参数，由于堆栈的后进先出特性吻合递归算法的执行过程，因而可以用非递归算法替代递归算法。在大量复杂的情况下，递归的问题无法直接转换成循环，需要采用工作栈消除递归。工作栈提供一种控制结构，当递归算法进层时需要将信息保留；当递归算法出层时需要从栈区退出信息。栈及其应用一.栈的特点：栈是一种线性表，对于它所有的插入和删除都限制在表的同一端进行，这一端叫做栈的“顶”，另一端则叫做栈的“底”，其操作特点是“后进先出”。二.栈的抽象数据定义：1、栈的数组表示 顺序栈s为栈、p为指向栈顶的指针Const m=max;Type Stack=array1.m of datatype;Var S:stack; p:0.m;typestack=recorddata:array1.m of datatype;p:0.mend;vars:stack;2、栈的链接表示 链式栈 bottomtype stack=struc; struc=recorddata:stype;link:stack; end;var s:stack;当栈的容量无法估计时，可采用链表结构链式栈.链式栈的栈顶在链头.无栈满问题，空间可扩充.进栈（插入）与出栈（删除）都在栈顶处执行.三.栈的基本操作：(1)进栈操作push(s,x)：往栈中推入元素x的项目；若p=m则write(overflow)否则p:=p+1;sp:=x;(2)出栈操作pop(s)：将栈顶元素中弹出；若p=0则write(underflow)否则p:=p-1;(3)读栈顶元素top(s,x)：把栈顶元素的值读到变量x中，栈保持不变；若p=0则write(error)否则x:=sp;(4)判栈是否为空sempty(s)：这是一个布尔函数，当栈sp中没有元素(即t=0)时，称它为空栈，函数取真值，否则值为假。若p=0则sempty:=true否则sempty:=false;(5)链式栈的进栈、出栈操作进栈：数据元素进栈时，先生成一个新结点P，置数据域为X、指针域指向原栈顶结点，栈顶结点指向P。（在链头插入一个新结点）出栈：先从栈顶取出数据元素至X，然后把S结点指到它的直接后继结点，原S结点清空。（在链头删去一个结点）例9、Ackermann函数问题描述已知Ackermann函数定义如下：1、手工计算Ack(3,2) 和Ack(3,6)。解答：29和5092、写出计算Ack(m，n)的递归算法程序。program ackermann1;var m,n:longint;function ack(m,n:longint):longint;begin if m=0 then ack:=n+1 else if n=0 then ack:=ack(m-1,1) else ack:=ack(m-1,ack(m,n-1)end;begin write(Input m,n:); readln(m,n); writeln(ack(m,n)end. 3、写出计算Ack(m，n)的非递归算法程序。program ackermann2;type stack=array 1.8000,1.2 of longint;var m,n,top:longint; s:stack;begin write(Input m,n:); readln(m,n); s1,1:=m; s1,2:=n; top:=1; while top0 do begin m:=stop,1; n:=stop,2; top:=top-1; if (top=0) and (m=0) then begin writeln(n+1); exit end; if m=0 then stop,2:=n+1 else if n=0 then begin top:=top+1; stop,1:=m-1; stop,2:=1 end else begin top:=top+1; stop,1:=m-1; top:=top+1; stop,1:=m; stop,2:=n-1 end endend.下面,我们就以ack(2,1)为例,开始分析递归调用树,采用一个栈记忆每次递归调用时的实参值，每个结点两个域vm, vn。对以上实例，递归树以及栈的变化如下：相应算法如下#include#includeusing namespace std;typedef struct node_t unsigned int vm, vn;node, *pnode;unsigned akm ( unsigned int m, unsigned int n ) std:stack st;pnode w, w1;unsigned int v;unsigned int vt;/根节点进栈w = (node *) malloc (sizeof (node);w-vm = m; w-vn = n; st.push (w);do /计算akm(m-1, akm(m, n-1)while ( st.top( )-vm 0 ) vt = w-vn;/计算akm(m, n-1), 直到akm(m,0) while ( st.top()-vn 0 ) w1 = (node *) malloc (sizeof (node); vt -; w1-vn = vt; w1-vm = w-vm; st.push( w1 ); /把akm(m, 0)转换为akm(m-1, 1),并计算 w = st.top( ); st.pop( ); w-vm-; w-vn = 1; st.push( w ); vt = w-vn;/计算akm( 0, akm( 1, * ) )w = st.top();st.pop( );w-vn+;/计算v = akm( 1, * )+1v = w-vn;/如果栈不为空,改栈顶为( m-1, v )if ( !st.empty( ) ) w = st.top