Worse than O(n) for time complexity? Seems it should be easily doable to transcribe the straight forward iterative solution to a tail recursive one. Something like:

    (defun fib-help (a b curX desiredX)
                    (if (= curX desiredX)
                        b
                        (fib-help b (+ a b) (+ curX 1) desiredX)))

 
    (defun fib (x) (fib-help 0 1 1 x))

(No, I don't really know lisp that well... learning.)