资源描述
11/13/2021数据结构与程序设计 1数据结构与程序设计(11) 王丽苹 11/13/2021数据结构与程序设计 2第五章 递归nWhat is recursion?nThe method in which a problem is solved by reducing it to smaller cases of the same problem.11/13/2021数据结构与程序设计 3Stack frames for subprogramsnP158 Figure 5.111/13/2021数据结构与程序设计 4Tree of subprogram callsnP159 Figure 5.211/13/2021数据结构与程序设计 5Tree-Diagram DefinitionsnThe circles in a tree diagram are called vertices or nodes.(节点)nThe top of the tree is called its root.（根）nThe vertices immediately below a given vertex are called the children of that vertex.（孩子）nThe (unique) vertex immediately above a given vertex is called its parent. (The root is the only vertex in the tree that has no parent.)（父亲）11/13/2021数据结构与程序设计 6Tree-Diagram DefinitionsnA vertex with no children is called a leaf or an external vertex.（叶子）nThe line connecting a vertex with one immediately above or below is called a branch.（分支）nSiblings are vertices with the same parent.（兄弟）11/13/2021数据结构与程序设计 7Tree-Diagram DefinitionsnTwo 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.nThe height of a tree 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.)nThe depth or level of a vertex is the number of branches on a path from the root to the vertex.11/13/2021数据结构与程序设计 8Two parts of recursionA recursive definition has two parts:nthe base case - a stopping conditionnthe recursive step - an expression of the computation or definition in terms of itself11/13/2021数据结构与程序设计 9General format forMany Recursive Functions if (some easily-solved condition) / base case solution statement else / general case recursive function call 11/13/2021数据结构与程序设计 1011/13/2021数据结构与程序设计 11nP161n目录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 us “closer” to the base case of Factorial(0). 11/13/2021数据结构与程序设计 12A recursive definitionnint factorial(int n)n/* nPre: The parameter n is a nonnegative integer.nPost: The function returns the nth Fibonacci number.n*/nn if (n = 0) n return 1;n else n return n*factorial(n-1);n11/13/2021数据结构与程序设计 13A recursive definitionnvoid main()nint n=0;ncoutendlPlease input an integer:n;ncoutn! is: factorial(n)endl;n11/13/2021数据结构与程序设计 14求解阶乘 4! 的过程11/13/2021数据结构与程序设计 15斐波那契数列斐波那契数列 P1781),2() 1(0,1,)(nnFibnFibnnnFib11/13/2021数据结构与程序设计 16斐波那契数列斐波那契数列int fibonacci(int n)/* fibonacci: recursive versionPre: The parameter n is a nonnegative integer.Post: The function returns the nth Fibonacci number.*/ if (n = 0) return 0; else if (n = 1) return 1; else return fibonacci(n - 1) + fibonacci(n - 2);11/13/2021数据结构与程序设计 17斐波那契数列的递归调用树斐波那契数列的递归调用树11/13/2021数据结构与程序设计 18斐波那契数列斐波那契数列n目录Fibonacci下例程11/13/2021数据结构与程序设计 19搜索链表最后一个结点并打印其数值搜索链表最后一个结点并打印其数值template void Find ( ListNode *f ) if ( f link = NULL ) cout f data endl; else Find ( f link );11/13/2021数据结构与程序设计 20在链表中寻找等于给定值的结点并打印其数值template void Print ( ListNode *f ) if ( f != NULL) if ( f data = x ) cout fdata 0) n move(count - 1, start, temp, finish);n cout Move disk count from startn to finish . 0) nmove2(count - 1, start, temp, finish); ncout Move disk count from startn to finish . 0) n move(count - 1, start, temp, finish);n cout Move disk count from startn to finish . 0) nmove(count - 1, start, temp, finish); ncout Move disk count from startn to finish . endl;ncount-; nswap = start;nstart = temp;ntemp = swap;nn11/13/2021数据结构与程序设计 34Hanoi Without Tail Recursionn目录Hanoi2下例程11/13/2021数据结构与程序设计 35IterativenBy reading the recursion tree from bottom to top instead of top to bottom, we immediately obtain the iterative program from the recursive one.11/13/2021数据结构与程序设计 36Factorial Without Tail Recursionnint factorial(int n)nn int count, product = 1;n for (count = 1; count = n; count+)n product *= count;n return product;n11/13/2021数据结构与程序设计 37Factorial Without Tail Recursion 目录Factorial2下例程11/13/2021数据结构与程序设计 38Fibonacci Without Tail Recursionnint fibonacci(int n)n/* fibonacci : iterative versionnPre: The parametern is a nonnegative integer.nPost: The function returns then th Fibonacci number. */nn int last_but_one; / second previous Fibonacci number,Fi-2n int last_value; / previous Fibonacci number,Fi-1n int current; / current Fibonacci numberFin if (n = 0) return 0;n else if (n = 1) return 1;n else n last_but_one = 0;n last_value = 1;n for (int i = 2; i = n; i+) n current = last_but_one + last_value;n last_but_one = last_value;n last_value = current;n n return current;n n11/13/2021数据结构与程序设计 39Fibonacci Without Tail Recursionn目录Fibonacci2下例程11/13/2021数据结构与程序设计 40Recursion(递归) or Iteration（循环）?nrecursion occurs when a function calls itself (directly or indirectly) nsome functions can be written more easily using recursion nRecursion can be replaced by iteration and stacks. It is also right in reverse.nIteration is more efficient than recursion.(循环程序在执行速度和空间占用上优于递归)
展开阅读全文