It is perfectly possible to write a fib function that takes O(1) space functionally too, but of course it'd have a worse time complexity due to the lack of memoisation.
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.)
Comments
It is perfectly possible to write a fib function that takes O(1) space functionally too, but of course it'd have a worse time complexity due to the lack of memoisation.
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:
(No, I don't really know lisp that well... learning.)