Inlab: Composing Functions (and Recursion)

In the previous inlab exercise we examined a computation that called for the definition and composition of multiple functions. In such a computation a function makes use of one or more other functions, which in turn might use additional functions to do their work (and so forth).

In Racket, the definition of a function named foo might look something like this:

(define (foo i1 i2 i3 i4)
  (fn-a i1
        (fn-b i2)
        (fn-c i3 (fn-d i4))))

where fn-a, fn-b, fn-c and fn-d are functions used in foo's definition. In this example, fn-a is composed with fn-b and fn-c, and fn-c is composed with fn-d; i.e., the results of fn-b and fn-c are used as input to fn-a, and the result of fn-d is used as input to fn-c.

In this inlab we'll continue to explore computations that require us to define multiple functions and layer them together. We'll take another intriguing step forward, however, and consider functions that are defined in terms of themselves, a technique known as recursion.

Exercise 1: Newton's method for computing square roots

The first computation we'll examine is a technique for approximating square roots known as Newton's method. Although Racket provides a function named sqrt that does this for us, it doesn't hurt to consider how we might go about defining the function ourself!

An example is a good starting point, so let's look at how Newton's method would be used to compute the square root of 3.

The method requires that we start with a guess -- so we'll just arbitrarily pick 1.5 (the better the guess the quicker you'll find the answer, but you'll usually get there no matter what you pick).

First let's check to see if we just happened to guess the actual square root of 3:

1.5 × 1.5 = 2.25

... so we clearly don't have the square root of 3 yet.

So we have to improve our guess. Newton's method says that when we have a guess g for the square root of a number x, we can come up with a better guess by computing the average of g and x/g.

In our case, that means computing the average between 1.5 and 3/1.5:

Now let's check our new guess:

1.75 × 1.75 = 3.0625

Closer, but we're not satisfied yet.

Let's improve our guess again:

Note that we're rounding to 5 significant digits. Let's check our new guess:

1.73214 × 1.73214 = 3.00030

Not bad! Let's try one more time. Improve our guess:

And check again:

1.73205 × 1.73205 = 3.00000

We can keep going until we hit an arbitrary level of precision, but we'll stop for now.

Summary of the method

Newton's method for approximation (newton), then, takes as input a guess g and number x, and operates as follows:

In Racket

You are to implement the following four functions:

Exercise 2: Fractal art

Fractal art is a fascinating (and mostly digital) artform wherein the object being depicted contains self-similarity --- i.e., the structure of the object at a given level is replicated at any other level (say, as one "zooms" in and out of the artwork).

The Barnsley Fern is a well known example of fractal art (courtesy Wikimedia Commons):

barnsley

We're going to try our own hands at generating fractal art for this exercise. It's easier than you might think!

Version 1

Start by writing a function called fractal-lvl-1 that takes as input an image 'img' and draws the original image beneath two half-scale versions of the image rotated, respectively, 35 and -35 degrees.

Given img= as input, fractal-lvl-1 would return . You should find the above, beside, rotate, and scale functions useful (all described in the image library documentation).

Version 2

Next, write a function called fractal-lvl-2 that takes as input an image 'img' and draws the original image beneath the images obtained by applying fractal-lvl-1 to the half-scaled image two separate times, which are then rotated, respectively, 35 and -35 degrees.

Given img= as input, fractal-lvl-2 would return .

Version 3

Next, write a function called fractal-lvl-3 that takes as input an image 'img' and draws the original image beneath the images obtained by applying fractal-lvl-2 to the half-scaled image two separate times, which are then rotated, respectively, 35 and -35 degrees.

Given img= as input, fractal-lvl-3 would return .

Onwards!

We could continue and write fractal-lvl-4, but you've probably noticed at this point that the code pretty much looks the same each time around, and we don't want to bore you.

Instead, we're going to exploit the fact that each level of the fractal is drawn in exactly the same way and implement a function called fractal which takes two arguments, an image 'img' and a number 'lvl', which works as follows:

Given img= and lvl=3 as input, fractal would return .

Congratulations!

If you've gotten here, then you just implemented a lean, mean, fractal-drawing machine. Play with it. Try giving it different images and values of lvl as input and see what happens. Try experimenting with the values used for rotation and scale in the definition of fractal. Enjoy, and let us know if you come up with anything interesting! (Oh, and don't worry if you can't explain how it works completely -- this is a preview of things to come!)