HW 6: Recursive Procedures and Strings

Due: Tuesday, November 1 by 10:30pm

Summary: In this assignment, you will use recursion techniques to solve several problems regarding strings and drawings.

Purposes: To practice using strings and tail recursion to solve various problems.

Collaboration: You must work with your assigned partners on this assignment. You must collaborate on every problem - do not break up the work so that one person works on problem 1, another on problem 2, and another on problem 3. (The “don’t break up the work” policy applies to every assignment. This note is just a reminder.) You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment.

Submitting: Send your answer to csc151-01-grader@grinnell.edu. The title of your email should have the form [CSC 151.01] Assignment 6 and should contain your answers to all parts of the assignment. I prefer that you put your answers in the body of the message, rather than as an attachment.

So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.

Assignment

Problem 1: Filtering Lists

Topics: tail recursion

Below is a procedure that determines the type of its parameter.

;;; Procedure:
;;;   get-type
;;; Parameters:
;;;   x, can be any type
;;; Purpose:
;;;   Returns the type of object x is 
;;; Produces:
;;;   type, a symbol
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   type  = 'number if x is a number
;;;   type  = 'symbol if x is a symbol
;;;   type  = 'list if x is a list
;;;   type  = 'pair if x is a pair (and not a list)
;;;   type  = 'string if x is a string
;;;   type  = 'other otherwise
(define get-type
  (lambda (x)
    (cond [(number? x) 'number]
          [(symbol? x) 'symbol]
          [(list? x) 'list]
          [(pair? x) 'pair]
          [(string? x) 'string]
          [else 'other])))

Using the given procedure above, write and document a tail-recursive procedure (filter-by-type lst types) that takes two parameters, a list of elements lst and a list of types types, and returns a copy of lst that only contains elements that are of one of the types in types. This procedure should also maintain the original order of the elements.

> (filter-by-type (list 5 "foo" 'bar) (list 'symbol 'number))
'(5 bar)

> (filter-by-type (list "hello" 'world (list 1 2 3)) (list 'list))
'((1 2 3))

Problem 2: Palindromes

Topics: tail recursion, strings and characters

A string is called a palindrome if reversing the characters of the string results in the same string. A few examples of palindromes are "radar", "civic", and "aabaa". Write and document a tail recursive procedure (palindrome? str) that checks to see if the string str is a palindrome. You may NOT use any string compare procedures for this problem (e.g. string=?, string<=?, etc.).

> (palindrome? "hello")
#f

> (palindrome? "civic")
#t

Problem 3: Drawing Self-Similar Fractals

Topics: recursion

A self-similar fractal can be constructed by iteratively applying the same pattern to an image. One famous example of a self-similar fractal is the Sierpinski carpet which is generated by the pattern below.

The Sierpinski carpet is produced iteratively using the following process.

1. Start with a drawing of a single square
2. Replace every non-empty square in the current drawing with the generating pattern
3. Repeat step 2 indefinitely or until a desirable level of detail is achieved

Below are the first four iterations of the Sierpinski carpet.

Write a procedure (sierpinski-carpet n) that returns a drawing of the nth iteration of the Sierpinksi carpet. Each square in the drawing must be a unit, black, square, and the upper left corner of the drawing must begin at (0,0).

> (image-show
   (drawing->image
    (scale-drawing 10 (sierpinski-carpet 3))
    90 90))

> (image-show
   (drawing->image
    (scale-drawing 10 (sierpinski-carpet 4))
    270 270))

Acknowledgments

The pattern image and the first four iterations image from this problem are from Paul Bourke’s web page on self-similar fractals.