When would it be better to use recursion than a loop?

5 views
Skip to first unread message

Flounder

unread,
Mar 28, 2000, 3:00:00 AM3/28/00
to
I come from a background of C/C++, perl, python, and more languages of
the sort. I am currently learning Lisp on my own and am seeing that
Lisp programmers use recursion more than I have seen in the other
languages that I have programmed in so when is it best to use it and
when would it be best to use loops? Maybe you could just give me some
basic rules to follow on how to decide which to use.

Thanks to all.

--
-Flounder


Yeh, Chih Hao

unread,
Mar 29, 2000, 3:00:00 AM3/29/00
to
At least, I found a situation quite suitable for recursion. That's
processing something with grammar, like BCNF.
Yochi
"Flounder" <ja...@flashmail.com> ?????
news:38E12D56...@flashmail.com...

Johan Kullstam

unread,
Mar 29, 2000, 3:00:00 AM3/29/00
to
Flounder <ja...@flashmail.com> writes:

> I come from a background of C/C++, perl, python, and more languages of
> the sort. I am currently learning Lisp on my own and am seeing that
> Lisp programmers use recursion more than I have seen in the other
> languages that I have programmed in so when is it best to use it and
> when would it be best to use loops? Maybe you could just give me some
> basic rules to follow on how to decide which to use.

use recursion to dive into nested lists. other than that, use
whatever comes naturally. recursion in lisp is somewhat less painful
and awkward than other languages, but that doesn't mean you have to
use it everywhere.

--
J o h a n K u l l s t a m
[kull...@ne.mediaone.net]
Don't Fear the Penguin!

Andrew Cooke

unread,
Mar 29, 2000, 3:00:00 AM3/29/00
to
In article <38E12D56...@flashmail.com>,

Flounder <ja...@flashmail.com> wrote:
> I come from a background of C/C++, perl, python, and more languages of
> the sort. I am currently learning Lisp on my own and am seeing that
> Lisp programmers use recursion more than I have seen in the other
> languages that I have programmed in so when is it best to use it and
> when would it be best to use loops? Maybe you could just give me some
> basic rules to follow on how to decide which to use.

I'd suggest using recursion until you're used to it. At that point
you'll have a "gut feeling" about what is most suitable when (the
extended loop command in lisp takes some learning too).

Thinking about when I use each, recursion is better for trees (when
you'd end up using stacks with loops) and can be easier to modify when
things are complicated. Looping, especially with the extended loop
command, is better for quickly running through simple lists (although
often the mapping functions can also be used here). I honestly think
you just have to try them all out and come to recognise which idiom to
use where.

I can remember in my first programming job, using C, after leaving
academia. In my spare time I'd been learning functional programming and
found recursion very difficult at first. I realised I'd finally broken
through when it struck me that a problem at work that required some
nasty coding had a much simpler recursive solution (even in C). My boss
wasn't very happy, though (in the end I left :-)

Andrew


Sent via Deja.com http://www.deja.com/
Before you buy.

Paolo Amoroso

unread,
Mar 29, 2000, 3:00:00 AM3/29/00
to
On Tue, 28 Mar 2000 16:08:22 -0600, Flounder <ja...@flashmail.com> wrote:

> the sort. I am currently learning Lisp on my own and am seeing that
> Lisp programmers use recursion more than I have seen in the other
> languages that I have programmed in so when is it best to use it and
> when would it be best to use loops? Maybe you could just give me some

I am a beginner myself, and I have the impression not much that Lisp
programmers use recursion more often, but rather that they are less afraid
of it. For an interesting example of recursionphobia, see:

"Considering Recursion - Granted, recursion means different things to
different people. But for Arch, recursion means trouble because recursive

code entangles control flow, which hurts readability, reuse, and
optimization."
Arch D. Robison
Dr.Dobb's Journal - March 2000, page 52


Paolo
--
EncyCMUCLopedia * Extensive collection of CMU Common Lisp documentation
http://cvs2.cons.org:8000/cmucl/doc/EncyCMUCLopedia/

Thomas A. Russ

unread,
Mar 29, 2000, 3:00:00 AM3/29/00
to

Rule 1: Always use recursion when you have to.

Rule 2: Use recursion when it makes the algorithm easier to understand.

Rule 3: Use a loop when it makes the algorithm easier to understand.

--
Thomas A. Russ, USC/Information Sciences Institute t...@isi.edu

David Hanley

unread,
Mar 29, 2000, 3:00:00 AM3/29/00
to

Basically, I use recursion when it makes the code clearer, and does
not cause excessive execution or memory cost in important places.

dave


Tom Breton

unread,
Mar 29, 2000, 3:00:00 AM3/29/00
to
Flounder <ja...@flashmail.com> writes:

> I come from a background of C/C++, perl, python, and more languages of

> the sort. I am currently learning Lisp on my own and am seeing that
> Lisp programmers use recursion more than I have seen in the other
> languages that I have programmed in

Functional languages, eg Scheme, ML, Haskell, also use recursion
heavily, even more than Lisp.

> so when is it best to use it and
> when would it be best to use loops? Maybe you could just give me some

> basic rules to follow on how to decide which to use.

Recursion is called for when you are processing a naturally recursive
data structure (eg a tree), or when your algorithm is naturally
recursive.

Caveat: no general rule is a substitute for good judgement.

--
Tom Breton, http://world.std.com/~tob
Not using "gh" since 1997. http://world.std.com/~tob/ugh-free.html
Rethink some Lisp features, http://world.std.com/~tob/rethink-lisp/index.html

Paul Rudin

unread,
Mar 30, 2000, 3:00:00 AM3/30/00
to
>>>>> "Thomas" == Thomas A Russ <t...@sevak.isi.edu> writes:

Thomas> Rule 1: Always use recursion when you have to.

You never _need_ to use (explicit) recursion. The are plenty of languages
that lack recursion that are Turing complete.

Thomas> Rule 2: Use recursion when it makes the algorithm easier to
Thomas> understand.

Thomas> Rule 3: Use a loop when it makes the algorithm easier to
Thomas> understand.

Often this is a matter of taste - if you're used to writing recursive code
then this is what helps you to understand stuff and vice versa.


Erik Naggum

unread,
Mar 30, 2000, 3:00:00 AM3/30/00
to
* Flounder <ja...@flashmail.com>

| I come from a background of C/C++, perl, python, and more languages of
| the sort. I am currently learning Lisp on my own and am seeing that Lisp
| programmers use recursion more than I have seen in the other languages
| that I have programmed in so when is it best to use it and when would it

| be best to use loops? Maybe you could just give me some basic rules to
| follow on how to decide which to use.

here's my rule of thumb: whenever the algorithm generates values from or
for each iteration, it is naturally recursive, and will most probably
find an elegant recursive expression, which, because it uses an optimized
storage of such values, namely the function call stack frame, will also
be more efficient than your hand-crafted storage unless you're very good
at what you're doing. whenever the algorithm does _not_ generate values
from each iteration (as in: generates and consumes an equal amount of
values), it is in my not so humble opionion extremely unlikely that a
recursive implementation will make more sense than an iterative solution,
and not unlikely that a recursive solution will be more complex and will
also run slower unless you're careful.

#:Erik

Tim Bradshaw

unread,
Mar 30, 2000, 3:00:00 AM3/30/00
to
* Paul Rudin wrote:
>>>>>> "Thomas" == Thomas A Russ <t...@sevak.isi.edu> writes:
Thomas> Rule 1: Always use recursion when you have to.

> You never _need_ to use (explicit) recursion. The are plenty of languages
> that lack recursion that are Turing complete.

So long as you like manipulating stacks yourself, of course!

--tim

Reply all
Reply to author
Forward
0 new messages