Report

COMPSCI 105 S2 2014 Principles of Computer Science Recursion 3 Agenda Agenda Textbook: 2 The Fibonacci Sequence The Towers of Hanoi Binary search Recursion and efficiency Problem Solving with Algorithms and Data Structures Chapter 4 – Recursion Chapter 5 – Searching COMPSCI105 22 22.1 The Fibonacci Sequence The Fibonacci Sequence Describes the growth of an idealised (biologically unrealistic) rabbit population, assuming that: 3 Rabbits never die A rabbit reaches sexual maturity exactly two months after birth, that is, at the beginning of its third month of life Rabbits are always born in male-female pairs At the beginning of every month, each sexually mature malefemale pair gives birth to exactly one male-female pair COMPSCI105 22 22.1 The Fibonacci Sequence The Fibonacci Sequence Problem How many pairs of rabbits are alive in month n? Example: rabbit(5) = 5 1 Month 2 Recurrence relation rabbit(n) = rabbit(n-1) + rabbit(n-2) 3 4 5 4 COMPSCI105 22 22.1 The Fibonacci Sequence Recursive Definition Base cases rabbit(2), rabbit(1) Recursive rabbit(n) = 1 if n is 1 or 2 rabbit(n-1) + rabbit(n-2) Fibonacci sequence The series of numbers rabbit(1), rabbit(2), rabbit(3), and so on The sequence of numbers rabbit(n) for all n is called Fibonacci Sequence or Fibonacci numbers. 5 if n > 2 def rabbit(n): if n <=2: return 1 return rabbit(n-1) + rabbit(n-2) COMPSCI105 22 22.1 The Fibonacci Sequence rabbit(6) rabbit(6) return rabbit(5)+rabbit(4) rabbit(5) return rabbit(4)+rabbit(3) rabbit(4) return rabbit(3)+rabbit(2) rabbit(3) return rabbit(2)+rabbit(1) rabbit(2) return 1 6 rabbit(2) return 1 rabbit(4) return rabbit(3)+rabbit(2) rabbit(3) rabbit(3) return rabbit(2)+rabbit(1) return rabbit(2)+rabbit(1) rabbit(2) return 1 rabbit(1) return 1 rabbit(2) return 1 rabbit(2) return 1 rabbit(1) return 1 rabbit(1) return 1 COMPSCI105 22 22.1 The Fibonacci Sequence Examples: Fibonacci Spiral Fibonacci Tiling 7 COMPSCI105 22 22.2 The Towers of Hanoi 2.6 The Towers of Hanoi Puzzle consists of n disks and three poles 8 The disks are of different size and have holes to fit themselves on the poles Initially all the disks were on one pole, e.g., pole A The task was to move the disks, one by one, from pole A to another pole B, with the help of a spare pole C. Due to its weight, a disks could be placed only on top of another disk larger than itself COMPSCI105 22 22.2 The Towers of Hanoi Solution If you have only one disk (i.e., n=1), If you have more than one disk, simply ignore the bottom disk and solve the problem for n-1 disk, with pole C is the destination and pole B is the spare Then move the largest disk from pole A to B; then move the n-1 disks from the pole C back to pole B We can use a recursion with the arguments: 9 move it from pole A to pole B Number of disks, source pole, destination pole, spare pole COMPSCI105 22 22.2 The Towers of Hanoi Solution defifhanoi(count,source,destination,spare): count is 1: Move a disk directly from source to destination Move count-1 disks from source to spare Applyfrom function recursively Move 1 disk source to destination to move these three disks.to destination Move count-1 disk from spare Source Source 10 destination destination spare Source Source spare COMPSCI105 destination destination spare spare 22 22.2 The Towers of Hanoi Pseudo code for the recursive solution Satisfies the four criteria of a recursive solution Recursive method calls itself Each recursive call solves an identical, but smaller problem Stops at base case Base case is reached in finite time def hanoi(count, source, destination, spare): if count <= 1: print ("base case: move disk from", source, "to", destination) else: 1 hanoi(count - 1, source, spare, destination) 2 print ("step2: move disk from", source, "to", destination) 3 hanoi(count - 1, spare, destination, source) 11 COMPSCI105 22 def hanoi(count, source, dest, spare): if count <= 1: print ("base case: move disk from", source, "to", dest) else: hanoi(count - 1, source, spare, dest) print ("step2: move disk from", source, "to", dest) hanoi(count - 1, spare, dest, source) Example: hanoi(3, "A", "B", "C") hanoi(3, ‘A’, ‘B’, ‘C’) Count = 3 Source = A Dest = B Spare = C ? ? hanoi(2, ‘A’, ‘C’, ‘B’) Count = 2 Source = A Dest = C Spare = B ? 3 Steps 3 Steps ? Print: from A to B A B hanoi(1, ‘A’, ‘B’, ‘C’ Count = 1 Source = A Dest = B Spare = C hanoi(1, ‘B’, ‘C’, ‘A’ Count = 1 Source = B Dest = C Spare = A C 12 3 Steps Base case: Print: from A to B A B C C Print: from A to C hanoi(2, ‘C’, ‘B’, ‘A’) Count = 2 Source = C Dest = B Spare = A ? Check Animation B A A B C A B C Base case: Print: from B to C hanoi(1, ‘C’, ‘A’, ‘B’ Count = 1 Source = C Dest = A Spare = B Base case: Print: from C to A A B C A B Print: from C to B hanoi(1, ‘A’, ‘B’, ‘C’ Count = 1 Source = A Dest = B Spare = C ? COMPSCI105 C Base case: Print: from A to B 22 22.2 The Towers of Hanoi Call Tree hanoi(3…) uses 10 calls, a top-level one and 9 recursive calls hanoi(3, ‘A’, ‘B’, ‘C’) hanoi(2, ‘A’, ‘C’, ‘B’) hanoi(2, ‘C’, ‘B’, ‘A’) Move A -> B A B C hanoi(1, ‘A’, ‘B’, ‘C’) hanoi(1 , ‘C’, ‘A’, ‘B’) Move A -> C A B C hanoi(1, ‘B’, ‘C’, ‘A’) A 13 Move C -> B B C A B A C COMPSCI105 B C hanoi(1, ‘A’, ‘B’, ‘C’) A B C A C B 22 22.3 Binary Search Binary Search Problem: look for an element (key) in an ordered collection Sequential search (e.g. find a word in a dictionary) Starts at the beginning of the collection Looks at every item in the collection in order until the item being searched for is found Binary search Cost? Repeatedly halves the collection and determines which half could contain the item Uses a divide and conquer strategy Search dictionary OR Search first half of dictionary 14 Search first half of dictionary COMPSCI105 22 22.3 Binary Search Implementation Implementation issues: 15 How will you pass “half of list” to the recursive calls to binary_search? How do you determine which half of the list contains value? What should the base case(s) be? How will binary_search indicate the result of the search? Example: a sorted list COMPSCI105 22 22.3 Binary Search Algorithm Design Base case: If array is empty number is not in the list, or If element is the one we look for return it Recursive call Determine element in the middle If the one we look for is smaller than element in the middle then search in the left half Otherwise search in the right half of the list Left half: [first .. mid-1] 0 first 16 1 2 Right half: [mid+1 .. last] 3 4 5 6 mid = (first + last)/2 COMPSCI105 7 8 9 last 22 22.3 Binary Search Example Code def binary_search(num_list, first, last, value): index = 0 if first > last: index = -1 else: mid = (first + last) // 2 if value == num_list[mid]: index = mid elif value < num_list[mid]: index = binary_search(num_list, first, mid-1, value) else: index = binary_search(num_list, mid+1, last, value) return index 17 COMPSCI105 22 index 22.3 Binary Search 0 1 2 3 4 5 6 7 Call Tree 1 5 9 12 15 21 29 31 A successful search for 9: value 9 first 0 last 7 0 7 mid 3 2 value anArray[3] binary_search(list,0,7,9) value 9 first 2 last 2 22 mid 2 2 value anArray[2] binary_search(list,0,2,9) value 9 first 0 last 2 02 mid 1 2 value anArray[1] binary_search(list,2,2,9) return 2 18 COMPSCI105 22 index 22.3 Binary Search 0 1 2 3 4 5 6 7 Call Tree 1 5 9 12 15 21 29 31 An unsuccessful search for 6: value 6 first 0 last 7 0 7 mid 3 2 value anArray[3] binary_search(list,0,7,6) value 6 first 2 last 2 binary_search(list,0,2,6) value 6 first 0 last 2 02 mid 1 2 value anArray[1] mid value anArray[2] binary_search(list,2,2,6) binary_search(list,2,1,6) 19 22 2 2 COMPSCI105 value 6 first 2 last 1 first last return 1 return -1 22 22.4 Efficiency Recursion and Efficiency Some recursive solutions are so inefficient that they should not be used Factors that contribute to the inefficiency of some recursive solutions 20 Overhead associated with method calls Inherent inefficiency of some recursive algorithms Note: The recursive methods binarySearch and solveTowers are quite efficient, but the fact and rabbit are inefficient COMPSCI105 22 22.4 Efficiency Recursion and Efficiency Do not use a recursive solution if it is inefficient and if you have a clear, efficient iterative solution Factorial’s recursive solution Rabbit counting recursive solution 21 Overhead associated with method calls Iterative method is more efficient Inherent inefficiency of recursive algorithms It computes same values over and over again, e.g., rabbit(7) computes rabbit (3) five times. Use rabbit’s recurrence relation to construct an efficient iterative solution COMPSCI105 22 22.4 Efficiency Iterative Solution def iterative_rabbit(n): previous = 1 current = 1 next_elt = 1 for i in range(3, n+1): next_elt = current + previous; previous = current; current = next_elt return next_elt 22 COMPSCI105 22 Exercise Given the following: my_list = [0, 1, 2, 8, 13, 17, 19, 32, 42] Draw the call tree of 23 binary_search(my_list,0,8,3) binary_search(my_list,0,8,13) COMPSCI105 22