;;; Fibonacci-Zahlen
;;; Common Lisp, big integers
;;; Wolfgang.Urban@schule.at


;;; Algorithmus 1
;
(defun fibo1 (n)
  (if (<= n 2)
      1
      (+ (fibo1 (- n 1)) (fibo1 (- n 2)))
  )
)

; Algorithmus 1a nicht möglich
; ein Zweig von if oder cond *muss* true sein


;;; Algorithmus 2
;;; mit assoziativer Liste
;
(defvar *fiboliste* '())
;
(defun fibo2 (n)
  (if (assoc n *fiboliste*)
      (cdr (assoc n *fiboliste*))
      (let ((neu (if (<= n 2)
                     1            
                     (+ (fibo2 (- n 1)) (fibo2 (- n 2))))))
           (push (cons n neu) *fiboliste*)
           neu)
  )
)


;;; Algorithmus 3
;
(defun fibo3 (n)
  (do ((zaehler 1 (+ zaehler 1))
       (b 1 (+ a b))
       (a 0 b))
      ((> zaehler n) a)
    
  )
)

;;; Algorithmus 4
;
(defun fibo4 (n a b)
  (cond ((= n 1) a)
        ((= n 2) b)
        (t (fibo4 (- n 1) b (+ a b)))
  )
)
; Hilfsfunktion
;
(defun fibo (n)
  (fibo4 n 1 1)
)


;;; Aufruf
;
(fibo1 10)
(fibo4 10 1 1)