Run update21 to create the cs21/labs/10 directory. Then cd into your cs21/labs/10 directory and create the python programs for lab 10 in this directory.

For this lab you will write a few programs that demonstrate the power of recursion. Using recursion often makes code more concise/readable than using an iterative solution. As you design recursive functions, make use of drawing the stack and tracing through your code to help you debug.

The goals for this lab assignment are:

• practice writing recursive functions
• practice with an iterative and recursive solution to the same problem
• continued practice with file I/O, functions and passing lists to functions, and top-down design
• designing test cases for testing program correctness

Before starting in on the programming parts of this lab, complete this worksheet (and note that it is due in class this week).

Print out this worksheet, answer the questions and turn it in in class this week (Friday Apr 14 or Thursday Apr 13): lab 10 worksheet

We are going to re-visit the series summation problem from Lab 2. This time you will write an iterative and a recursive function, each of which compute the sum of the first n terms of the series.

In a file named recursive_series.py, write a program that calculates the sum of the first n terms of the following series:

$$ {1 \over 2^1} + {1 \over 2^2} + {1 \over 2^3} + {1 \over 2^4} + \ldots $$

Your main program should prompt the user to enter a positive int value for n, call both the iterative and the recursive version of the function to compute this summation, and print out the return value for both. For example:

$ python recursive_series.py

This program computes the first n terms of the series
1/2 + 1/(2 squared) + 1/(2 cubed) + ...
using both an iterative and a recursive function.

Enter a value for n: 43adb
Hey 43adb isn't a positive int value...try again
Enter a value for n: 10

The sum of the first 10 terms is 0.999023 (iterative) 0.999023 (recursive)

Write a program set_max.py that implements a recursive function recursiveSetMax that changes all values in a list of ints that are larger than a given max value to the max value. The function should return the number of values changed in the list.

Your program should:

1. Prompt the user to enter the name of a file
2. Open and read in integer values from the file into a list of integers.
3. Print out the total number of items in the list.
4. Print out the list, using nice formatting to print some number of values per line in a way that is easy to read.
5. Prompt the user to enter a maximum value max (and check that the input value is actually an integer)
6. Call your recursiveSetMax function to set all values in the list that are greater than max to max.
7. Print out the total number of values changed to max.
8. Print out the list, using nice formatting.

Requirements

1. recursiveSetMax must use recursion to modify the list of values. It should return the total number of list values that were changed to max in the list. Think about what parameters this function needs.
2. The recursion should be done in place on the list. This means that you should not be creating new copies of the full or partial list. Your program should create the list one time, and then recurse on bucket index values.

   The function prototype for recursiveSetMax might look like:

   def recursiveSetMax(L, bucket_index, max):
   

   Where L is the list of values, max is the max value, and bucket_index is the index of the bucket value to consider at each recursive step.

3. In addition to the recursive recursiveSetMax function, you should apply Top-Down Design to determine other places where functions should be used in your program.
4. With the starting point code is an example input file lab10input.txt, that you can use. You should also create your own input files for testing your program. In vim, open a file input.txt and just enter a bunch of int values, one per line. They try out your program on your file. Create a few different test files, of different sizes, and with different values to test correctness of different cases.
   The file format should be one integer value per line. For example, here are the contents of a file I created named small.txt that contains 3 integer values:

   % cat small.txt
     10
     40
     77
   

5. You program should check for and handle bad input values for the max value. You DO NOT need to handle the case if the infile name is wrong (it is okay if your program crashes if the user enters a bad input file name).

Sample Output

$ python set_max.py
Enter the name of the file: lab10input.txt
16 values were read in from the file
list before:
   10      40      77       8      23       8      29      44      30      31
   20      -3      14      33      90       6
Enter a value for max: 24
8 out of 16 values were set to 24
list after:
   10      24      24       8      23       8      24      24      24      24
   20      -3      14      24      24       6


$ python set_max.py
Enter the name of the file: lab10input.txt
16 values were read in from the file
list before:
   10      40      77       8      23       8      29      44      30      31
   20      -3      14      33      90       6
Enter a value for max: 8sa
Hey 8sa isn't an int value...try again
Enter a value for max: -2
15 out of 16 values were set to -2
list after:
   -2      -2      -2      -2      -2      -2      -2      -2      -2      -2
   -2      -3      -2      -2      -2      -2

Some Tips

• Remeber you can directly compare string values using relational operators:

    s = "hello"
    if(s[0] == 'h'):
       print("the first letter in s is h")
  

  The isdigit method of the string class may also be useful.
  See the str and list methods for more help with strings.
• See the File I/O reference.

Write a program, called fractal_shapes.py, that recursively draws a pattern of shapes to the graphics window. Your program will:

1. prompt the user to enter a depth value for your recursive pattern.
2. create a square graphics window.
3. call a recursive draw_shapes function to recursively draw a fractal pattern of shapes for the given depth of recursion. You should use some different colors for the shapes in different locations (e.g. note that in my example, I'm using the same color (white) for the recursive upper-right shape). Also you are free to pick the shape or shapes you want to draw.
4. wait for the user to click in the graphics window to exit.

For example, here are the results of two runs of a working program, the first is for a level 1 pattern drawing circles, the second for a level 3 pattern drawing squares (using just one shape, either squares or circles or something more interesting, is fine):

The above pattern is based on recursively splitting the square graphics window into 9 even sub-squares. The center square will be filled with a shape of the passed color. The other 8 should be recursively filled with shapes of dimension one third of the current shape's size

Your recursive draw_shapes function should do the following:

1. draw a shape of the given size and color, centered in the given portion of the graphics window
2. decide if it should recur or not, based on the current depth
3. if it should recur, think of the current drawing space as divided into 9 equal sub-squares, and make eight recursive calls to draw smaller shapes (at the next smallest depth level) to the eight sub-squares (above right, above, above left, below right, below, below left).
4. Each of the eight recursive calls should draw a shape of a different color. Use colorPicker to find colors in the graphics library.

Here is an animation showing one example of the recursive pattern:

The function prototype for your draw_shapes function might look like this (it is fine if yours is different from this):

def draw_shapes(win, depth, size, x, y, color):

Where depth is the recursive depth, size is the size of the center shape at this level of recursion, x, y are the coordinates of the center point in the current portion of the window, and color is the color to draw the center shape.

You are welcome to design a recursive function that uses a different set of parameters than this example. Yours may differ depending on what your function needs to do to draw at each recursive step, and how you want to pass that information to the recursive calls. Think about what the function needs to determine if it needs to make further recursive calls or stop the recursion, and what it needs to know to draw a shape to the graphics window at the appropriate position of the appropriate size of the appropriate color.

Some Tips

• Start with an simple shape to draw (a circle or square), and change it to something more interesting if you have time.
• Worry about picking colors after you figure out the recursion pattern. You can start off by drawing all shapes the same color, like blue.
• Work on the base case first. Next, figure out how to match the examples at level 1 and level 3. You can first try recursively drawing just one of the eight smaller square's contents, for example the one to the right (see below). Once you have that working, then add in code to recursively draw each of the eight sub-squares.
• The graphics library.
• the random library

This is not part of the regular lab assignment; only try these if you have completed the regular lab assignment problems.

There are a lot of fractal patterns you can "easily" draw using recursive functions. Try coming up with your own recursive fractal patterns. Here are a few links to some information about fractals (there are lots more on-line if you search around):

• Fractals in nature
• Recursion in Nature, Mathematics and Art
• Lindenmayer System recursive rules that generate fractal patterns
• Trippy "fractal zoom" videos on youtube

And here are two pretty challenging patterns you could try out: extra challenging fractal patterns

Once you are confident that your programs work, fill out the questionnaire in README-10.txt.

Then run handin21 a final time to make sure we have access to the most recent versions of the files required for this lab.