Chapter 5 Recursion.

Presentation on theme: "Chapter 5 Recursion."— Presentation transcript:

1 Chapter 5 Recursion

2 Chap.5 Contents 5.1 Introduction 5.2 Factorial 5.2.1 Execution Frames
5.3 Decimal to Binary 5.4 Towers of Hanoi 5.4.1 Analysis of the move Method 5.5 Searching An Array 5.6 Backtracking 5.6.1 An A-maze-ing Application 5.8 The Cost of Recursion

3 Recursive v.s. Iterative
OCCUR 發生 RECUR 重覆發生 Recursion Recursive ITERATE 重覆發生 Iteration Iterative

4 5.1 Introduction

5

6

7 5.2 Factorial

8

9

10

11

12 5.2.1 Execution Frames

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31 5.3 Decimal to Binary

32

33

34

35

36

37

38

39

40

41

42

43 Example 3: Towers of Hanoi
河內塔

44

45

46 Design sketch for case n=4
1.First, see if the simplest case n=1 works. 首先, 假設最簡單的例子 n=1. 2.Next, by mathematical induction, assuming n=3 works, that is, 3 disks can be magically moved to the destination, 接下來, 用數學歸納法假設n=3 那就是3個disks移動到目的地 3.Then, draw design sketches to solve n=4, 4 disks problem. 然後, 畫出設計草圖來解決n=4, 4個disks的問題

47 The simplest case n=1 Simply move the disk from A to B. It is done.
簡單的移動disk從A到B. Thus, case n=1 works. 這樣 case n =1就做完了. Next, try to solve n=4 case by assuming n=3 works. 接下來, 使用n=3的方式來解決n=4的case

48 下面四張 n=4 的設計草圖 清楚引導出 後面虛凝碼 (演算法) 的設計 這是軟體開發的重要工序 至於如何想出設計草圖? 經驗加能力吧

49 Tower of Hanoi Tower of hanoi

50

51 2) 把 disk n (disk 4) 從A移到B

52 3) 把 n-1 (that is 3) disks 從 C 移動到 B

53

54

55

56 /** move 決定disks從原來的pole移動到目的pole所需要的步驟.
* The worstTime(n) is O(2n). * n n個disk需要被移動. orig disk一開始所在的pole. dest 目的的pole. temp 當作暫時存放的pole. 以一個字串表示需要如何移動. IllegalArgumentException if n 小於或等於0. */ public static String move (int n, char orig, char dest, char temp) { final String DIRECT_MOVE = "Move disk " + n + " from " + orig + " to " + dest + "\n"; if (n <= 0) throw new IllegalArgumentException( ); if (n == 1) return DIRECT_MOVE; return move (n ‑ 1, orig, temp, dest) + DIRECT_MOVE move (n ‑ 1, temp, dest, orig) ; } // end of move

57 5.4.1 Analysis of the move Method

58

59

60 The total number of calls to move is: 移動所需要的全部calls次數是:
… + 2n-1 = Σ 2i i=0

61 See example 6 of Appendix 2 for a proof by mathematical induction.

62 This shows that: worstTime(n) is O(2n)

63 To trace the execution of this recursive move function:

64

65 5.5 Searching An Array

66

67

68

69

70

71

72

73 比較 英文 與 中文method descriptions
接下來的兩頁是中文的版本. 比較這兩個版本. 哪一個版本 比較容易瞭解?

74

75

76 英詞中句 interface /* 用 binary search 在特定 array 找特定object.
array 須依自然順序排序，否則結果 undefined. if array 含多個特定object, 不保證找到何者 The worstTime(n) is O(log n). @param a – 被找的 array @param first – array目前找尋範圍的最小index @param last - array目前找尋範圍的最大index @param key - 要找的object.

77 public static int binarySearch (Object[ ] a, int first, int last,
@return 要找的 object 的 index, if 此 object 存在 array 中 傳回找到的 index else 傳回 - insertion point -1 insertion point 為將此 object 按順序插入 array 中的 index @throws ClassCastException if array 含有不能互相 compare 的 elements (如 strings 與 integers) or 要找的 object 不能與 array 中的 elements 互相 compare */ public static int binarySearch (Object[ ] a, int first, int last, Object key)

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94 5.6 Backtracking Backtracking is the strategy of
trying to reach a goal by a sequence of chosen positions, with re-tracing in reverse order of positions that cannot lead to the goal. Backtracking 是試著以 一系列選取的 positions 到達目的地的策略,同時依不能通到目的地的positions的相反順序倒退.

95 Strategy: try to go west; if unable to go west, try to go south; if unable to go south, backtrack (until you can go south). 試著向西, 如果沒辦法向西, 就試著向南; 如果不能向南, 就返回原路 (直到你可以向南) Do not go to any position that has been shown not to lead to a goal. The goal is either G1 or G2. Start at P1. 不要去任何已經被標示不能通到終點的位置. 終點不是G1就是G2. 起點是P1. P P P1 P P5 G P P6 G1

96 For example, P4 is not visited from P5.
When a position is visited, it is marked as (potentially) being on a path to the goal. 當一個地點被拜訪時, 它會被標示當作(可能的)通往終點的路徑. If we discover otherwise, the marking must be undone, so that position will never again be visited. 如果我們發現不是, 標記就會被取消, 這個地點不會再被拜訪. For example, P4 is not visited from P5. 例如, P4 不會被從P5拜訪.

97 within the general framework of backtracking,
We will solve this: 我們將解決這一個問題: maze-search problem within the general framework of backtracking, 使用一般的backtracking 的 framework , which can easily be utilized in other applications. 它可以比較輕易的被其它applications利用.

98 The Application interface and the Backtrack class are generic:
The Application interface and the Backtrack class are generic: 這個Application interface和Backtrack class為泛型: They are the same for any backtracking project. 對於任何backtracking project, 它們是相同的.

99 import java.util.*; public interface Application { // 如果pos是合法位置 就回傳true. boolean isOK (Position pos);    // 標示pos為可能在通往終點的路徑上. void markAsPossible (Position pos); // 如果pos是終點 傳回true. boolean isGoal (Position pos);

100 //標示pos為不在通往終點的路徑上. void markAsDeadEnd (Position pos); //回傳字串表示方式. String toString(); //回傳 iterator 從 pos 可直接到達的 positions. Iterator<Position> iterator (Position pos); } // interface Application

101

102

103

104

105

106

107

108

109 5.6.1 An A-maze-ing Application

110 Maze searching: 1 = Corridor; 0 = Wall start 1 1 1 0 1 1 0 0 0 1 1 1 1
finish Iterator choices: north, east, south, west Marked as possible = 9; dead end = 2

111 Solution: 9 = Path; 2 = dead end

112 All that need to be developed are: the Position class,
所有需要開發的是: the Position class, the class that implements the Application interface and a tester. 這個class實做Application interface和 tester. For this application, a position is simply a row and column, so: 對於這一個application, Position就是row和column, 所以:

113

114

115

116

117

118

119

120

121

122 Exercise: Recall the solution when the order was north, east, south, west:

123 Re-solve with the order north, east, west, south:
start finish Hint: Only one ‘1’ remains.