Recursive Fibonacci Schemes

fibonacci.scm

;;; Gabriel B. Sant'Anna <baiocchi.gabriel@gmail.com>
;;; Explained in pt-br at <https://baioc.github.io/scheme/>

;; binary-recursive aka dumb fibonacci
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

;; linear iteration / tail-recursive fibonacci
(define (fibo n)
  (let iter ((n n) (prev 1) (curr 0))
    (if (= n 0) curr
        (iter (- n 1) curr (+ prev curr)))))

;; rec-iterative O(lg(n)) fast fibonacci via successive squaring
(define (fibonacci n)
  (define (square x) (* x x))
  (define (iter a b p q n)
    (cond ((= n 0) b)
          ((even? n) (iter a
                           b
                           (+ (square q) (square p))    ; p'
                           (+ (square q) (* 2 (* p q))) ; q'
                           (/ n 2)))
          (else (iter (+ (* b q) (* a (+ q p)))
                      (+ (* b p) (* a q))
                      p
                      q
                      (- n 1)))))
  (iter 1 0 0 1 n))

;; closed form found through linear algebra eigen-stuff
(define (fibonac n)
  (define phi (/ (+ 1 (sqrt 5)) 2)) ; golden ratio number
  (define fi (- 1 phi))             ; and its complement
  (round (/ (- (expt phi n) (expt fi n))
            (sqrt 5))))