Lab 5 Recursion, With A Twist

Purpose: The purpose of this lab is to get some more practice with recursive functions, specifically with recursion over natural numbers.

Recursion over natural numbers

A recursive data structure we use very often in programming is the collection of natural numbers:

; A Nat, or natural number, is one of:

;  - 0

;  - (add1 Nat)

;

; The predicate for 0 is: zero?

;

; The predicate for (add1 n): positive?

; The selector for (add1 n): sub1

Sample Problem What is the template for Nat?

Sample Problem Think about the relationship between the following functions and constants:

empty – 0

empty? – zero?

cons? – positive?

cons – add1

rest – sub1

first – ???

Does anything relate to the list function first? If so, what? If not, why not?

In the following exercises we will redefine some built-in arithmetic functions to get practice writing recursive functions over Nats, so don’t simply reuse the built-in functions.

Exercise 1 Design a function nat-even? that returns true if the given Nat is even. Use only sub1, zero?, nat-even? itself, and not. Do not use even?, odd?, modulo, etc. Also, calling sub1 twice in a row does not follow the template and is therefore wrong.

Exercise 2 Design a function double that doubles the given Nat. Again, you may only use add1 and sub1, and of course double.

Exercise 3 Design a function down-from that takes a Nat n and returns the list of Nats counting down from n. For example,

> (down-from 3)

(list 3 2 1 0)

Exercise 5 Design a function nat+ that takes two Nats and computes their sum. Use recursion instead of the built-in + function.

Exercise 6 Design a function nat* that takes two Nats and computes their product. Again, use recursion instead of the built-in * function, though consider making use of nat+.

Exercise 7 Design a function nat-factorial that takes a Nat and computes the factorial of that number. The factorial of a natural number n is given by the product of all natural numbers less than or equal to n (excluding zero). Use your nat* function.

Exercise 8 Challenge: Design a function nat-square that squares the given Nat, but don’t use nat*! You may use add1, sub1, double, nat+, and of course nat-square.

Concentric rings in the World

Let’s build a world where clicking our mouse results in ever-growing rings to be drawn. Here is some basic setup:

(require 2htdp/image)

(require 2htdp/universe)

(define width 400)

(define height 400)

(define-struct ring (size center))

; A Ring is a (make-ring Nat Posn)

; where size is the ring's radius

;       center is the x,y coordinate of the ring's center

(define ring1 (make-ring 0

(make-posn 50 50)))

(define ring2 (make-ring (add1 0)

(make-posn 150 0)))

(define ring3 (make-ring (add1 (add1 0))

(make-posn 0 75)))

; A World is a [Listof Ring]

Exercise 9 Design a grow-ring function that increases a Ring’s size by one.

Exercise 10 Design a draw-ring function that takes a Nat r as input and simply returns an image of a circle with radius r. We’ll make this more interesting later.

Exercise 11 Design a place-ring function that draws a Ring into the given scene at the Ring’s location. Use draw-ring here so that we can modify it later to change the animation.

Exercise 13 Design a mouse function that, when the mouse is clicked, adds a 0-size Ring to the World at the location of the click.

Exercise 14 Design a tick function that grows all the Rings in the World using grow-ring.

Put it all together and see what you get:

(big-bang empty

[on-tick tick 0.25]

[to-draw draw]

[on-mouse mouse])

Exercise 15 Now let’s redesign the draw-ring : Nat -> Image function. Instead of making an image of a solid circle, let’s make concentric rings of many circles. We can achieve this by overlaying many circles of increasing sizes:

(overlay ) =

Natural number recursion should serve you well here...

A Little Puzzle

Exercise 16 Design a function foo that given a Nat will only output the same natural number if the inputs are equal. In other words, (foo n) should only equal (foo m) if n and m are equal.

Exercise 17 Design a function foo2 that given two Nats will only output the same natural number if the inputs are equal. In other words, (foo2 a b) should only equal (foo2 x y) if a equals x and b equals y. Does this tell you anything about how many natural numbers there are vs. how many pairs of natural numbers there are? Hint: expt.

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.