数据结构C语言描述(耿国华)第3章.ppt

5)递归过程的实现递归进层（i→i+1层）系统需要做三件事：(1)保留本层参数与返回地址（将所有的实在参数、返回地址等信息传递给被调用函数保存）；(2)给下层参数赋值（为被调用函数的局部变量分配存储区）；(3)将程序转移到被调函数的入口。而从被调用函数返回调用函数之前，递归退层（i←i+1层）系统也应完成三件工作：(1)保存被调函数的计算结果；(2)恢复上层参数（释放被调函数的数据区）；(3)依照被调函数保存的返回地址，将控制转移回调用函数。2.递归算法到非递归算法转换递归算法具有两个特性：(1)递归算法是一种分而治之、把复杂问题分解为简单问题的求解问题方法，对求解某些复杂问题，递归算法的分析方法是有效的。（2）递归算法的时间效率低。1)消除递归的原因其一：有利于提高算法时空性能，因为递归执行时需要系统提供隐式栈实现递归，效率低且费时。其二：无应用递归语句的语言设施环境条件，有些计算机语言不支持递归功能，如FORTRAN、C语言中无递归机制。其三：递归算法是一次执行完，这在处理有些问题时不合适，也存在一个把递归算法转化为非递归算法的需求。2)简单递归（尾递归和单向递归）消除在简单情况下，将递归算法可简化为线性序列执行，可直接转换为循环实现。例：n=最小尺度(由自然数1直接定义)n1其递归算法如下，intf(intn)/*设n0*/{ifn=0thenreturn(1)elsereturn(n*f(n-1))；}图3.9递归调用变化情况示意递归进层三件事：保存本层参数、返回地址;; 传递参数，分配局部数据空间; 控制转移。递归退层三件事：恢复上层； 传递结果； 转断点执行。图3.10f(3)递归调用流程变化示意由图3.11可看出，整个计算包括自上而下递归调用进层和自下而上递归返回退层两个阶段，所有递归调用直接或间接依赖f(0)，所以整个阶段分两步，计算顺序在第二阶段，先计算f(0)→f(1)→…→f(n),工作变量y记录中间结果。例：斐波那契数列斐波那契数列的递归算法Fib(n)如下，Fib(intn){if（n==0||n==1）returnn;/*递归出口*/elsereturnFib(n-1)+Fib(n-2);/*递归调用*/}图3.11Fib(5)递归调用过程示意3-12Fib(5)循环调用过程示意图(1)进栈操作。intPush(LinkStacktop,StackElementTypex)/*将数据元素x压入栈top中*/{LinkStackNode*temp;temp=(LinkStackNode*)malloc(sizeof(LinkStackNode));if(temp==NULL)return(FALSE);/*申请空间失败*/temp-data=x;temp-next=top-next;top-next=temp;/*修改当前栈顶指针*/return(TRUE);}(2)出栈操作。intPop(LinkStacktop,StackElementType*x){/*将栈top的栈顶元素弹出，放到x所指的存储空间中*/LinkStackNode*temp;temp=top-next;if(temp==NULL)/*栈为空*/return(FALSE);top-next=temp-next;*x=temp-data;free(temp);/*释放存储空间*/return(TRUE);}3.1.3栈的应用举例1.数制转换假设要将十进制数N转换为d进