Speaking of the Fibonacci Sequence
We can write this as the recursion relation
G0 = 1
Gn+1 = 1 + 1/Gn
The problem is to find G200. It's not hard to see that the Gn converge to some number G and therefore that G = 1 + 1/G, and so G is the golden ratio.
More interesting, though, is that Gn = Fibn+1/Fibn, where Fibn is the nth Fibonacci number starting from 1—that is, the Fibonacci sequence 1, 1, 2, 3, 5, … . Exercise 1.19 of SICP develops a fast method of calculating Fibn+1 and Fibn at the same time in O(log n) time (it's very much like the fast exponential routines). This gives us an elegant and fast solution to the problem
(define golden-ratio (lambda (n) (let iter ((n n) (p 0) (q 1) (a 1) (b 1)) (cond ((= n 0) (/ a b)) ((even? n) (iter (/ n 2) (+ (* p p) (* q q)) (+ (* 2 p q) (* q q)) a b)) (else (iter (- n 1) p q (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q))))))))I like this problem because it's a chance to use the fast Fibonacci
calculator from SICP, an opportunity that doesn't come up often.