;;; Intro to AI
;;;
;;; The Fibonacci Function x 3
;;;
;;;     --Selmer Bringsjord

(defun fib1 (n)
  "The Fibonacci functing defined in doubly
   recursive fashion"
  (if (or (= n 0) (= n 1))
    1
    (+ (fib1 (- n 1))
       (fib1 (- n 2)))))

(defun fib2 (n)
  "Another definition of the Fibonacci function,
   using assert."
  (assert (and (> n -1) (integerp n))
          (n)
          "The argument must be a natural number; instead
           it's ~S."
          n)
  (if (or (= n 0) (= n 1))
    1
    (+ (fib2 (- n 1))
       (fib2 (- n 2)))))

(defun fib3 (n)
  "Yet another definition of the Fibonacci function, this time without
   recursion.  This definition uses Binet's formula.  The exact equation,
   in LaTex, is:
        $$
        f(n) = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}
        -\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}\right]
        $$"
  (assert (and (> n -1) (integerp n))
          (n)
          "The argument must be a natural number; instead
           it's ~S."
          n)
  (let ((constant (sqrt 5)))
    (round (/ (- (expt (/ (+ 1 constant) 2) (+ n 1))
                 (expt (/ (- 1 constant) 2) (+ n 1)))
              constant))))