Mail Archives: djgpp/1999/12/12/10:28:22
On Sun, 12 Dec 1999, Yong-Kwang Goh wrote:
> Now, I've a dillema -- should I use recursion or looping after all.
> AFAIK, recursion is a very useful and good programming technique,
> but one which gobbles up computing resources and *must* be
> used carefully. Looping is more efficient but usually more complicated
> than using recursion.
>
> I wonder if recursion *is faster* than looping.
The popular wisdom is that looping is faster. However, it turns out that
this is not always true, perhaps even mostly untrue. A great advantage
of recursion is higher locality of code (meaning that the code is
smaller), so it tends to fit better into code caches of modern CPUs.
One particular package (FFTW, The Fastest Fourier Transform in the West,
see http://www.fftw.org) actually uses recursion in speed-critical code,
and performs better than almost any other FFT algorithm.
So your best bet is to try both approaches and see which one is faster.
Of course, the recursive algorithm should be well guarded against stack
overflow and other atrocities, but that's usually easy to do if you plan
for it in advance.
- Raw text -