2 ms·
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 memo
by FreeFull 13y ago
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.
- taeric 13y agoWorse 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.)