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

5/5/2021 数 据 结 构 与 程 序 设 计 1 数 据 结 构 与 程 序 设 计 (11) 王 丽 苹 5/5/2021 数 据 结 构 与 程 序 设 计 2 第 五 章 递 归n What is recursion?n The method in which a problem is solved by reducing it to smaller cases of the same problem. 5/5/2021 数 据 结 构 与 程 序 设 计 3 Stack frames for subprogramsn P158 Figure 5.1 5/5/2021 数 据 结 构 与 程 序 设 计 4 Tree of subprogram callsn P159 Figure 5.2 5/5/2021 数 据 结 构 与 程 序 设 计 5 Tree-Diagram Definitionsn The circles in a tree diagram are called vertices or nodes.(节 点 )n The top of the tree is called its root.（ 根 ）n The vertices immediately below a given vertex are called the children of that vertex.（ 孩 子 ）n The (unique) vertex immediately above a given vertex is called its parent. (The root is the only vertex in the tree that has no parent.)（ 父 亲 ） 5/5/2021 数 据 结 构 与 程 序 设 计 6 Tree-Diagram Definitionsn A vertex with no children is called a leaf or an external vertex.（ 叶 子 ）n The line connecting a vertex with one immediately above or below is called a branch.（ 分 支 ）n Siblings are vertices with the same parent.（ 兄 弟 ） 5/5/2021 数 据 结 构 与 程 序 设 计 7 Tree-Diagram Definitionsn 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.n The 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.) n The depth or level of a vertex is the number of branches on a path from the root to the vertex. 5/5/2021 数 据 结 构 与 程 序 设 计 8 Two parts of recursionA recursive definition has two parts:n the base case - a stopping conditionn the recursive step - an expression of the computation or definition in terms of itself 5/5/2021 数 据 结 构 与 程 序 设 计 9 General format forMany Recursive Functions if (some easily-solved condition) / base case solution statement else / general case recursive function call 5/5/2021 数 据 结 构 与 程 序 设 计 10 5/5/2021 数 据 结 构 与 程 序 设 计 11 n P161n 目 录 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). 5/5/2021 数 据 结 构 与 程 序 设 计 12 A recursive definitionn int factorial(int n)n /* n Pre: The parameter n is a nonnegative integer.n Post: The function returns the nth Fibonacci number.n */n n if (n = 0) n return 1;n else n return n*factorial(n-1);n 5/5/2021 数 据 结 构 与 程 序 设 计 13 A recursive definitionn void main()n int n=0;n coutendlPlease input an integer:n;n coutn! is: factorial(n)endl;n 5/5/2021 数 据 结 构 与 程 序 设 计 14 求解阶乘 4! 的过程 5/5/2021 数 据 结 构 与 程 序 设 计 15 斐波那契数列 P178 1),2()1( 0,1,)( nnFibnFib nnnFib 5/5/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); 5/5/2021 数 据 结 构 与 程 序 设 计 17斐波那契数列的递归调用树 5/5/2021 数 据 结 构 与 程 序 设 计 18 斐 波 那 契 数 列n 目 录 Fibonacci下 例 程 5/5/2021 数 据 结 构 与 程 序 设 计 19搜索链表最后一个结点并打印其数值template void Find ( ListNode *f ) if ( f link = NULL ) cout f data endl; else Find ( f link ); 5/5/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) n move2(count - 1, start, temp, finish); n cout Move disk count from startn to finish . 0) n move(count - 1, start, temp, finish);n cout Move disk count from start n to finish . 0) n move(count - 1, start, temp, finish); n cout Move disk count from startn to finish . endl;n count-; n swap = start;n start = temp;n temp = swap;n n 5/5/2021 数 据 结 构 与 程 序 设 计 34 Hanoi Without Tail Recursionn 目 录 Hanoi2下 例 程 5/5/2021 数 据 结 构 与 程 序 设 计 35 Iterativen 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/5/2021 数 据 结 构 与 程 序 设 计 36 Factorial Without Tail Recursionn int factorial(int n)n n int count, product = 1;n for (count = 1; count = n; count+)n product *= count;n return product;n 5/5/2021 数 据 结 构 与 程 序 设 计 37 Factorial Without Tail Recursion 目 录 Factorial2下 例 程 5/5/2021 数 据 结 构 与 程 序 设 计 38 Fibonacci Without Tail Recursionn int fibonacci(int n)n /* fibonacci : iterative versionn Pre: The parametern is a nonnegative integer.n Post: The function returns then th Fibonacci number. */n n int last_but_one; / second previous Fibonacci number,Fi-2n int last_value; / previous Fibonacci number,Fi-1 n 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 n 5/5/2021 数 据 结 构 与 程 序 设 计 39 Fibonacci Without Tail Recursionn 目 录 Fibonacci2下 例 程 5/5/2021 数 据 结 构 与 程 序 设 计 40 Recursion(递 归 ) or Iteration（ 循环 ） ?n recursion occurs when a function calls itself (directly or indirectly) n some functions can be written more easily using recursion n Recursion can be replaced by iteration and stacks. It is also right in reverse. n Iteration is more efficient than recursion.(循 环 程序 在 执 行 速 度 和 空 间 占 用 上 优 于 递 归 )