CSCI 150: Lab 8

Powers

Understand:

n raised to the k is the product of k n's. 2 raised to the 3 is 8. 3 raised to the 2 is 9. What is 5 raised to the 4? Which is larger, 2 raised to the 100 or 100 raised to the 2?

Design:

Since we're trying to solve this recursively, we need to think about how exponentiation (raising one number to the power of another) can be described recursively. That is, we want to try to describe n raised to the k in terms of a smaller version of that same problem. The key insight is that [n raised to the k] can be described as simply n times [n raised to the (k-1)]. Note that we've now defined exponentiation in terms of a simple operation (a single multiplication). That's our recurrence. All that remains is to specify a base case so that our recursion know to stop at some point. We could define n raised to the 1 as n, but a better solution (in that it'll work for 0 as well) is to define n raised to the 0 as 1. Question: would it have made sense to define n raised to the k in terms of (n-1) raised to the k?

Implement, Test, and Maintain:

You now have the necessary pieces to write a recursive function pow(n,k). Test that it works on a range of cases. Be sure to add comments to your code once you're done if you haven't been doing so along the way.

Sum of Squares

Understand:

The first few squares are 1, 4, 9, 16, 25, 36, etc. So the sum of the first one of these is 1, the sum of the first two is 5, and the sum of the first three is 14. What are the next two sums of squares?

Design:

As with the previous problem, the key is to figure out how to describe the sum of the first x squares in terms of a few simpler operations and the answer to a smaller instance of the sum-of-squares problem. If you knew the value of sum of the first n-1 squares, what would you need to do to compute the sum of the first n squares? Write that down as a recurrence. Now what makes sense as a base case?

Implement, Test, and Maintain:

Write a recursive function sps(n). Test that it works on a range of cases. Be sure to comment your code once you're done if you haven't been doing so along the way.

Choose

Understand:

The value [n choose k] represents the number of ways of picking k distinct objects out of a set of n distinct objects. For example, suppose we have four people; Alice (A), Balthazar (B), Charlize (C) and Douglass (D). How many ways could you pick a pair of them? Six: AB, AC, AD, BC, BD and CD. We've just argued that 4 choose 2 is 6. Just so you have some more test data, 5 choose 2 and 5 choose 3 are both 10 (coincidence?), and 6 choose 3 is 20. Compute 6 choose 2 on your own.

Design:

The standard definition of n choose k involves a few factorials. However, there is also a recursive definition that can be very handy. This recursive definition isn't as straight-forward as the previous two, so we'll state it here and then walk through the reasoning behind it:

• If k > n then [n choose k] is 0; you can't pick k different things if you have fewer than k choices available.
  
  
• If k = n then [n choose k] is 1; your only option is to take everything.
  
  
• If k = 0 then [n choose k] is also 1; your only option is to take nothing.
  
  
• In all other cases, [n choose k] is [(n-1) choose k] plus [(n-1) choose (k-1)].

This last case is the heart of the recursion -- the rest are just base cases. You don't really need to understand why this works to write a recursive function for this operation; you can just use this definition and magically you'll be computing the correct values. However, the explanation is actually pretty cool (and you'll be seeing more of these types of arguments if you take Discrete Math).

For those interested in why this recurrance works: suppose we trying to think of how many sets of k objects can be selected from n objects. We can break these sets down in two groups: the the sets that don't include object 1, and the sets that do. How many sets of size k are there that don't include object 1? Well, we'd need to pick k objects out of the remaining n-1. Given our definition of choose, the number of those is just (n-1) choose k. And how many sets of size k are there that do include object 1? Such sets would have to use (k-1) out of the remaining (n-1) objects, so there are (n-1) choose (k-1) of these. If we sum these two terms together, we've counted all the sets we were considering.

Implement, Test, and Maintain:

Write a recursive function choose(n,k). Test that it works on a range of cases. Be sure to comment your code once you're done if you haven't been doing so along the way.

Example Output

  % python3 recnum.py

  Welcome to my Amazing Recursive Calculator!

  Please enter a non-negative integer x: 6
  Please enter a non-negative integer k: 3

  6 raised to the power of 3 is 216.
  The sum of the first 6 squares is 91.
  6 choose 3 is 20.
                

Backwards

Understand:

The string "alligator" backwards is "rotagilla". The string "step on no pets" backwards is "step on no pets" (woah...)

Design:

Generating s backwards recursively can be done as follows: if the length of s is 0, you're done. Easy peasy. Otherwise, use recursion to reverse all but the first character of s, then concatenate the first character of s to the end of that result. Alternatively, take the last letter of s, and then concatentate to that the result of recursively reversing the remainder of s (all but the last character).

Implement, Test, and Maintain:

Write a recursive function rev(s). You'll probably want to use the method len(s) to find the length of s string (or check for an empty string s == ""), and slicing operations to get at substrings. Comment your code once you're done if you haven't been doing so along the way.

Palindrome

Understand:

As you probably know, a palindrome is any string that reads the same forward as backwards. "UFO tofu" is one such example. "No, sir, away! A papaya war is on!" is not only a palindrome but also an unexpectedly ominous declaration.

Design:

We can recursively check whether s is a palindrome as follows; if s has length 0 or 1, then it is a palindrome. Otherwise, it is only a palindrome if the first character is the same as the last character and the substring with those two characters removed is also a palindrome.

Implement, Test, and Maintain:

Write a recursive function pal(s) that returns true if s is a palindrome. You may assume your input is "clean," i.e. you can assume that all spaces and other non-letters have been removed, and all characters are lowercase. So the second example given above would actually have been input as "nosirawayapapayawarison". Make sure your code is commented.

Please note: your solution for pal(s) should not call rev(s)

Subsequence

Understand:

"toga" is a subsequence of "strongbad" since the characters 't', 'o', 'g' and 'a' all appear in the latter in that order. Note that these letters don't need to appear contiguously. "goat" is not a subsequence of "strongbad" -- all requisite letters are there, but they don't appear in a consistent order. Which of "songa" and "ratdog" are subsequences of "strongbad"?

Design:

A recursive definition of whether t is a subsequence of s would be as follows:

• If t has length 0, then t is a subsequence of s


• If t is longer than s, then t is not a subsequence of s


• If the first character of both strings match, then:
  • t is a subsequence of s whenever t with the first letter removed is a subsequence of s with the first letter removed
  • t is not a subsequence of s whenever t with the first letter removed is not a subsequence of s with the first letter removed
• If the first character of both strings don't match, then:
  • t is a subsequence of s whenever t is a subsequence of s with the first letter removed
  • t is not a subsequence of s whenever t is not a subsequence of s with the first letter removed

Try a few examples to convince yourself that this definition makes sense.

Implement, Test, and Maintain:

Write a recursive function subseq(s,t) that returns true if t is a subsequence of s. Check it on the above exmaples, and make sure your code is commented.

Example Output

% python3 recstr.py

 Welcome to my Incredible Recursive string Thing!
 
 Please enter a string s: racecar
 Please enter a string t: rare
 
 The string "racecar" backwards is "racecar".
 The string "racecar" is a palindrome.
 The string "rare" is not a subsequence of "racecar".
 
 % python3 recstr.py

 Welcome to my Incredible Recursive string Thing!
 
 Please enter a string s: strongbad
 Please enter a string t: toga
 
 The string "strongbad" backwards is "dabgnorts".
 The string "strongbad" is not is a palindrome.
 The string "toga" is a subsequence of "strongbad".
                

Example Fractal: Bubbles

Understanding:

Consider the following sequence of fractal patterns (which are only an example -- you do not need to implement this in your recpic.py):

Bubbles with recursive depths 1 through 6 respectively.

Each pattern is built entirely out of filled in circles. The pattern can be described recursively as a single filled circle, with four patterns of one lesser depth and half the size, offset to the northwest, northeast, southwest and southeast.

Design:

For this fractal, the repeating pattern is drawing a circle, then repeating four times around the just-drawn circle. This implies that the design of the recursion is to draw a circle at a given center (x,y) and with a given radius r, then make four recursive calls with:

• new centers (one recursive call for each of the northwest, northeast, southwest, and southeast)
• half the radius of the just-drawn circle
• one less depth (so we count down to depth == 0)

This process continues depth times. So a simple base case is to check the value of depth: if it is greater than 0, keep drawing, else stop (by returning from the function).

Implement, Test, and Maintain:

The code used to implement this fractal is provided for you in bubbles.py in your repl.it projects. Please feel free to use this example to help you with the following fractals.

Carpet

Understanding:

The carpet pattern, also known as Sierpinski's carpet, is built entirely out of filled in squares. The pattern can be described recursively as a single filled square (whose sides have length one third the size of the length of the area containing the square), with eight patterns of one lesser depth and one third the size, offset to the north, northeast, east, southeast, south, southwest, west, and northwest. See the examples below.

Carpet with recursive depths 1 through 6 respectively.

Design:

At this point we're ready to define our recurrence more precisely. When designing recursive algorithms, it's critical that you think about how your recurrence works not just at the top level, but also at subsequent levels. It's easy to define a recurrence that does what you intend on the first step, or even the first few steps, but then breaks down on deeper interations.

In this case, it's tempting to simply say that the largest square is drawn centered halfway from top to bottom and side to side, and the next recursive calls are made centered at 1/6 width by 1/6 height (for the northwest repeat), 1/2 width and 1/6 height (for the north repeat), etc. Unfortunately, that description doesn't lend itself to a useful recurrence. What happens now when the lower-right subproblem is solved recursively?

To deal with this, we need a more general description. In particular, try to figure out what it would mean to draw this pattern with depth d, centered at position (x,y), with a size of r (just like our Bubbles fractal example). Note that you shouldn't assume x and y correspond to the middle of the canvas, because in many recursive calls they won't. Similarly, don't assume that r is at all related to x or y. It might be helpful to work through the details of this recurrance on paper.

Implement, Test, and Maintain:

Now create a function called carpet in your recpic.py that generates this pattern. You'll need to decide upon a few things. In particular, what parameters will this function take in? And what will the initial call to this function look like? If something goes wrong, find the smallest depth at which things break down and trace through what your program is doing. You may find you've implemented your design incorrectly, or you may need to revisit the algorithm itself. Along the way, make sure to comment your code.

Gasket

Understanding:

The gasket pattern, also known as Sierpinski's triangle or Sierpinski's gasket, is built out of trianges. The depth 1 figure includes a single triangle, with lower corners at the lower corners of the pane, and the upper corner centered at the top middle. Each subsequent depth replaces the existing triangle with 3 triangles, each of half the width and half the height as shown below.

Gasket with recursive depths 1 through 6 respectively.

Design:

There are two distinct recurrences we could use to create this pattern, depending on how we think about the forms. Option 1: draw the carpet (the blue parts). In this case, notice that for a given pattern, all the triangles are of the same size. Thus the creation of triangles only happens as a base case in our recurrence. Option 2: draw the holes (the yellow parts) on top of a single blue triangle. In this case, a recursive call at any depth involves the creation of a triangle (in addition to additional recursive calls, so long as the depth is positive).

Which approach you take is up to you. Either way, you'll need to write out a recursive description of the pattern before you begin coding. The key thing to think about is how a given recursive call in turns makes its own recursive calls. Think about how you'd describe making a the gasket pattern if the outer triangle has corners at positions A, B and C.

Implement, Test, and Maintain:

Now create a function called gasket that generates this pattern. What parameters does it require? You'll want to make use of the drawPolygonFill() function from the picture module, which takes in a list (indicated by brackets), containing any number of points, represented as pairs of integers (themselves in parentheses as tuples). So

canvas.drawPolygonFill([(a, b), (c, d), (e, f)])

would draw a filled in polygon on canvas whose first vertex was (a,b), etc. Test and comment as usual.

Snowflake

Understanding:

Consider the fractal patterns below.

Snowflake with recursive depths 1 through 6 respectively.

To understand the snowflake design, let's think about drawing only one of the three sides of the snowflake (for example, focus on the bottom side of the snowflake below). When depth == 1, the side is just a line. For higher depths, the side is made up of several lines. What does this hint about the base case of the recursion?

For depth == 2, the side no longer a single line, but four particular lines -- each with one third the length of the line at depth == 1 and some angles between those lines. Altogether, these four lines form a line along the side, two lines forming a triangle, and a final line along the side. For depth == 3, each line in depth == 2 is replaced with the same pattern, just as the line from depth == 1 was replaced to create depth == 2. This hints that the recursion involves drawing four lines with angle rotations between them.

Once we understand the recursion for each side of the snowflake, then the only thing left to do is to draw all three sides of the fractal. Unlike bubbles, carpet, and gasket, the recursive function doesn't draw the entire snowflake, but only one side. So instead we need three total calls to the snowflake function in our main function (one call for each side).

Implement, Test, and Maintain:

Create a function called snowflake that generates this pattern. What parameters does it require? Test and comment as usual. Below are some picture functions you may find useful.

 rotate(theta)          # rotate pen theta degrees clockwise 
 drawForward(d)         # draw a length-d line from the current position in the current direction.
 setPosition(x,y)       # move the pen to position (x,y)