T-Th 9:05 |
CS 1110: Introduction to Computing Using Python Fall 2012 |
Main
About: Announcements Staff Consultants Times & Places Calendar Materials: Texts Python Command Shell Terminology Handouts: Lectures Assignments Labs Assessment: Grading Exams Resources: CMS Piazza (link) Piazza (about) AEWs FAQ Python API Style Guide Academic Integrity |
RecursionThere is a PDF version of these instructions, if you would prefer to have that instead. This lab gives you experience with writing recursive functions. All of the functions in this lab will either be recursive functions on sequences (e.g. strings or lists), or recursive functions on integers, just as we saw in class. This is a fairly important lab. If you do not finish today, please be sure to finish it soon after you get back from Fall Break. Requirements For This LabWe have created a few files for this lab. You should create a new directory on your hard drive and download the following modules into that directory:
The last two files are unit tests that we have provided for you. You do
not need to write your own unit tests in this lab. All you need to worry
about are the functions in To successfully complete this lab, you should implement the first four functions in the file recursive.py. When you have done this, show your file to a TA. As always, you should try to finish the lab during your section. However, this is a longer lab than the past two (now that you are done with all that work), and so it may not be possible. If you do not finish during section, you have two weeks to finish, as there is no lab section the week of fall break. Show your work to your instructor at the beginning of your next lab. As always, remember that labs are graded on effort, not correctness. Recursive FunctionsRemember that creating and understanding a recursive function involves four points: A precise specification of the functionWithout this, you cannot write the function. Handling the base case properlyThe base case involves the "smallest" parameter values, for which the result can be given easily, without the need for recursive calls. For a function that works on a sequence (e.g. either a string or a list), the base case is usually a sequence of length 0 (or both length 0 and 1). However, it could be something else, depending on the problem.
For a function that works on the natural numbers
In the module Handling the recursive case properlySolve the original problem in terms of the same problem but on a "smaller"
value. For example, if the function involves a sequence (e.g. a string
or a list) In writing/understanding a recursive call, understand it in terms of the specification of the function being called. Do not try to trace the execution in your head. Making progress toward terminationIn keeping with the last point, the arguments of a recursive call must be in some measure smaller than the parameters of the method; this is what ensures termination. Each recursive call has "smaller arguments", so that after some point, the base case will be reached. For example, if the argument is a sequence (e.g. either a string or a list), then each call should be on a smaller slice of the sequence. Lab ActivitiesIn this lab, you are to implement the first four functions from the module recursive.py. These are the ones specified below. All your implementations must be recursive (practicing recursion is the point of this lab).
|