Due Saturday Night, April 15 before 11:59pm

Worsheet due in class Thurs April 13 or Friday April 14

Worsheet due in class Thurs April 13 or Friday April 14

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.

Goals

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

Worksheet

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

1. Recursive and Iterative Sum of Series Functions

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)

2. Recursive List: Set to Max Function

Write a program Your program should:

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

**Requirements**

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

- 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

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

3. Fractal Pattern

Write a program, called - prompt the user to enter a depth value for your recursive pattern.
- create a square graphics window.
- 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.
- wait for the user to click in the graphics window to exit.

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:

- draw a shape of the given size and color, centered in the given portion of the graphics window
- decide if it should recur or not, based on the current depth
- 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).
- 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

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.

- 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

Extra Challenge: More fun with Fractals

This is not part of the regular lab assignment; 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

Answer the Questionnaire; Run `handin21`

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.