Recursion vs iteration in Lisp

Question

At this site http://jatha.sourceforge.net/ the example for a fast function is through recursion. Is it that recursion is usually faster and of better performance than iteration in Lisp?

Edit: Does Lisp optimize recursion more than other languages?

Answer 1

It really depends on what you mean by "Lisp" and "recursion".

Scheme mandates tail call optimization, but other than that you are at the mercy of your implementation (and your optimization settings).

E.g., a Lisp implementation may keep recursive calls un-optimized if the debug setting is higher than the speed setting, so that the traces are more meaningful. You need to consult your implementation's manual for details.

However, the critical point here is that (SICP):

... a computer language is not just a way of getting a computer to perform operations, but rather ... it is a novel formal medium for expressing ideas about methodology

IOW, you write code for people to read more that for a computer to execute, so you need to think more in terms of how to express your algorithm clearly than how it will be compiled and executed.

Answer 2

It depends on the algorithm; some make better use of the overhead that recursion typically incurs, to the point that they are faster than their iterative counterparts.

Usually, though, it is the algorithm itself that makes the biggest difference, not this particular implementation detail.