CS21 Lab 9: Recursion

Run update21, if you haven't already done so, to create the cs21/labs/09 directory. Then cd into this directory to create the python programs for this lab.

This week we will write a few different, smaller programs, all using recursion.

In a file called insert.py, write a program that asks the user to enter a string and then a pattern to insert between the characters of the string. Include in this program both a recursive and an iterative function to perform the insertions. Both functions should only need two parameters:

insertPattern(string, pattern) 
recursiveInsertPattern(string, pattern) 

Examples are shown below:

$ python insert.py 

 string: hello
pattern: *

iterative: h*e*l*l*o
recursive: h*e*l*l*o

$ python insert.py 

 string: ponies
pattern: !!

iterative: p!!o!!n!!i!!e!!s
recursive: p!!o!!n!!i!!e!!s

Note: You only need to use + to do concatentation of strings. Do not use join or list.

Write a program called parse.py that parses a user-given string for matching parentheses. Your program should output either True or False, depending on if the given string has the correct syntax (all parens have a match). Your program should use a recursive function to determine if the string has correct syntax or not. Here are a few examples:

$ python parse.py 

string: ()()()
True

$ python parse.py 

string: ((( () () ))
False

$ python parse.py 

string: (we)((LOVE))(C)(S)
True

$ python parse.py 

string: r = Rectangle(Point(x1,y1),Point(x2,y2)
False

Note: the user can type in any string, and your program should work.

One way to do this is to keep track of matching parentheses with a level indicator. For example, starting at level 0, if you are parsing a string and encounter three consecutive opening parens, "(", that would change the level to 3. Encountering a closing paren would decrease the level by 1. Here are the rules and some examples:

• start with level = 0
• if you encounter an opening paren, "(", increase the level by 1
• if you encounter a closing paren, ")", decrease the level by one
• the level should never become negative
• at the end of the string, the level should be back to 0

Here are some examples of parsing a string for matching parens. These are only to help you understand the algorithm -- your program does not need to produce this output.

  string:  ((()()))
   level: 012323210
  result: OK

  string:  (())  )()
   level: 012100-1
  result: incorrect syntax

  string:  4*(5+6)*(3.14)
   level: 000111100111110
  result: OK
  
  string:  int(raw_input("int: ")
   level: 00001111111111222222221
  result: incorrect syntax

Write a program called binary.py that uses recursion to convert integers into their binary equivalent. Here are some examples:

$ python binary.py 

number: 412
110011100

number: 256
100000000

Binary numbers are just like regular numbers, except there are only two possible values, 0 and 1. When you count using regular numbers, when you get to 9 (the highest single-digit value), the digit in the ones column goes back to 0 and you "carry" the 1 to the tens column, producing 10. The same happens in binary, except the highest single-digit value is 1, so the carry happens after only two numbers. Here's a table of the first ten numbers:

Notice how the digit in the ones column just repeats 0, then 1, then back to 0, etc.

For this problem you can use the % and / operators to get the rightmost digits of the binary number from the original number. Here's an example using 6:

n = 6
n%2 = 0 (rightmost digit of binary 6)
n/2 = 3 (use to get next rightmost digit of binary number)

3%2 = 1 (next rightmost digit of binary 6)
3/2 = 1 (use to get next...)

1 is less than 2, so this is the last digit

put them all together to get 110

Here's the start of the 412 example above:

n = 412
n%2 = 0 (rightmost digit of binary 412)
n/2 = 206 (use to get next rightmost digit of binary number)

206%2 = 0 (next rightmost digit of binary 412)
206/2 = 103 (use to get next...)

103%2 = 1 (next rightmost digit of binary 412)
103/2 = 51 (and so on...)

Hint: what type of data should this function return? If we are putting together digits (1's and 0's) to make the final result (e.g, 110011100), should the digits be integers that we just add together??

Write a graphics program called diamonds.py that uses a recursive function to display an image like the following one (using Zelle graphics):

Your recursive function should have the following 4 parameters:

• graphics window to draw to
• center point of diamond
• size of diamond
• color to use or recursion level

(adding another parameter for how much the size changes with each recursion is a nice addition)

Your picture does not have to be identical to the one above (you may use different colors and sizes), but it should:

• show at least 4 levels of recursion
• alternate colors between each level (e.g., odd levels are black, even are white)

For the above image, I reduced the size of the diamond each time to 0.33 * the previous size, and each subsequent diamond is moved horizontally and vertically from the previous diamond by size.

Note: to draw diamonds, you will need to use the Polygon() constructor.

Once you are satisfied with your program, hand it in by typing handin21 in a terminal window.