SICP Exercise 1.35

Question

Show that the golden ratio $\varphi$ (section 1.2.2) is a fixed point of the transformation $x\mapsto 1+\frac{1}{x}$, and use this fact to compute $\varphi$ by means of the fixed-point procedure.

Answer

We know from section 1.2.2 that ${\varphi }^2=\varphi +1$. We can use this information to show that the above transformation will converge to $\varphi$.

So why does this work? Well, because they are the same equation. If we divide ${\varphi }^2=\varphi +1$ by $\varphi$ on both sides, we get $\varphi =1+\frac{1}{\varphi }$, which, of course, is the equation from the question.

copy(define tolerance 0.0001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(fixed-point (λ (x) (+ 1 (/ 1 x))) 1.0)

The results are very close to the actual value of $\varphi$:

copy1.6180555555555556