Lab 4 Recursion

Purpose: The purpose of this lab is to give you some hands-on experience with self-referential data.

Textbook references: Chapter 9: Designing with Self-Referential Data Definitions

Pet Rock

Goals: Practice processing self-referential data.

Matt is very protective of his pet rock, "King Paimon". He carefully guards it by placing it in layers of bags of varying colors, each with their own size.

Starter Code: The following data definition encapsulates this psychologically dubious scenario.

Exercise (Reviewed) 2 ** Design a function which gives the size of the largest bag in a PRS (where the pet rock itself has size 0).

Exercise 3 ** Design a function which determines if a bag of a particular color is in a PRS.

Exercise 4 ** Design a function which takes a PRS and increases all of its bag sizes by 1.

Exercise 5 ** Design a function which takes a PRS and a number and discards all bags bigger than that size.

Exercise 6 *** Design the function well-stored? which ensures a PRS is comprised of successively smaller contents. Hint: break the problem down into English. Doing so shall hopefully show that a previously defined function will help.

Expanding Conciousness

Goals: Learn to look at numbers and recursion in a new way.

Starter Code: Below is a data definition which shows how natural numbers can be built up recursively.

; A Nat is one of:

; - 0

; - (add1 Nat)

(define NAT-0 0)

(define NAT-1 (add1 NAT-0))

(define NAT-2 (add1 NAT-1))

Exercise 7 ** Design the template for Nats. The predicates to tell the two clauses apart are zero? and positive?, respectively. The selector for an (add1 Nat) is sub1.

Exercise 8 ** Design the function double which doubles a Nat. As we are following our Nat template, you may only use the functions mentioned above, cond, and double (no + or *).

Exercise 9 *** Design the function even?/nat which deterimes if a Nat is even. You may only use the functions mentioned above, as well as cond, not, and even?/nat. Your code must follow the template exactly, and therefore two successive calls to sub1 is forbidden.

Exercise 10 ** Design the function nat+ which sums two Nats. You may only use the functions mentioned above, as well as cond and nat+ (no +).

Exercise 11 ** Design the function nat* which multiplies two Nats. You may only use the functions mentioned above, as well as cond, nat+, and nat* (no *).

Exercise 12 ** Design the function factorial which computes the factorial of a natural number. You may only used the functions mentioned above, cond, nat*, and factorial.

Before You Go...

If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance.

Spinning In Circles

Goals: Use the power of recursion to make exciting animations.

Exercise 13 * Design the function draw-circle which given a Nat draws a circle of that size radius. The color of the circle should be "red" if the input is even or "black" if the input is odd (or whatever two colors suit your fancy).

Exercise 14 ** Design the function draw-circles which given a Nat uses draw-circle to overlay concentric circles on top of each other (0 should produce empty-image).

Exercise 15 * Design the function draw-scene which given a Nat draws concentric circles on a 200x200 empty-scene. Use modulo to keep the radius below 100.

Exercise 16 * animate your scene.

Exercise 17 *** Modify your draw-scene function to to make the circle grow and shrink in a loop instead of grow and suddenly disappear and grow again. Hint: quotient, even?.