scheme代写 CSE1729 Introduction to Programming Laboratory Assignment 4

Objectives

• Workwith“tailrecursion”
• Workwithhigherorderfunctions

Activities

1. RecallfromProblemSet3:TheLucasnumbersareasequenceofintegers,namedafterÉdouardLucas,which are closely related to the Fibonacci sequence. In fact, they are defined in very much the same way:

2 Ln= 1

Ln−1 + Ln−2
(a) Ask your SCHEME interpreter to compute L30, then L35, then L40. What would you suspect to happen if

you asked it to compute L50?
(b) Computingwithapromise.ConsiderthefollowingSCHEMEcodeforafunctionoffourparameterscalled

fast-Lucas-help. The function call
(fast-Lucas-help n k lucas-a lucas-b)

is supposed to return the nth Lucas number under the promise that it is provided with any pair of pre- viousLucasnumbers.Specifically,ifitisgivenanumberk≤nandthetwoLucasnumberLk andLk−1 (in the parameters lucas-a and lucas-b), it will compute L n . The idea is this: If it was given L n and Ln−1 (sothatk =n),thenitsimplyreturnsLn,whichiswhatiswassupposedtocompute. Otherwise assume k < n, in which case it knows Lk and Lk−1 and wishes to make some “progress” towards the previous case; to do that, it calls fast-Lucas-help, but provides Lk+1 and Lk (which it can compute easily from Lk and Lk−1). The code itself:

(define (fast-Lucas-help n k lucas-a lucas-b) (if (= n k)

lucas-a
(fast-Lucas-help n (+ k 1) (+ lucas-a lucas-b) lucas-a)))

With this, you can define the function fast-Lucas as follows:
(define (fast-Lucas n) (fast-Lucas-help n 1 1 2))

(Afterall,L0 =2andL1 =1.)
Enter this code into your SCHEME interpreter. First check that fast-Lucas agrees with your previ-

ous recursive implementation (Lucas) of the Lucas numbers (on, say, n = 3,4,5,6). Now evaluate (fast-Lucas 50)or(fast-Lucas 50000).
There seems to be something qualitatively different between these two implementations. To explain it, consideracallto(Lucas k);howmanytotalrecursivecallsdoesthisgeneratetothefunctionLucas for k = 3,4,5,6? Now consider the call to (fast-Lucas-help k 1 1 2); how many recursive calls

does this generate to fast-Lucas-help for k = 3,4,5,6? Specifically, populate the following table (values for k = 1, 2 have been filled-in):

1

if n = 0, ifn=1, if n > 1.

2. Abstractingthesummationofaseries
(a) ConsidertheharmonicnumbersH =1+1+1+···+1.LastweekyouwrotearecursiveSCHEMEfunction

n123 n
(named harmonic) which, given a number n , computes Hn . Revise your harmonic function, keeping

the name (harmonic n), to take advantage of the sum function seen in the textbook (Section 1.3.1) and shown below:

      (define (sum term a next b)
          (if (> a b)

0
(+ (term a)

                 (sum term (next a) next b))))

Of course, your new and improved definition of harmonic should not be recursive itself and should rely on sum to do the hard work.

2. (b)  Theabovedefinitionofsumisarecursiveprocess.Writeaniterativeversionsum-ithatsolvesthesame problems as sum in an iterative fashion. Demonstrate that it works by using it to define harmonic-i.
3. (c)  Showthatyourharmonicfunctionsworkfor1,50,and100.

3. SICP Exercise 1.42 – Let f and g be two one-argument functions. The composition f after g is defined to be the function x 􏰈→ f (g (x )). Define a procedure, named (compose f g), that implements composition. For example, if inc is a procedure that adds 1 to its argument,
   ((compose square inc) 6)

   49

4. SICP Expercise 1.43 – If f is a numerical function and n is a positive integer, then we can form the n t h re- peated application of f , which is defined to be the function whose value at x is f ( f (…( f (x ))…)). For example, if f is the function x 􏰈→ x +1, then the nth repeated application of f is the function x 􏰈→ x +n. If f is the operation of squaring a number, then the n t h repeated application of f is the function that raises its argu- ment to the 2n th power. Write a procedure named (repeated f n), that takes as inputs a procedure that computesf andapositiveintegernandreturnstheprocedurethatcomputesthenth repeatedapplication of f . Your procedure should be able to be used as follows:

   (( repeated square 2) 5) 625

   You may want to take advantage of the compose function you wrote.

5. The 91 function was introduced in papers published by Zohar Manna, Amir Pnueli and John McCarthy in 1970. These papers represented early developments towards the application of formal methods to program verification. Consider the following form for the 91 function:

   􏰉x − 10, if x > 100 f(x)= f91(x+901), ifx≤100

   where f 91(y ) stands for f (f (··· f (y )···)) , the 91-times-repeated application of f . That is, f composed with itself90times.WriteaSCHEMEfunction,named(m91 x)whichcomputesthe91functionasdefinedabove. You should notice it has some interesting behavior for x ≤ 100.

2