Problem: Compute the nth term in the Fibonacci sequence where the sequence
starts with the values 1 and 1.
I. Tree Recursive Process.
(a). Write (fib-r n) a recursive function that uses a recursive process.
(b). Test your code.
Verify these test cases:
(fib-r 1) -> 1
(fib-r 2) -> 1
(fib-r 3) -> 2
(fib-r 4) -> 3
(fib-r 5) -> 5
(fib-r 6) -> 8
(c). Time the following function calls.
(time (fib-r 30))
(time (fib-r 31))
(time (fib-r 32))
(d). If (time (fib-r 30)) is x and (time (fib-r 31)) is y
what is the time of (fib-r 32)?
(e). Can you compute the 100th term with this method?
II. Iterative process.
(a). Write (fib-i n) that uses an iterative process to compute the
nth term in the sequence.
(b). Verify that your function works.
(c). Time your function.
(d.) Can you compute the 100th term?
III. Explicit Method
(a). Define phi to be (/ (+ 1 (sqrt 5)) 2).
(b). Add the distance method to your work space.
(define distance
(lambda (a b)
(abs (- a b))))
(c). Useful functions.
(ceiling x ) evaluates to the smallest integer greater than or equal x.
(floor x) evaluates to the largest integer greater than or equal to x.
(expt b n) evaluates to b raised to the nth power. This function is
fast.
Test:
(ceiling 2.3)
(floor 2.3)
(ceiling 12.8)
(floor 12.8)
(ceiling -3.1)
(floor -3.1)
Write the function (closest-integer x) that returns the closest integer
to x. Assume x is a real number.
Test cases:
(closestInteger 3.9) -> 4
(closestInteger 3.1) -> 3
(closestInteger 3.5) -> 4
(closestInteger 2.5) -> 3
(d). Note the closest integer to (phi^n)/(sqrt 5) is the nth term in the
Fibonacci sequence that begins with 1 and 1.
Write a function (fib n) to compute the nth term.
(f). Verify that it works.
(g). Can you compute the 100th term? Is it equal to (fib-i 100)?
(h). Write the function (find-largest n) that finds the largest integer
n such that (fib n) is equal to (fib-i n).
;; Integer -> Integer
;; Assumes n >= 100.
(define find-largest
(lambda(n)
(i). What is the result of (find-largest 100)?