Date:	Sun, 12 Dec 1999 14:38:16 +0200 (IST)
From:	Eli Zaretskii <eliz AT is DOT elta DOT co DOT il>
X-Sender:	eliz AT is
To:	Yong-Kwang Goh <ykgoh1 AT singnet DOT com DOT sg>
cc:	djgpp AT delorie DOT com
Subject:	Re: Use of recursion
In-Reply-To:	<82vfqn$6ce$1@mango.singnet.com.sg>
Message-ID:	<Pine.SUN.3.91.991212143236.19096l-100000@is>
MIME-Version:	1.0
Reply-To:	djgpp AT delorie DOT com
X-Mailing-List:	djgpp AT delorie DOT com
X-Unsubscribes-To:	listserv AT delorie DOT com

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 -