Chapter 3Preliminaries: First day of class…Slide 3Slide 4Recursive SolutionsSlide 6Slide 7Slide 8A Recursive Valued Method: The Factorial of nSlide 10Slide 11Slide 12A Recursive void Method: Writing a String BackwardSlide 14Slide 15Counting ThingsMultiplying Rabbits (The Fibonacci Sequence)Slide 18Slide 19Slide 20Organizing a ParadeSlide 22Slide 23Slide 24Mr. Spock’s Dilemma (Choosing k out of n Things)Slide 26Slide 27Slide 28Slide 29Searching an Array: Finding the Largest Item in an ArrayFinding the Largest Item in an ArrayBinary SearchSlide 33Finding the kth Smallest Item in an ArraySlide 35Slide 36Organizing Data: The Towers of HanoiThe Towers of HanoiSlide 39Recursion and EfficiencySummarySlide 42Slide 43© 2006 Pearson Addison-Wesley. All rights reserved 3-1Chapter 3Recursion: The MirrorsCS102 Sections 51 and 52Marc Smith and Jim Ten EyckSpring 2008© 2006 Pearson Addison-Wesley. All rights reserved 3-2Preliminaries:First day of class…•Syllabus / Course home page–Course content and written req’s–Type and number of exams(3 including final; open book / open notes)•CS Dept–Available 24/7 during the semester–Your student ID card will unlock door•Office hours posted© 2006 Pearson Addison-Wesley. All rights reserved 3-3Preliminaries:First day of class…•This course is available as NRO(for non-majors only)•Textbook available in the College Store•This course involves no research involving human subjects--for the most part… :-)© 2006 Pearson Addison-Wesley. All rights reserved 3-4Preliminaries:First day of class…•Labs: officially in the Asprey Lab…–but we’ll use the printers in the Intro Lab–and we might spill over into the Intro Lab–unless we can more evenly balance the two sections during Monday labs–any volunteers? (please see me)•Academic accommodations•Let’s begin!© 2006 Pearson Addison-Wesley. All rights reserved 3-5Recursive Solutions•Recursion–An extremely powerful problem-solving technique–Breaks a problem in smaller identical problems–An alternative to iteration (*)•An iterative solution involves loops(*) Iteration is a special case of recursion: tail recursion© 2006 Pearson Addison-Wesley. All rights reserved 3-6Recursive Solutions•Sequential search–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–If we know the collection is sorted, we can do better!–Repeatedly halves the collection and determines which half could contain the item–Uses a divide and conquer strategy© 2006 Pearson Addison-Wesley. All rights reserved 3-7Recursive Solutions•Facts about a recursive solution–A recursive method calls itself–Each recursive call solves an identical, but smaller, problem–A test for the base case enables the recursive calls to stop•Base case: a known case in a recursive definition–Eventually, one of the smaller problems must be the base case© 2006 Pearson Addison-Wesley. All rights reserved 3-8Recursive Solutions•Four questions for constructing recursive solutions–How can you define the problem in terms of a smaller problem of the same type?–How does each recursive call diminish the size of the problem?–What instance of the problem can serve as the base case?–As the problem size diminishes, will you reach this base case?© 2006 Pearson Addison-Wesley. All rights reserved 3-9A Recursive Valued Method: The Factorial of n•Problem–Compute the factorial of an integer n•An iterative definition of factorial(n)factorial(n) = n * (n-1) * (n-2) * … * 1 for any integer n > 0factorial(0) = 1© 2006 Pearson Addison-Wesley. All rights reserved 3-10A Recursive Valued Method: The Factorial of n•A recursive definition of factorial(n)factorial(n) = 1 if n = 0 n * factorial(n-1) if n > 0 •A recurrence relation–A mathematical formula that generates the terms in a sequence from previous terms–Examplefactorial(n) = n * [(n-1) * (n-2) * … * 1] = n * factorial(n-1)© 2006 Pearson Addison-Wesley. All rights reserved 3-11A Recursive Valued Method: The Factorial of n•Box trace–See examples, p. 120, 126–A systematic way to trace the actions of a recursive method–Each box roughly corresponds to an activation record–An activation record•Contains a method’s local environment at the time of and as a result of the call to the method© 2006 Pearson Addison-Wesley. All rights reserved 3-12A Recursive Valued Method: The Factorial of n•A method’s local environment includes:–The method’s local variables–A copy of the actual value arguments–A return address in the calling routine–The value of the method itself Figure 3-3Figure 3-3A box© 2006 Pearson Addison-Wesley. All rights reserved 3-13A Recursive void Method: Writing a String Backward•Problem–Given a string of characters, write it in reverse order•Recursive solution–Each recursive step of the solution diminishes by 1 the length of the string to be written backward–Base case•Write the empty string backwardDoes this problem sound familiar to some of you?© 2006 Pearson Addison-Wesley. All rights reserved 3-14A Recursive void Method: Writing a String BackwardFigure 3-6Figure 3-6A recursive solution© 2006 Pearson Addison-Wesley. All rights reserved 3-15A Recursive void Method: Writing a String Backward•Execution of writeBackward can be traced using the box trace•Temporary System.out.println statements can be used to debug a recursive method© 2006 Pearson Addison-Wesley. All rights reserved 3-16Counting Things•Next three problems–Require you to count certain events or combinations of events or things–Contain more than one base cases–Are good examples of inefficient recursive solutions© 2006 Pearson Addison-Wesley. All rights reserved 3-17Multiplying Rabbits (The Fibonacci Sequence)•“Facts” about rabbits–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 male-female pair gives birth to exactly one male-female pair© 2006 Pearson Addison-Wesley. All rights reserved 3-18Multiplying Rabbits (The Fibonacci Sequence)•Problem–How many pairs of rabbits are alive in month n?•Recurrence relationrabbit(n) = rabbit(n-1) + rabbit(n-2)© 2006 Pearson Addison-Wesley. All rights reserved 3-19Multiplying