数据结构与程序设计(王丽苹)11-递归.ppt

《数据结构与程序设计(王丽苹)11-递归.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计(王丽苹)11-递归.ppt（40页珍藏版）》请在三一办公上搜索。

1、5/27/2023,数据结构与程序设计,1,数据结构与程序设计(11),王丽苹,5/27/2023,数据结构与程序设计,2,第五章 递归,What is recursion?The method in which a problem is solved by reducing it to smaller cases of the same problem.,5/27/2023,数据结构与程序设计,3,Stack frames for subprograms,P158 Figure 5.1,5/27/2023,数据结构与程序设计,4,Tree of subprogram calls,P159 F

2、igure 5.2,5/27/2023,数据结构与程序设计,5,Tree-Diagram Definitions,The circles in a tree diagram are called vertices or nodes.(节点)The top of the tree is called its root.（根）The vertices immediately below a given vertex are called the children of that vertex.（孩子）The(unique)vertex immediately above a given verte

3、x is called its parent.(The root is the only vertex in the tree that has no parent.)（父亲）,5/27/2023,数据结构与程序设计,6,Tree-Diagram Definitions,A vertex with no children is called a leaf or an external vertex.（叶子）The line connecting a vertex with one immediately above or below is called a branch.（分支）Sibling

4、s are vertices with the same parent.（兄弟）,5/27/2023,数据结构与程序设计,7,Tree-Diagram Definitions,Two branches of a tree are adjacent if the lower vertex of the first branch is the upper vertex of the second.A sequence of branches in which each is adjacent to its successor is called a path.The height of a tre

5、e is the number of vertices on a longest possible path from the root to a leaf.(Hence a tree containing only one vertex has height 1.)The depth or level of a vertex is the number of branches on a path from the root to the vertex.,5/27/2023,数据结构与程序设计,8,Two parts of recursion,A recursive definition ha

6、s two parts:the base case-a stopping conditionthe recursive step-an expression of the computation or definition in terms of itself,5/27/2023,数据结构与程序设计,9,General format forMany Recursive Functions,if(some easily-solved condition)/base case solution statement else/general case recursive function call,

7、5/27/2023,数据结构与程序设计,10,递归的使用,在以下三种情况下，常常用到递归方法。定义是递归的 数据结构是递归的 问题的解法是递归的,5/27/2023,数据结构与程序设计,11,定义是递归的,P161目录Factorial下例程The value of Factorial(n)can be written as n*the product of the numbers from(n-1)to 1,that is,n*(n-1)*.*1 or,n*Factorial(n-1)And notice that the recursive call Factorial(n-1)gets

8、us“closer”to the base case of Factorial(0).,5/27/2023,数据结构与程序设计,12,A recursive definition,int factorial(int n)/*Pre:The parameter n is a nonnegative integer.Post:The function returns the nth Fibonacci number.*/if(n=0)return 1;else return n*factorial(n-1);,5/27/2023,数据结构与程序设计,13,A recursive definitio

9、n,void main()int n=0;coutn;coutn!is:factorial(n)endl;,5/27/2023,数据结构与程序设计,14,求解阶乘 4!的过程,5/27/2023,数据结构与程序设计,15,斐波那契数列 P178,5/27/2023,数据结构与程序设计,16,斐波那契数列,int fibonacci(int n)/*fibonacci:recursive versionPre:The parameter n is a nonnegative integer.Post:The function returns the nth Fibonacci number.*/

10、if(n=0)return 0;else if(n=1)return 1;else return fibonacci(n-1)+fibonacci(n-2);,5/27/2023,数据结构与程序设计,17,斐波那契数列的递归调用树,5/27/2023,数据结构与程序设计,18,斐波那契数列,目录Fibonacci下例程,5/27/2023,数据结构与程序设计,19,数据结构是递归的,搜索链表最后一个结点并打印其数值template void Find(ListNode*f)if(f link=NULL)cout f data endl;else Find(f link);,例如，单链表结构,5

11、/27/2023,数据结构与程序设计,20,在链表中寻找等于给定值的结点并打印其数值template void Print(ListNode*f)if(f!=NULL)if(f data=x)cout fdata endl;else Print(flink);,5/27/2023,数据结构与程序设计,21,问题的解法是递归的 例如，汉诺塔(Tower of Hanoi)问题,5/27/2023,数据结构与程序设计,22,汉诺塔,void move(int count,int start,int finish,int temp)if(count 0)move(count-1,start,temp

12、,finish);cout Move disk count from start to finish.endl;move(count-1,temp,finish,start);,5/27/2023,数据结构与程序设计,23,汉诺塔,目录Hanoi下例程,5/27/2023,数据结构与程序设计,24,Program Tracing,P166-168给出figure 5.5的输出About time,5/27/2023,数据结构与程序设计,25,课后作业,P169E1E2,5/27/2023,数据结构与程序设计,26,Designing Recursive Algorithms,Find a st

13、opping rule.This stopping rule is usually the small,special case that is trivial or easy to handle without recursion.Outline your algorithm.Combine the stopping rule and the key step,using an if statement to select between them.,5/27/2023,数据结构与程序设计,27,Designing Recursive Algorithms,Check termination

14、.Verify that the recursion will always terminate.Be sure that your algorithm correctly handles extreme cases.Draw a recursion tree.The height of the tree is closely related to the amount of memory that the program will require,and the total size of the tree reflects the number of times the key step

15、will be done.P174 Figure 5.7,5/27/2023,数据结构与程序设计,28,Tail recursion,DEFINITION Tail recursion occurs when the last-executed statement of a function is a recursive call to itself.,5/27/2023,数据结构与程序设计,29,Tail recursion,If the last-executed statement of a function is a recursive call to the function its

16、elf,then this call can be eliminated by reassigning the calling parameters to the values specified in the recursive call,and then repeating the whole function.,5/27/2023,数据结构与程序设计,30,Tail recursion,5/27/2023,数据结构与程序设计,31,Hanoi Without Tail Recursion,void move2(int count,int start,int finish,int temp

17、)int swap;while(count 0)move2(count-1,start,temp,finish);cout Move disk count from start to finish.endl;count-;swap=start;start=temp;temp=swap;,5/27/2023,数据结构与程序设计,32,问题的解法是递归的 例如，汉诺塔(Tower of Hanoi)问题,5/27/2023,数据结构与程序设计,33,Hanoi Without Tail Recursion,思考题：void move2(int count,int start,int finish,

18、int temp);void move(int count,int start,int finish,int temp)if(count 0)move(count-1,start,temp,finish);cout 0)move(count-1,start,temp,finish);cout Move disk count from start to finish.endl;count-;swap=start;start=temp;temp=swap;,5/27/2023,数据结构与程序设计,34,Hanoi Without Tail Recursion,目录Hanoi2下例程,5/27/20

19、23,数据结构与程序设计,35,Iterative,By reading the recursion tree from bottom to top instead of top to bottom,we immediately obtain the iterative program from the recursive one.,5/27/2023,数据结构与程序设计,36,Factorial Without Tail Recursion,int factorial(int n)int count,product=1;for(count=1;count=n;count+)product*=

20、count;return product;,5/27/2023,数据结构与程序设计,37,Factorial Without Tail Recursion,目录Factorial2下例程,5/27/2023,数据结构与程序设计,38,Fibonacci Without Tail Recursion,int fibonacci(int n)/*fibonacci:iterative versionPre:The parametern is a nonnegative integer.Post:The function returns then th Fibonacci number.*/int

21、last_but_one;/second previous Fibonacci number,Fi-2 int last_value;/previous Fibonacci number,Fi-1 int current;/current Fibonacci numberFi if(n=0)return 0;else if(n=1)return 1;else last_but_one=0;last_value=1;for(int i=2;i=n;i+)current=last_but_one+last_value;last_but_one=last_value;last_value=curre

22、nt;return current;,5/27/2023,数据结构与程序设计,39,Fibonacci Without Tail Recursion,目录Fibonacci2下例程,5/27/2023,数据结构与程序设计,40,Recursion(递归)or Iteration（循环）?,recursion occurs when a function calls itself(directly or indirectly)some functions can be written more easily using recursion Recursion can be replaced by iteration and stacks.It is also right in reverse.Iteration is more efficient than recursion.(循环程序在执行速度和空间占用上优于递归),