## Description

Objectives

• Work with recursive functions

• Learn to work with others

Your code should be saved as file lab3.rkt, and submitted to Mimir. Be careful with the names,

and good luck!

Activities

1. Young Jeanie knows she has two parents, four grandparents, eight great grandparents, and so

on.

(a) Write a recursive function (num-in-gen n) to compute the number of Jeanie’s ancestors

in the n

th previous generation without using the expt function. The number of ancestors

in each generation back produces a sequence that may look familiar:

2, 4, 8, 16, . . .

For each generation back, there are twice the number of ancestors than in the previous

generation back. That is, an = 2an−1. Of course, Jeanie knows she has two ancestors, her

parents, one generation back.

(b) Write a recursive function to compute Jeanie’s total number of ancestors if we go back n

generations. Specifically, (num-ancestors n) should return:

2 + 4 + 8 + · · · + an

Use your function in part (a) as a “helper” function in the definition of (num-ancestors

n)1

.

2. Perhaps you remember learning at some point that 22

7

is an approximation for π, which is an

irrational number. In fact, in number theory, there is a field of study named Diophantine approximation, which deals with rational approximation of irrational numbers. The Pell numbers

are an infinite sequence of integers which correspond to the denominators of the closest rational

approximations of √

2. The Pell numbers are defined by the following recurrence relation (which

looks very similar to the Fibonacci sequence):

Pn =

0 if n = 0

1 if n = 1

2Pn−1 + Pn−2 otherwise

1Of course, we can use the closed-form solution for the geometric progression to compute num-ancestors

(ancestors(n) = 2n+1 − 2) but that doesn’t give us any experience with recursive functions. However, this is a

useful fact we can use when testing our functions to ensure they are correct.

1 CSE 1729

(a) Use this recurrence relation to write a recursive function, pell-num, which takes one parameter, n, and returns the n

th Pell number.

(b) The numerator for the rational approximation of √

2 corresponding to a particular Pell

number is half of the corresponding number in the sequence referred to as the companion

Pell numbers (or Pell-Lucas numbers). The companion Pell numbers are defined by the

recurrence relation:

Qn =

2 if n = 0

2 if n = 1

2Qn−1 + Qn−2 otherwise

Use this recurrence relation to write a function, named comp-pell-num, which returns the

n

th companion Pell number.

(c) Finally write a function (sqrt-2-approx n) that uses the Pell number and companion

Pell number functions to compute the n

th approximation for √

2. Use your new function

to compute the approximation for √

2 for the sixth Pell and companion Pell numbers.

3. Binary exponentiation Consider the following function, (power base exp), that raises a

number (base) to a power (exp):

( define ( power base exp )

( cond ((= exp 0) 1)

( else

(* base ( power base (- exp 1))))))

(a) There are more efficient means of exponentiation. Design a Scheme function fastexp which

calculates b

e

for any integer e ≥ 0 by the rule:

b

e =

1 if e = 0,

(b

e

2 )

2

if e is even,

b ∗ (b

e−1

2 )

2

if e is odd.

You may find it useful to define square as a separate function for use inside your fastexp

function. You may also want to try the even? and odd? functions defined in Scheme.

(b) Show that the fastexp function is indeed faster than the power function by comparing the

number of multiplications that must be done for some exponent e in both functions. (You

can assume the exponent e is of the form 2

k

.)

4. It is an interesting fact the the square-root of any number may be expressed as a continued

fraction. For example,

√

x = 1 +

x − 1

2 +

x − 1

2 +

x − 1

.

.

.

2 CSE 1729

(a) We can rewrite the above equation as

√

x − 1 =

x − 1

2 +

x − 1

2 +

x − 1

.

.

.

and let its right-hand-side be the continued fraction we want, then the following recurrence

relation describes our approximation:

cont-frac(k, x) =

0 if k = 0,

x−1

2+cont-frac(k−1,x)

otherwise

Given this recurrence, write a function (cont-frac k x) that computes it.

(b) Next, write a Scheme function called new-sqrt which takes two formal parameters x and

n, where x is the number we wish to find the square root of and n is the depth of the

fraction computed (that is, the k in the cont-frac function). Demonstrate that for large

n, new-sqrt is very close to the builtin sqrt function. Use cont-frac (as you defined

above) as a helper function, but do not define it within new-sqrt.

3 CSE 1729