CS21 Lab 9: Recursion
Run update21, if you haven't already, to create the cs21/labs/09 directory. Then cd into your cs21/labs/09 directory and create the python programs for lab 09 in this directory.
This week we will write a few smaller programs, all using recursion.
Some of the programs will use the Zelle graphics library again.
Write a program to create a silly text effect in the terminal window. Your program should include a main() function that asks the user for some text, then asks for a valid non-negative integer $n$. After getting the user's input, call a recursive function that creates and returns a string, where each letter of the original text is repeated $n$ times. Recall, you can use the * operator to repeat a string $n$ times, e.g., "hello"*2 evaluates to "hellohello"
Your recursive function should have just two parameters: the text string and the number of times to repeat each character. The function should return the final string to be printed in main(). Some examples are shown below.
$ python sillytext.py string: puppy num: 2 ppuuppppyy $ python sillytext.py string: Whale num: 3 WWWhhhaaallleee $ python sillytext.py string: robot num: 0 #in the case above, no text is printed $ python sillytext.py string: recursion num: 1 recursion
Write a program called cleanstring.py that removes a specified character from a string.
You should write a recursive function with just two parameters: the text string and the character to remove. The function should return the final string to be printed in main().
Write a small main program that prompts the user to enter a string and a character to remove and removes all occurrences of the character from the string. Your program should check the character entered is indeed a single character.
$ python cleanstring.py string: This . is ... a . test.. ch : . This is a test $ python cleanstring.py string: Mississippi ch : s Miiippi $ python cleanstring.py string: November ch : ember Invalid. Please enter a single character ch : Invalid. Please enter a single character ch : d November
Write a program in findfiles.py that allows the user to search for filenames containing a given pattern in a given directory. Your program should prompt the user to enter a directory to search and a pattern to look for, then print the names of all filenames contained within the given directory that contain the given pattern.
Since linux directories can contain either files or other subdirectories, you need to write a recursive function that recursively searches subdirectories for additional files and/or directories. Python provides a couple of convenient functions for helping you search paths and directories. You should include the following lines at the top of your program
from os import listdir from os.path import isdir, expanduser
The function isdir returns True if a given string is a directory and False otherwise. Below are some examples.
>>> isdir("/usr/share/dict/")
True
>>> isdir("/usr/share/dict/words")
False
>>> isdir("/puppy")
False
The function listdir list the names of files and directories in a given directory. Some examples are shown below.
listdir("/usr/share/dict/")
['cracklib-small', 'american-english', 'words',
'words.pre-dictionaries-common', 'README.select-wordlist']
>>> listdir("/home/adanner/public_html/cs21/f15")
['w03_decisions.php', 'book.jpg', 'private', 'book', 'img', 'viqr.pdf',
'w01_intro.php', 'w02_loops_nums_str.php', 'w04_loops.php', 'update.sh',
'outline.html', 'w07_design.php', 'ZelleCh5.pdf', 'stack-handout.pdf',
'graphics.php', 'Labs', 'index.php', 'Quizzes', 'outline.md', 'style',
'w05_graphics.php', 'w06_functions.php']
In linux, the string ~/ represents your home directory. To use this convenient shortcut in python, use the expanduser function.
>>> home = expanduser("~/")
>>> print home
/home/adas/
>>> listdir(home+"/cs21")
['inclass', 'labs', '.gitignore', '.git']
>>> listdir(home+"/cs21/labs")
['02', '00', '04', '09', '03', '07', '06', '05', '08', '01']
Your recursive function should accepts two input strings; a directory name and a pattern to search for. If there are any files whose name matches the pattern given, you should print out the full directory and file name. If there are any directories in the given input directory, you should recursively search those directories as well. You may need a for loop to process the result of listfiles. Some sample outputs of a working program are shown below.
$ python findfiles.py path : ~/cs21 pattern: txt /home/adas/cs21/inclass/w07-design/colors.txt /home/adas/cs21/labs/00/bio.txt /home/adas/cs21/labs/08/twitter-data.txt $ python findfiles.py path : ~/cs21/labs pattern: findfiles /home/adas/cs21/labs/09/findfiles.py $ python findfiles.py path : ~/cs21/labs pattern: py /home/adas/cs21/labs/02/patternA.py /home/adas/cs21/labs/02/store.py /home/adas/cs21/labs/02/missing.py /home/adas/cs21/labs/02/patternC.py /home/adas/cs21/labs/02/patternB.py /home/adas/cs21/labs/04/code.py /home/adas/cs21/labs/04/nim.py /home/adas/cs21/labs/04/race.py /home/adas/cs21/labs/09/findfiles.py /home/adas/cs21/labs/03/vo2max.py /home/adas/cs21/labs/03/message.py /home/adas/cs21/labs/03/countvowels.py /home/adas/cs21/labs/03/5qquiz.py /home/adas/cs21/labs/07/ww-design.py /home/adas/cs21/labs/06/listFns.py /home/adas/cs21/labs/05/shadowText.py /home/adas/cs21/labs/05/bubbleGame.py /home/adas/cs21/labs/05/trees.py /home/adas/cs21/labs/08/twitter_getter.py /home/adas/cs21/labs/01/tripcost.py /home/adas/cs21/labs/01/booksavings.py /home/adas/cs21/labs/01/drivetime.py $ python findfiles.py path : ~/cs21 pattern: mp3 #in the case above, no text is printed
Write a graphics program that uses recursion to draw a picture.
First write a graphics function to draw an object, like a star, a flower, a smiley face, or anything you choose. However, your function must work with the following parameters:
- a graphics window object
- a center point (where to draw your object)
- a size (how big to draw your object)
Your object should use at least four different shapes (they can all be the same type) and at least two colors. Test your function by calling it twice in main with different centers and sizes and see that you get the same image just scaled differently and in different locations.
Now write a full program called recursive-graphics.py that draws a picture similar to those below. Your main function should set up the graphics window and then call a recursive function to draw the objects. call your original drawStar() function (or drawFlower(), etc).
Your recursive function should take four input parameters
- a graphics window object
- a center point (where to draw the current object)
- a size (how big to draw the current object)
- an integer (how many additional level to recurse)
If the fourth argument to your recursive function is larger than 1, you should draw your original pattern drawStar() function (or drawFlower(), etc), and then recursively draw smaller versions of the pattern in at least two locations.
below is a recursive drawing with the fourth parameter set to 1. In this case we just draw the pattern we designed once.
below is a recursive drawing with the fourth parameter set to 2. In this case we just draw the main pattern we designed once, and then recursively draw smaller versions two the left and right.
below is a recursive drawing with the fourth parameter set to 5. Note there are five progressively smaller flower pattern sizes. Some of the patterns may be drawn outside the boundaries of the window. This is OK.
The examples below recurse multiple levels in four corners
Hacker's ChallengesThese are just fun, optional additions. Try these if you are looking for more to do (no bonus points).- In the sillytext example, you may have used the string repetition operator * to repeat a character $n$ times. Try to modify to program to use your recursive function instead and only use the + operator to build your strings.
SubmitOnce you are satisfied with your program, hand it in by typing handin21 in a terminal window.
Back to the CS21 homepage