CS21 Lab 9: Recursion

Due Saturday Night, November 21
giraffe image

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.

1. Silly Text

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


$ python sillytext.py 
string: Whale
num: 3


$ python sillytext.py 
string: robot
num: 0

#in the case above, no text is printed

$ python sillytext.py 
string: recursion
num: 1


2. Remove characters

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


$ python cleanstring.py 
string: November
ch    : ember
Invalid. Please enter a single character
ch    : 
Invalid. Please enter a single character
ch    : d


3. File search

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/")
>>> isdir("/usr/share/dict/words")
>>> isdir("/puppy")

The function listdir list the names of files and directories in a given directory. Some examples are shown below.

['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

>>> 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


$ python findfiles.py
path   : ~/cs21/labs
pattern: findfiles


$ python findfiles.py
path   : ~/cs21/labs
pattern: py


$ python findfiles.py
path   : ~/cs21
pattern: mp3

#in the case above, no text is printed

4. Recursive Graphics

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:

star image flower image smiley image

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