ds3.3陆小马功钟浩.pptVIP

§3.3 栈与递归 递归与栈的应用 §3.3 栈与递归 1.函数调用与返回的过程 2.递归函数 3.递归的设计原则 4.递归的优点和缺点 5.消除递归 1.函数调用与返回的过程 （1）函数调用当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务： 将返回地址、所有实参等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。 1.函数调用与返回的过程 （2）函数返回从被调用函数返回调用函数之前，应该完成下列三项任务： 保存被调函数的计算结果； 释放被调函数保存局部变量的数据区； 依照被调函数保存的返回地址将控制转移到调用函数。 函数嵌套调用时，后调用的函数先返回。 int main() { int n = 10; int sn; sn = sum(n); cout sn endl; } int sum ( int n ) { int i, s = 0; for( i=1; in; i++) s += i; return s; } int main() { int n = 10; int sn; sn = sum(n); cout sn endl; } int sum ( int n ) { int i, s = 0; for( i=1; in; i++) s += i; return s; } 2. 递归函数 函数直接或间接调用自身，称为递归(Recursion)。 何时应用递归？ 问题具有递归的数学定义 使用了递归的数据结构 问题存在递归的解决方法 问题具有递归的数学定义 计算n!. long Fact ( int n ) { if ( n==0 ) return 1; else return n*Fact(n-1); } 问题具有递归的数学定义 计算Fibonacci数列：0,1,1,2,3,5,8,13,21,… long Fib ( int n ) { if ( n==1 ) return 0; if ( n==2 ) return 1; return Fib(n-1)+Fib(n-2); } 问题具有递归的数学定义 计算xn（n为整数，n≥0） double Power ( double x, int n ) { if ( n==0 ) return 1; if ( n==1 ) return x; if ( n%2==0 ) return Power(x*x, n/2); else return x*Power(x*x, n/2); } 使用了递归的数据结构 打印单链表。 void PrintLinkList ( LinkList L ) { if ( L-next != NULL ) { print (L-next-data); PrintLinkList (L-next); } } 问题存在递归的解决方法 汉诺塔问题。Hanoi (n, a, b, c)表示解决n个盘子的汉诺塔问题（从a搬到c，可以借助b）。解决方法： 若n=1，直接将盘子从a搬到c即可； 否则，可以分解为如下步骤： Hanoi ( n-1, a, c, b ) move ( n, a, c ) Hanoi ( n-1, b, a, c ) void Hanoi ( int n, char a, char b, char c ) { if ( n==1 ) move ( n, a, c ); else { Hanoi ( n-1, a, c, b ); move ( n, a, c ); Hanoi ( n-1, b, a, c ); } } 3.递归的设计原则 如果递归设计不当… 容易造成无穷递归，最终会耗尽应用程序的栈空间，导致栈溢出错误，使程序失败。 // 无穷递归的例子 // 讲不完的故事 void Story () { print ( “从前有座山，山上有个庙，庙里有个和尚在讲故事：” ); Story(); } 3.递归的设计原则 （1）基准情形 必须存在不用继续递归即可解决的情况。 （2）不断推进 对于需要递归解决的情况，每一次递归都要使得求解朝着基准情况的方向推进。 （3）设计法则 假设所有的递归调用都能运行。 （4）合成效益 解决一个问题时，切勿在不同的递归调用中做重复的工作。 一个不符合合成效益法则的例子：