CompSci 4Chap 8 Sec 1 Nov 17, 2005Prof. Susan RodgerNote: thanks to Wanda Dann and Steve Cooper for slide ideasAnnouncements• Read Chapter 10, Section 1 and 2 for next time– Sec 1 is a review of variables– Sec 2 introduces arrays• Note: We will NOT cover Chap 8, Sec 2What we will do today• Lecture on Chap 8 Section 1– Recursion• ClassworkRepetition• Sometimes don’t know exactly how many times a block of instructions should be repeated– Repeat until some condition is true– Repetition gets closer to condition being true• Example – Chess, don’t know when in advance how many moves til game endsIndefinite Repetition• When number of repetitions is indefinite– While statement – previously– Recursion - todayRecursion• Many times a structure is identified by a special word– Do in order– Do Together– If/Else–Loop• Recursion– Is NOT a program statement with a special word– Recursion means a method (or function) calls a clone of itselfExample – horse race•Horse race• One horse randomly selected to move forward, repeatedly• First horse to finish line is winnerStoryboard• “do everything again” means the entire method should be repeated – this is recursionraceif one of the horses has wonwinner says “I won”elserandomly choose horse and movedo everything again“Do everything again” -Call race method• Recursion means that a method calls a “clone of itself”raceif one of the horses has wonwinner says “I won”elserandomly choose horse and movecall the race methodStepwise Refinementraceif one of the horses has wonwinner says “I won”elserandomly choose horse and movecall the race methodisGameOver?whichHorseWon?moveRandomHorseForwardisGameOver and WhichHorseWon• isGameOver– Is the finish line < 0.5 meters in front of any horse? If so, game is over– Returns true if game is over•WhichHorseWon– Which horse is within 0.5 meters of finish line?– Returns the horse that wonmoveRandomHorseForward• To choose horse to move forward, use built-in random selection functionrace method• Uses recursion• Where is the “way out”?Classwork today• Written: raceHorse move recursive statement• Write recursive method BunnysMeet– Two bunnys repeatedly hop towards each other at the same time, as long as they are > 3 meters apart. – When bunnys are close (<= 3 meters apart but still at least 2 meters apart, 1 bunny hops once.– When bunnys are too close to jump any more, they bow to each other once at the same time.• Download file:
View Full Document