Cơ sở dữ liệu - Chapter 6: Recursion

Nội dung text: Cơ sở dữ liệu - Chapter 6: Recursion

1. Chapter 6 - Recursion  Subprogram implementation  Recursion  Designing recursive algorithms  Recursion removal  Backtracking  Examples of backtracking and recursive algorithms: . Factorial . Fibonacci . The towers of Hanoi . Eight Queens Problem . Tree-structured program: Look-ahead in Game 1
2. Subprogram implementation 2
3. Subprogram implementation 3
4. Subprogram implementation 4
5. Subprogram implementation 5
6. Tree and Stack frames of function calls 6
7. Tree and Stack frames of function calls Stack frames: Each vertical column shows the contents of the stack at a given time There is no difference between two cases: o when the temporary storage areas pushed on the stack come from different functions, and o when the temporary storage areas pushed on the stack come from repeated occurrences of the same function. 7
8. Recursion 8
9. Recursion 9
10. Recursion Recursion is the name for the case when: • A function invokes itself, or • A function invokes a sequence of other functions, one of which eventually invokes the first function again.  In regard to stack frames for function calls, recursion is no different from any other function call. . Stack frames illustrate the storage requirements for recursion. . Separate copies of the variables declared in the function are created for each recursive call. 10
11. Tree and Stack frames of function calls D E F F E E E 11
12. Tree and Stack frames of function calls Recursive calls: M M M M M M M M M M M M M M M M M M M M M M M M M M M M 12
13. Recursion  In the usual implementation of recursion, there are kept on a stack.  The amount of space needed for this stack depends on the depth of recursion, not on the number of times the function is invoked.  The number of times the function is invoked (the number of nodes in recursive tree) determines the amount of running time of the program. 13
14. Recursion 14
15. Print List 6 10 14 20 15
16. Print List A list is • empty, or • consists of an element and a sublist, where sublist is a list. 16
17. Print List 6 10 14 20 17
18. Print List Algorithm Print(val head ) Prints Singly Linked List. Pre head points to the first element of the list needs to be printed. Post Elements in the list have been printed. Uses recursive function Print. 1. if (head = NULL) // stopping case 1. return 2. write (head->data) 3. Print(head->link) // recursive case End Print 18
19. Print List in Reverse 19
20. Print List in Reverse 20
21. Print List in Reverse Algorithm PrintReverse(val head ) Prints Singly Linked List in reverse. Pre head points to the first element of the list needs to be printed. Post Elements in the list have been printed in reverse. Uses recursive function PrintReverse. 1. if (head = NULL) // stopping case 1. return 2. PrintReverse(head->link) // recursive case 3. write (head->data) End PrintReverse 21
22. Factorial: A recursive Definition 22
23. Iterative Solution Algorithm IterativeFactorial (val n ) Calaculates the factorial of a number using a loop. Pre n is the number to be raised factorial, n >= 0. Post n! is returned. 1. i = 1 2. factN = 1 3. loop (i <= n) 1. factN = factN * i 2. i = i + 1 4. return factN End IterativeFactorial 23
24. Recursive Solution Algorithm RecursiveFactorial (val n ) Caculates the factorial of a number using recursion. Pre n is the number to be raised factorial, n >= 0 Post n! is returned. Uses recursive function RecursiveFactorial 1. if (n = 0) 1. factN = 1 // stopping case 2. else 1. factN = n * RecursiveFactorial(n-1) // recursive case 3. return factN End RecursiveFactorial 24
25. Recursive Solution  The recursive definition and recursive solution can be both concise and elegant.  The computational details can require keeping track of many partial computations before the process is complete. 25
26. Recursive Solution Algorithm RecursiveFactorial (val n ) Calaculates the factorial of a number using recursion. Pre n is the number to be raise factorial, n >= 0. Post n! is returned Uses recursive function RecursiveFactorial. 1. if (n = 0) 1. factN = 1 2. else 1. factN = n * RecursiveFactorial(n-1) 3. return factN End RecursiveFactorial 26
27. Recursive Solution Stack 27
28. Thinking of Recursion  Remembering partial computations: computers can easily keep track of such partial computations with a stack, but human mind can not.  It is exceedingly difficult for a person to remember a long chain of partial results and then go back through it to complete the work.  Ex.:  When we use recursion, we need to think in somewhat difference terms than with other programming methods.  Programmers must look at the big picture and leave the detailed computations to the computer. 28
29. Recursion The essence of the way recursion works: To obtain the answer to a large problem, a general method is used that reduces the large problem to one or more problems of a similar nature but a smaller size. The same general method is then used for these subproblems. Recursion continues until the size of the subproblems is reduced to some smallest, base case. Base case: the solution is given directly without using further recursion. 29
30. Recursion Every recursive process consists of two parts: 1. Some smallest base cases that are processed without recursion. 2. A general method that reduces a particular case to one or more of the smaller cases, thereby making progress toward eventually reducing the problem all the way to the base case. 30
31. Designing Recursive Algorithms 31
32. Designing Recursive Algorithms 32
33. Designing Recursive Algorithms 33
34. Fibonacci Numbers 34
35. Fibonacci Numbers 35
36. Fibonacci Numbers Algorithm Fibonacci (val n ) Calculates the nth Fibonacci number. Pre n is the ordinal of the Fibonacci number. Post returns the nth Fibonacci number Uses Recusive function Fibonacci 1. if (n = 0) OR (n = 1) // stopping case 1. return n 2. return ( Fibonacci(n -1)+Fibonacci(n -2) ) // recursive case End Fibonacci 36
37. Fibonacci Numbers 37
38. Fibonacci Numbers 38
39. Fibonacci Numbers  The recursive program needlessly repeats the same calculations over and over.  The amount of time used by the recursive function to calculate Fn grows exponentially with n.  Simple iteractive program: starts at 0 and keep only three variables, the current Fibonacci number and its two predecessors. 39
40. Fibonacci Numbers (Iteractive version) 40
41. The Towers of Hanoi 41
42. The Towers of Hanoi 42
43. The Towers of Hanoi 43
44. The Towers of Hanoi Algorithm Move (val count ,val source , val destination , val auxiliary ) Moves count disks from source to destination using auxiliary. Pre There are at least count disks on the tower source. The top disk (if any) on each of towers auxiliary and destination is larger than any of the top count disks on tower source. Post The top count disks on source have been moved to destination; auxiliary (used for temporary storage) has been returned to its starting position. Uses recursive function Move. 1. if (count > 0) 1. Move (count -1, source, auxiliary, finish) 2. move a disk from source to finish 3. Move (count -1, auxiliary, finish, source) End Move 44
45. The Towers of Hanoi 45
46. The Towers of Hanoi Does the program for the Towers of Hanoi produce the best possible solution? (possibly include redundant and useless sequences of instruction sush as: • Move disk 1 from tower 1 to tower 2. • Move disk 1 from tower 2 to tower 3. • Move disk 1 from tower 3 to tower 1. ) How about the depth of recursion tree? How many instructions are needed to move 64 disks? (One instruction is printed for each vertex in the tree, except for the leaves with count = 0) 46
47. The Towers of Hanoi The depth of recursion is 64, not include the call with count = 0 which do nothing. Total number of moves: If one move takes 1s, 264 moves take about 5 x 1011 years! Recursive program for the Towers of Hanoi would fail for lack of time, but not for lack of space. 47
48. The Towers of Hanoi 48
49. Recursion When recursion should or should not be used? 49
50. Recursion or Not? Chain:  Recursive function makes only one recursive call to itself.  Recursion tree does reduce to a chain: each vertex has only one child.  By reading the recursion tree from bottom to top instead of top to bottom, we obtain the iterative program. Recursion tree for calculating factorials  We save both space and time. 50
51. Recursion or Not? Notice of the chain:  A chain: recursive function makes only one recursive call to itself.  Recursive call appears at only one place in the function, but might be inside a loop: more than one recursive calls!  Recursive call appears at more than one place in the function but only one call can actually occur (conditional statement) 51
52. Recursion or Not? Duplicate tasks: th Recursion tree for the calculation of 7 Fibonacci number 52
53. Recursion or Not? Duplicate tasks:  Recursion tree for calculating Fibonacci numbers contains many vertices signifying duplicate tasks.  The results stored in the stack, used by the recursive program, are discarded rather than kept in some other data structure for future use.  It is preferable to substitute another data structure that allows references to locations other than the top of the stack. 53
54. Recursion or Not? Comparison of Fibonacci and Hanoi: • Both have a very similar divide-and-conquer form. • Each consists of two recursive calls. • Hanoi recursive program is very efficient. • Fibonacci recursive program is very inefficient. • Why? • The answer comes from the size of the output! • Fibonacci calculates only one number, while • For Hanoi, the size of the output is the number of instructions to be printed, which increases exponentially with the number of disks. 54
55. Recursion or Not? 55
56. Recursion or Not? If the recursion tree has a simple form: iterative version may be better. If the recursion tree involves duplicate tasks: data structures other than stacks will be appropriate, the need for recursion may disappear. If the recursion tree appears quite bushy, with little duplication of tasks: recursion is likely the natural method. 56
57. Recursion or Not? Top-down design: Recursion is something of a top-down approach to problem solving. Iteration is more of a bottom-up approach. Stacks or recursion? Any recursion can be replaced by iteration stack. When recursion should be removes? When a program involves stacks, the introduction of recursion might produce a more natural and understandable program. 57
58. Recursion Removal • Recursion can be removed using stacks and iteration. 58
59. Recursion Removal Algorithm P (val n ) 1. if (n = 0) Execution: 1. print("Stop") Q(n) 2. else Q(n-1) 1. Q(n ) 2. P(n - 1) 3. R(n) Q(1) End P Stop R(1) R(2) R(n) 59
60. Recursion Removal Algorithm P (val n ) Algorithm P (val n ) 1. if (n = 0) 1. stackObj 1. print("Stop") 2. loop (n >0) 2. else 1. Q(n ) 1. Q(n ) 2. stackObj.Push(n) 2. P(n - 1) 3. n = n – 1 3. R(n) 3. print("Stop") End P 4. loop (NOT stackObj.isEmpty()) 1. stackObjTop(n ) 2. stackObj.Pop() 3. R(n ) End P 60
61. Tail Recursion DEFINITION : Tail recursion occurs when the last-executed statement of a function is a recursive call to itself. • Tail recursion can be eliminated by reassigning the calling parameters to the values specified in the recursive call, and then repeating the whole function. 61
62. Subprogram calls 62
63. Tail Recursion • When the recursive call is initiated, the local variables of the calling function are pushed onto the stack. • When the recursive call terminates, these local variables are popped from the stack and used for the calling function. • But there is no any task the calling function must do. • If space considerations are important, tail recursion should be removed. 63
64. Tail Recursion 64
65. Tail Recursion 65
66. Tail Recursion 66
67. Backtracking 67
68. Eight Queens problem PROBLEM: Place eight queens on the chess board in such a way that no queen can capture another. Algorithm EightQueens Finds all solutions of Eight Queens problem. Pre ChessBoard contains no Queen. Post All solutions of Eight Queens problem are printed. Uses Recursive function RecursiveQueens. 1. row = 0 2. RecursiveQueens(ChessBoard, row) 68
69. Eight Queens problem Algorithm RecursiveQueens(val ChessBoard , val r ) Pre ChessBoard represents a partially completed arrangement of nonattacking queens on the rows above row r of the chessboard Post All solutions that extend the given ChessBoard are printed. The ChessBoard is restored to its initial state. Uses recursive function RecursiveQueens. 69
70. Eight Queens problem Algorithm RecursiveQueens(val chessBoard , val r ) 1. if (ChessBoard already contains eight queens) 1. print one solution. 2. else 1. loop (more column c that cell[r, c] is unguarded) 1. add a queen on cell[r, c] 2. RecursiveQueens(chessBoard) // recursivelly continue to // add queens to the next rows. 3. remove a queen from cell[r, c] End RecursiveQueens 70
71. Eight Queens problem • Data structure for version 1 of class Board 71
72. Eight Queens problem class Board_ver1 { }; 72
73. Eight Queens problem Algorithm RecursiveQueens(val chessBoard , val r ) 1. if (ChessBoard already contains eight queens) 1. print one solution. board[r][c]=1 2. else 1. loop (more column c that cell[r, c] is unguarded) 1. add a queen on cell[r, c] 2. RecursiveQueens(chessBoard) // recursivelly continue to add // queens to the next rows. 3. remove a queen from cell[r, c] End RecursiveQueens 73
74. Eight Queens problem • Data structure for version 2 of class Board 74
75. Eight Queens problem Refinement: class Board_ver2 { }; This implementation keeps arrays to remember which components of the chessboard are free or are guarded. 75
76. Eight Queens problem Algorithm RecursiveQueens(val chessBoard , val r ) 1. if (ChessBoard already contains eight queens) col_free[c] = 0 1. print one solution. upward_free[r+c]=0 downward_free[r-c]=0 2. else 1. loop (more column c that cell[r, c] is unguarded) 1. add a queen on cell[r, c] 2. RecursiveQueens(chessBoard) // recursivelly continue to add // queens to the next rows. 3. remove a queen from cell[r, c] End RecursiveQueens
77. Eight Queens problem Algorithm RecursiveQueens(val chessBoard , val r ) 1. if (ChessBoard already contains eight queens) col_free[c] = 1 1. print one solution. upward_free[r+c]=1 2. else downward_free[r-c]=1 queen_in_row[r] = c 1. loop (more column c that cell[r, c] is unguarded) 1. add a queen on cell[r, c] 2. RecursiveQueens(chessBoard) // recursivelly continue to add // queens to the next rows. 3. remove a queen from cell[r, c] End RecursiveQueens col_free[c] = 0 upward_free[r+c]=0 downward_free[r-c]=0
78. Eight Queens problem Class Queens_ver1 Class Queens_ver2 78
79. Eight Queens problem 79
80. Eight Queens problem Recursion tree for Eight Queens problem Each node in the tree might have up to eight children (recusive calls for the eight possible values of column). Most of the branches are found to be impossible. Backtracking is a most effective tool to prune a recursion tree to manageable size. 80
81. Tree-Structured Program 81
82. Tree-Structured Program Look-ahead in Game Computer algorithm plays a game by looking at moves several steps in advance Evaluation function Examine the current situation and return an integer assessing its benefits. 82
83. Tree-Structured Program Minimax method At each node of the tree, we take the evaluation function from the perspective of player who must make the first move. First player wishes to maximize the value. Second player wishes to maximize the value for oneself, i.e. minimize value for the first player. In evaluating a game tree we alternately take minima and maxima, this process called a minimax method 83
84. Look-ahead in Game Look_ahead(val board , val depth , ref recommended_move ) Pre board represents a legal game position. Post An evaluation of the game, based on looking ahead depth moves, is returned. recommended_move contains the best move that can be found for the mover. Uses Recursive function Look_ahead 84
85. Look_ahead(val board , val depth , ref recommended_move ) 1. if ( (game is over) OR (depth=0) ) 1. return board.evaluate() // return an evaluation of the position. 2. else 1. list 2. Insert into list all legal moves 3. best_value = WORST_VALUE //initiate with the value of the worst case 4. loop (more data in list) // Select the best option for the mover among 1. list.retrieve(tried_move) // values found in the loop. 2. board.play(tried_move) 3. value = Look_ahead (board, depth-1, reply) // the returned value 4. if (value > best_value) // of reply is not used at this step. 1. best_value = value 2. recommended_move = tried_move 5. board.unplay(tried_move) 5. return best_value 3. End Look_ahead 85