Chapter 5 Recursion

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

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

5.1 Introduction

5.2 Factorial

5.2.1 Execution Frames

5.3 Decimal to Binary

Example 3: Towers of Hanoi 河內塔

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的問題

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

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

Tower of Hanoi Tower of hanoi http://www.cut-the-knot.org/recurrence/hanoi.shtml

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

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

/** move 決定disks從原來的pole移動到目的pole所需要的步驟. * The worstTime(n) is O(2n). * * @param n n個disk需要被移動. * @param orig disk一開始所在的pole. * @param dest 目的的pole. * @param temp 當作暫時存放的pole. * @return 以一個字串表示需要如何移動. * @throws 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

5.4.1 Analysis of the move Method

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

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

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

To trace the execution of this recursive move function: http://www.cs.lafayette.edu/~collinsw/hanoi2/hanoiins.html

5.5 Searching An Array

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

英詞中句 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.

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)

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的相反順序倒退.

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. P3 P2 P1 P4 P5 G2 P7 P6 G1    

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拜訪.  

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利用.

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, 它們是相同的.

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

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

5.6.1 An A-maze-ing Application

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

Solution: 9 = Path; 2 = dead end 9 9 9 0 2 2 0 0 0 2 2 2 2 1 0 9 9 9 0 2 2 2 2 2 0 2 1 0 0 0 9 0 2 0 2 0 2 0 2 1 0 0 0 9 2 2 0 2 0 2 2 2 1 1 1 1 9 0 0 0 0 1 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 9 9 9 9 9 9 9 9 9

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, 所以:

Exercise: Recall the solution when the order was north, east, south, west: 9 9 9 0 2 2 0 0 0 2 2 2 2 1 0 9 9 9 0 2 2 2 2 2 0 2 1 0 0 0 9 0 2 0 2 0 2 0 2 1 0 0 0 9 2 2 0 2 0 2 2 2 1 1 1 1 9 0 0 0 0 1 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 9 9 9 9 9 9 9 9 9

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