数据结构与程序设计 第五章 递归

1、11/23/2021数据结构与程序设计 1第五章 递归nWhat is recursion?nThe method in which a problem is solved by reducing it to smaller cases of the same problem.11/23/2021数据结构与程序设计 2Stack frames for subprogramsnP158 Figure 5.111/23/2021数据结构与程序设计 3Tree of subprogram callsnP159 Figure 5.211/23/2021数据结构与程序设计 4Tree-Diagram D

2、efinitionsnThe 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

3、only vertex in the tree that has no parent.)（父亲）11/23/2021数据结构与程序设计 5Tree-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.（兄弟）

4、11/23/2021数据结构与程序设计 6Tree-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

5、 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/23/2021数据结构与程序设计 7Two parts of recursionA recursive definition has two parts:nthe base case - a stopping c

6、onditionnthe recursive step - an expression of the computation or definition in terms of itself11/23/2021数据结构与程序设计 8General format forMany Recursive Functions if (some easily-solved condition) / base case solution statement else / general case recursive function call 11/23/2021数据结构与程序设计 911/23/2021数

7、据结构与程序设计 10nP161n目录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/23/2021数据结构

8、与程序设计 11A 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/23/2021数据结构与程序设计 12A recursive definitionnvoid main()nint n=0;ncoutendlPlease in

9、put an integer:n;ncoutn! is: factorial(n)endl;n11/23/2021数据结构与程序设计 13求解阶乘 4! 的过程11/23/2021数据结构与程序设计 14斐波那契数列斐波那契数列 P1781),2() 1(0,1,)(nnFibnFibnnnFib11/23/2021数据结构与程序设计 15斐波那契数列斐波那契数列int fibonacci(int n)/* fibonacci: recursive versionPre: The parameter n is a nonnegative integer.Post: The function r

10、eturns the nth Fibonacci number.*/ if (n = 0) return 0; else if (n = 1) return 1; else return fibonacci(n - 1) + fibonacci(n - 2);11/23/2021数据结构与程序设计 16斐波那契数列的递归调用树斐波那契数列的递归调用树11/23/2021数据结构与程序设计 17斐波那契数列斐波那契数列n目录Fibonacci下例程11/23/2021数据结构与程序设计 18搜索链表最后一个结点并打印其数值搜索链表最后一个结点并打印其数值template void Find (

11、ListNode *f ) if ( f link = NULL ) cout f data endl; else Find ( f link );11/23/2021数据结构与程序设计 19在链表中寻找等于给定值的结点并打印其数值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(coun

12、t - 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

13、= swap;nn11/23/2021数据结构与程序设计 33Hanoi Without Tail Recursionn目录Hanoi2下例程11/23/2021数据结构与程序设计 34IterativenBy reading the recursion tree from bottom to top instead of top to bottom, we immediately obtain the iterative program from the recursive one.11/23/2021数据结构与程序设计 35Factorial Without Tail Recursionn

14、int factorial(int n)nn int count, product = 1;n for (count = 1; count = n; count+)n product *= count;n return product;n11/23/2021数据结构与程序设计 36Factorial Without Tail Recursion 目录Factorial2下例程11/23/2021数据结构与程序设计 37Fibonacci Without Tail Recursionnint fibonacci(int n)n/* fibonacci : iterative versionnPr

15、e: 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

16、;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/23/2021数据结构与程序设计 38Fibonacci Without Tail Recursionn目录Fibonacci2下例程11/23/2021数据结构与程序设计 39Recursion(递归) or Iteration（循环）?nrecursion occurs when