Unformatted text preview:

© 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 involvinghuman 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 twosections 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 theitem being searched for is found• Binary search– If we know the collection is sorted, we can do better!– Repeatedly halves the collection and determines whichhalf 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 tostop• Base case: a known case in a recursive definition– Eventually, one of the smaller problems must be thebase 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 smallerproblem of the same type?– How does each recursive call diminish the size of theproblem?– What instance of the problem can serve as the basecase?– As the problem size diminishes, will you reach thisbase 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) * … * 1for 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 asequence 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 recursivemethod– Each box roughly corresponds to an activation record– An activation record• Contains a method’s local environment at the timeof 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 localenvironment includes:– The method’s localvariables– A copy of the actualvalue arguments– A return address in thecalling routine– The value of themethod itselfFigure 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 thelength 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 tracedusing the box trace• Temporary System.out.println statementscan 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 ofevents 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 monthsafter birth, that is, at the beginning of its third month oflife– Rabbits are always born in male-female pairs• At the beginning of every month, each sexuallymature male-female pair gives birth to exactly onemale-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 Rabbits(The Fibonacci Sequence)Figure 3-10Figure 3-10Recursive solution to the rabbit problem© 2006 Pearson Addison-Wesley. All rights reserved 3-20Multiplying Rabbits(The Fibonacci Sequence)• Base cases– rabbit(2), rabbit(1)• Recursive definitionrabbit(n) = 1 if n is 1 or 2 rabbit(n-1) + rabbit(n-2) if n > 2• Fibonacci sequence– The series of numbers rabbit(1), rabbit(2), rabbit(3),and so on© 2006 Pearson Addison-Wesley. All rights reserved 3-21Organizing a Parade• Rules about organizing a parade– The parade will consist of bands and floats in a singleline– One band cannot be placed immediately after another• Problem– How many ways can you


View Full Document

VASSAR CMPU 102 - Recursion

Download Recursion
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Recursion and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Recursion 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?