Recursive searching through a list

[Dorian Fabre]

Hi there,

I need to write a script that will test each item in a list to see if that
item is a list. If it is, it should test each item in the new list to see if
it is a list (and so on, to infinity) before moving on to the second item in
the first list. If the item being tested isn't a list, it should be appended
to a third list.

The final result should be a list of all the items that aren't lists
themselves - if you use the example at
[url]http://www.andrewssykes.nl/test/flowchart.htm[/url], the result should be [X1a1,
X1a2, X1b, X2a, X2b]. It's also very important that the list is kept in this
order.

Can anyone help?

Cheers
Dorian

[Robert Tweed]

"Dorian Fabre" <dorian.f@sel-pres.co.uk> wrote in message
news:bgdfon$sam$1@forums.macromedia.com...

>
> I need to write a script that will test each item in a list to see if that
> item is a list. If it is, it should test each item in the new list to see

if

> it is a list (and so on, to infinity) before moving on to the second item

in

> the first list. If the item being tested isn't a list, it should be

appended

> to a third list.

That's quite simple:

on recurseList theList
output = []

repeat with i in theList
if( listP( theList[i] ) ) then
-- Recurse
output.add( recurseList( theList[i] ) )
else
output.add( theList[i] )
end
end repeat

return output
end

NB: Spot anything odd about the output of this function?

> The final result should be a list of all the items that aren't lists
> themselves

Well, in that case you don't need recursion at all because you are simply
ignoring all the sub-lists, no? All you want is:

on flattenList theList
output = []

repeat with i in theList
if( not listP( theList[i] ) ) then
output.add( theList[i] )
end
end repeat

return output
end

BTW, you should avoid recursion whenever possible because it can be very
slow, and you have to be careful to avoid infinite recursion, which will
crash your system by stack overflow quicker than you can say "blue screen of
death".

- Robert

[David Downie]

"Robert Tweed" <robertNOSPAM@killingmoon.com> wrote in message
news:bgdpmv$hef$1@forums.macromedia.com...

> "Dorian Fabre" <dorian.f@sel-pres.co.uk> wrote in message
> news:bgdfon$sam$1@forums.macromedia.com...

> >
> > I need to write a script that will test each item in a list to see if

that

> > item is a list. If it is, it should test each item in the new list to

see

> if

> > it is a list (and so on, to infinity) before moving on to the second

item

> in

> > the first list. If the item being tested isn't a list, it should be

> appended

> > to a third list.

>
> That's quite simple:
>
> on recurseList theList
> output = []
>
> repeat with i in theList
> if( listP( theList[i] ) ) then

I've never seen listP before - looked it up and it indicates true if the
item is a list, rectangle or point. How do you know here that we are not
dealing with lists of rectangles and points?

> -- Recurse
> output.add( recurseList( theList[i] ) )
> else
> output.add( theList[i] )
> end
> end repeat
>
> return output
> end
>
> NB: Spot anything odd about the output of this function?

This will just return the same list as was passed to it won't it? What's the
point?

> > The final result should be a list of all the items that aren't lists
> > themselves

>
> Well, in that case you don't need recursion at all because you are simply
> ignoring all the sub-lists, no? All you want is:
>
> on flattenList theList
> output = []
>
> repeat with i in theList
> if( not listP( theList[i] ) ) then
> output.add( theList[i] )
> end
> end repeat
>
> return output
> end

I'm not sure that is what she wants is it? I think she wants all the items
in the lists and sublists.

(Quoting from her original message)

> The final result should be a list of all the items that aren't lists
> themselves - if you use the example at
> [url]http://www.andrewssykes.nl/test/flowchart.htm[/url], the result should be [X1a1,
> X1a2, X1b, X2a, X2b]. It's also very important that the list is kept in

this

> order

(End her quote)

I don't have director on this machine due to an unfortunate monitor
explosion, so I'm going to be lazy and not write the routine as I'd like to
test it. But I'll try and give it a go this arvo.

> BTW, you should avoid recursion whenever possible because it can be very
> slow, and you have to be careful to avoid infinite recursion, which will
> crash your system by stack overflow quicker than you can say "blue screen

of

> death".

Recursion solutions can be very elegant. Haven't tried it with lingo though
(hopefully will this arvo).

David

[Luke]

> BTW, you should avoid recursion whenever possible because it can be very

> slow, and you have to be careful to avoid infinite recursion, which will
> crash your system by stack overflow quicker than you can say "blue screen

of

> death".

Others would argue that recursion is amazingly useful (even beautiful),
especially in languaging parsing and AI work. The programming language LISP
is built around recursive theory (recursive use of conditional
expressions ). Most language parsers use recursion to work through search
trees. Moreover, recursion isn't just a programming technique. Recursion as
a trope combines ideas of self-reference, self-similarity, circularity,
repetition and nesting. It reveals a path from the finite to the infinite,
from the same to the different (see
[url]http://www.screenarts.net.au/beingconnected/f_exh/pal900.html[/url],
[url]http://www.lingoworkshop.com/examples/Orbital1.asp[/url])

Sure, recursion can be a tiny bit slower than iterating through a loop, but
the best things in life aren't always the absolute quickest ;-)

Luke

[David Downie]

"Dorian Fabre" <dorian.f@sel-pres.co.uk> wrote in message
news:bgdfon$sam$1@forums.macromedia.com...

> Hi there,
>
> I need to write a script that will test each item in a list to see if that
> item is a list. If it is, it should test each item in the new list to see

if

> it is a list (and so on, to infinity) before moving on to the second item

in

> the first list. If the item being tested isn't a list, it should be

appended

> to a third list.
>
> The final result should be a list of all the items that aren't lists
> themselves - if you use the example at
> [url]http://www.andrewssykes.nl/test/flowchart.htm[/url], the result should be [X1a1,
> X1a2, X1b, X2a, X2b]. It's also very important that the list is kept in

this

> order.
>
> Can anyone help?

Hi how about something like this:

on exitFrame me

end

on beginSprite
testList = [ [ ["x1a1", "x2a2"], "x1b"] , ["x2a2","x2ab"] ]
destList = []
genList(testList, destList)
put destList
end

on genList sourceList, destList
i = 1
repeat while i <= sourceList.count
if ilk(sourceList[i], #list) then
genList( sourceList[i], destList)
else
destList.add( sourceList[i] )
end if
i = i + 1
end repeat
end

David.

[David Downie]

"Robert Tweed" <robertNOSPAM@killingmoon.com> wrote in message
news:bgdpmv$hef$1@forums.macromedia.com...

> "Dorian Fabre" <dorian.f@sel-pres.co.uk> wrote in message
> news:bgdfon$sam$1@forums.macromedia.com...

>> That's quite simple:

>
> on recurseList theList
> output = []
>
> repeat with i in theList
> if( listP( theList[i] ) ) then
> -- Recurse
> output.add( recurseList( theList[i] ) )
> else
> output.add( theList[i] )
> end
> end repeat
>
> return output
> end

Also - apart from this returning a list with each call resulting in a list
of lists - doesn't "i" in the loop represent the value of the member, rather
than the index? ence it would just be listP( i ) rather than listP(
theList[i] ).

David.

[Luke]

> on genList sourceList, destList

> i = 1
> repeat while i <= sourceList.count
> if ilk(sourceList[i], #list) then
> genList( sourceList[i], destList)
> else
> destList.add( sourceList[i] )
> end if
> i = i + 1
> end repeat
> end

Here's a minor variation to show how it might be achieved using recursion
without the repeat loop (for illustration only, in this case, there is no
advantage to do away with the repeat loop)


on genList (sourceList, destList, i)
if i < sourceList.count then
i = i + 1
thing = sourceList[i]
if listP(thing) then genList(thing, destList, 0)
else destList.append(thing)
genList (sourceList, destList, i)
end if
end

Luke

[Robert Tweed]

"David Downie" <david@NOSPAMdownieFORME.net> wrote in message
news:bgek2n$8ue$1@forums.macromedia.com...

>
> I've never seen listP before - looked it up and it indicates true if the
> item is a list, rectangle or point. How do you know here that we are not
> dealing with lists of rectangles and points?

You don't. If you really care, you can use ilk to be more specific. Do we
care in this instance?

> > NB: Spot anything odd about the output of this function?

>
> This will just return the same list as was passed to it won't it? What's

the

> point?

Well spotted, there is no point. This was not intended to be a completed
solution as I was quite tired and didn't fully understand what the poster
was asking. It was just intended to show how to go about solving the problem
with recursion.

> I'm not sure that is what she wants is it? I think she wants all the items
> in the lists and sublists.

No, you're right, I missed the point entirely. The solution you posted
elsethread appears to be correct. The only thing I would do to make it
simpler is rewrite it like this:

on genList sourceList, destList
if( not ListP( destList ) ) then destList = []

repeat with theItem in sourceList
if( listP( theItem ) ) then
genList( theItem, destList )
else
destList.add( theItem )
end if
end repeat

return destList
end

This way, you can just call with:

destList = genList( sourceList )

You don't need to initialise and pass destList to the function, which is a
good way to introduce bugs (i.e., reusing the same list and forgetting to
reset it).

Also, I wouldn't use your repeat-while structure unless you have a good
reason to. It's very easy to forget the i = i + 1 line (or construct the
code in such a way that it is sometimes skipped) which can easily introduce
bugs. I generally only use complex loop structures for unusually complex
code that really warrants it.

[from other post]

> Also - apart from this returning a list with each call resulting in a list
> of lists - doesn't "i" in the loop represent the value of the member,

rather

> than the index? ence it would just be listP( i ) rather than listP(
> theList[i] ).

Oops, you're right. I'd been doing a lot of JavaScript programming that day,
and in JavaScript the for( i in list ) loop structure sets i to the index,
not the item. I got the two languages mixed up. I've fixed that in the code
above, and even tested it this time! :-)

- Robert

[Robert Tweed]

"Luke" <lukewig@SPAMMAGNET_hotmail.com> wrote in message
news:bgf0li$q8r$1@forums.macromedia.com...

>
> Others would argue that recursion is amazingly useful (even beautiful),
> especially in languaging parsing and AI work.

I would say that in such cases, it is a necessary evil.

> The programming language LISP
> is built around recursive theory (recursive use of conditional
> expressions ).

That's why no-one uses LISP ;-)

> Moreover, recursion isn't just a programming technique. Recursion as
> a trope combines ideas of self-reference, self-similarity, circularity,
> repetition and nesting. It reveals a path from the finite to the infinite,
> from the same to the different (see
> [url]http://www.screenarts.net.au/beingconnected/f_exh/pal900.html[/url],
> [url]http://www.lingoworkshop.com/examples/Orbital1.asp[/url])

No-one's saying recursion should always be avoided, since it's clearly
essential for certain things (like Fractals) but for solving general
programming tasks, it should be avoided like the plague wherever possible
for the reasons that it is slow and consumes memory extremely quickly.

> Sure, recursion can be a tiny bit slower than iterating through a loop,

but

> the best things in life aren't always the absolute quickest ;-)

Given two solutions, one of which has one or two lines less code, but runs
in exponential time instead of linear time, I'd go with the slightly longer
one.

You've also overlooked the problem of memory usage in recursion, which is
more often a far bigger problem than the issue of running time. Every
recursive iteration requires some memory; either a few bytes or possibly
more. Either way, passing a large input to a naive recursive function is an
easy way to crash your system as you soon run out of stack space and/or heap
space.

- Robert

[Robert Tweed]

"Luke" <lukewig@SPAMMAGNET_hotmail.com> wrote in message
news:bgfbgf$96c$1@forums.macromedia.com...

>
> Here's a minor variation to show how it might be achieved using recursion
> without the repeat loop (for illustration only, in this case, there is no
> advantage to do away with the repeat loop)

JFTR, not only is there no advantage but the fully recursive solution does
have a potentially major disadvantage (hence my earlier comments about
trying to avoid recursion whenever possible). The disadvantages are (1) it
is slightly slower and (2) it uses a lot of stack space.

(2) is potentially the most worrying of these, because if you pass a very
long list, the recursive function is likely to crash, whereas the iterative
function will not.

Of course, since this problem requires some recursion anyway, it's worth
pointing out that there are similar risks in both solutions (though the
fully-recursive solution is riskier). In particular, if every list contains
only one element (another list, except for leaf nodes) then there will be no
advantage in the iterative method at all, since there will never be anything
to iterate through.

Also, you need to be carful of infinite recursion. You can cause this like
so:

someNode = [1, 2, 3]
tree = [ someNode, someNode ]
someNode.add( tree )

Now try "put tree" (but make sure you don't have any unsaved data first!).
"put" is recursive, as are these functions, and this self-reference will
cause any naive recursive function to go into an infinte death-spiral. Each
iteration is using slightly more memory too, so it won't be long before the
system runs out of resources and crashes.

There are techniques to avoid this problem, but I don't think they are
possible in Lingo since it doesn't have any method of comparing pointers.

- Robert

[David Downie]

> I don't know if I want to pick up too many lingo
> specific ways of doing things - generally I think of it is a sloppy
> scripting language, although I'm having to work with it this year.

Of course I would make a sloppy english mistake here. Not a word!
Not-a-word.

David.

[Robert Tweed]

"David Downie" <david@NOdownieSPAM.net> wrote in message
news:bghbf3$1qt$1@forums.macromedia.com...

> >
> > You don't. If you really care, you can use ilk to be more specific. Do
> > we care in this instance?

>
> Well I cared because I was scared when I saw that it sometimes returned
> true
> when it wasn't a list. I didn't know what the list was to be of - although
> the example seemed to use strings.

Yeah, I get that. My view is that there is always more than one "correct"
solution, the important thing is to have given it some thought. Sometimes
the difference is a matter of personal taste, sometimes it comes down to
wanting a specific outcome. The main thing is that you should always know
exactly what each function does, and not be surprised when it does it.

The good thing about a group like this is that people will post different
alternatives that we may not have considered ourselves, which often lend
themselves to better solutions to future problems.

> Well, I guess that I'm used writing while loops from other languages. I'm
> not used to lingo's list traversal stuff, so I guess you stick to what you
> know, at least initially. I don't know if I want to pick up too many lingo
> specific ways of doing things - generally I think of it is a sloppy
> scripting language, although I'm having to work with it this year.

I disagree to some extent because Lingo is actually one of my favourite
languages. OK, it does have it's quirks and quite a lot of legacy stuff that
could have been done better if the language had been designed from the
ground up yesterday rather than incrementally transmogrified over a number
of years. If you give it a fair chance this year then you may well come to
appreciate it. Apart from anything, it has a great "instant gratification"
factor, because you can get a project working remarkably quickly in
Director.

Something like "repeat with" is actually pretty common in modern languages,
especially scripting languages. JavaScript has a special for structure, PHP
has foreach. In languages that don't support this, but it would have been
appropriate, I often use something like:

for( i=list.length; i; --i ) { item = list[i]; doStuff( item ); }

Whatever you do, it's still best to have a self contained loop control
structure, and *not* modify the loop control variable inside the loop. This
simple rule keeps your code less prone to bugs, so it's a good idea to do it
whenever possible. It's just too easy to accidentally modify the control
code by accident, unless it's part of the loop structure itself.

There are some complex loop structures that can only be built with a while
structure and separate control logic, but those are very rare and should be
treated with great care when they are required. Even when making such loops
in C, Java or JavaScript I try to put all the logic in a for loop and use
the comma operator so that all the code is self-contained.

Unfortunately Lingo isn't very flexible in that repect, but the golden rule
is still to keep things as simple as possible. If I ever do really have to
seperate them out, then I put a comment like this:

i = i + 1 -- Next item in list, do not change

It just lets me know the importance of that line so I don't do something
stupid later, which is surprisingly easy to do at 4am :-)

> Mate, it's easy enough to make a mistake. As someone relatively new to
> lingo
> though, you can be sure I took peverse pride in finding mistakes in your
> example! :-)

Yeah, don't worry, you'll probably find plenty more as I quite often post
code solutions without testing them. I'm actually surpised I don't post an
awful lot more mistakes than I do: I actually seem to make less stupid
mistakes than I do when I'm writing my own code :-)

- Robert

[David Downie]

"Robert Tweed" <robertNOSPAM@killingmoon.com> wrote in message
news:bghe08$4td$1@forums.macromedia.com...

> "David Downie" <david@NOdownieSPAM.net> wrote in message
> news:bghbf3$1qt$1@forums.macromedia.com...

> The good thing about a group like this is that people will post different
> alternatives that we may not have considered ourselves, which often lend
> themselves to better solutions to future problems.

Agree. That's why I'm taking part. A good way to learn.

> > Well, I guess that I'm used writing while loops from other languages.

I'm

> > not used to lingo's list traversal stuff, so I guess you stick to what

you

> > know, at least initially. I don't know if I want to pick up too many

lingo

> > specific ways of doing things - generally I think of it is a sloppy
> > scripting language, although I'm having to work with it this year.

>
> I disagree to some extent because Lingo is actually one of my favourite
> languages. OK, it does have it's quirks and quite a lot of legacy stuff

that

> could have been done better if the language had been designed from the
> ground up yesterday rather than incrementally transmogrified over a number
> of years.

Yep, the old style and dot style double up is an example of this I think.
One example of something that annoys me is lack of typing and declarations
for locals. Funny Gary Rozenbweig trys to say typing is used in "older
languages" and lingo "does not have this restriction" (Using MX, p84).
Requiring typing and declarations would result in me making less mistakes!

> If you give it a fair chance this year then you may well come to
> appreciate it. Apart from anything, it has a great "instant gratification"
> factor, because you can get a project working remarkably quickly in
> Director.

I appreciate that already - I can whip stuff up very quickly. Indeed the
challenge as I find it is in the content creation (images, sound, look and
feel, game design, cartoon scripts) rather than the "programming". It's the
easy bit (at least in the sort of thing I'm doing - a language style
teaching CD with cartoon animation and early 80s style games). Unfortunately
I'm a much better programmer than graphic designer.

I suspect if I was using something like C++ the programming challenge would
be much greater unless I had a great 3rd party library (but perhaps I would
be less bored).

> Something like "repeat with" is actually pretty common in modern

languages,

> especially scripting languages. JavaScript has a special for structure,

PHP

> has foreach. In languages that don't support this, but it would have been
> appropriate, I often use something like:
>
> for( i=list.length; i; --i ) { item = list[i]; doStuff( item ); }
>
> Whatever you do, it's still best to have a self contained loop control
> structure, and *not* modify the loop control variable inside the loop.

I just disagree. I think it is a matter of personal choice. There is no evil
in iterating something yourself. Again, I suppose it's just an informed
choice whether you use a for or while loop - I've used a few in my time
although I didn't program for 4 years. I did regularly from 92-98 though, as
a CS student and for a while out in the field. But I'm back now, and trying
to make my fortune, although it's going slow! :-)

> Unfortunately Lingo isn't very flexible in that repect, but the golden

rule

> is still to keep things as simple as possible.

I'm all for that. Sometimes for my brain it is simple to to a trivial while
traversal.

> Yeah, don't worry, you'll probably find plenty more as I quite often post
> code solutions without testing them. I'm actually surpised I don't post an
> awful lot more mistakes than I do: I actually seem to make less stupid
> mistakes than I do when I'm writing my own code :-)

Well better to help someone with a risk of a mistake than not help them at
all.

David.

[Robert Tweed]

"David Downie" <david@NOdownieSPAM.net> wrote in message
news:bghd4v$3tn$1@forums.macromedia.com...

> >
> > Also, you need to be carful of infinite recursion.

>
> Just as you have to be careful of infinate loops. How would an iterative
> solution be any better in this example? Presumably you are maintaining

some

> sort of stack anyway to keep track of prior state while working down the
> list iteratively ?

No, the difference between iterative traversal and recursive traversal is
that recursion uses the stack whereas iteration doesn't. Each iteration of a
recursive function adds more data to the stack, whereas each iteration of
the iterative method uses no extra memory.

In this case, the "iterative" solution is actually a hybrid part-iterative,
part-recursive function. The recursive part has exactly the same problems as
the pure-recursive solution. The only difference is that these problems are
magnified with the pure recursive function because it *must* use the stack
for every item in the list, whereas the hybrid function *might* use the
stack. Obviously the second of these is less likely to result in a stack
overflow, but each could well overflow given a sufficiently deeply nested
list.

> As for the time taken to call
> a function, in a lot of languages it isn't really significant - lingo

isn't

> known for speed anyway, so I guess you would have to time it. Having said
> that computers are pretty fast these days, even when running lingo, so I
> guess again you would need to time it.

[url]http://www.killingmoon.com/director/optimise/speedtest/[/url]

Of course, the fact that recursion is an inherently slow design means that
if you want to write optimal code you should avoid it anyway, no matter how
small the overhead for each iteration might be (it all adds up over a large
dataset). Remember though, the stack space overhead is far more significant
than the overhead in terms of time.

- Robert

[David Downie]

"Robert Tweed" <robertNOSPAM@killingmoon.com> wrote in message
news:bghge1$7mh$1@forums.macromedia.com...

> "David Downie" <david@NOdownieSPAM.net> wrote in message
> news:bghd4v$3tn$1@forums.macromedia.com...

> > >
> > > Also, you need to be carful of infinite recursion.

> >
> > Just as you have to be careful of infinate loops. How would an iterative
> > solution be any better in this example? Presumably you are maintaining

> some

> > sort of stack anyway to keep track of prior state while working down the
> > list iteratively ?

>
> No, the difference between iterative traversal and recursive traversal is
> that recursion uses the stack whereas iteration doesn't. Each iteration of

a

> recursive function adds more data to the stack, whereas each iteration of
> the iterative method uses no extra memory.

But in this instance, how would you iteratively traverse down a list of
lists of lists without recording state? It has to go somewhere.

> In this case, the "iterative" solution is actually a hybrid

part-iterative,

> part-recursive function. The recursive part has exactly the same problems

as

> the pure-recursive solution. The only difference is that these problems

are

> magnified with the pure recursive function because it *must* use the stack
> for every item in the list, whereas the hybrid function *might* use the
> stack. Obviously the second of these is less likely to result in a stack
> overflow, but each could well overflow given a sufficiently deeply nested
> list.

So one way or the other you record state.

> > As for the time taken to call
> > a function, in a lot of languages it isn't really significant - lingo

> isn't

> > known for speed anyway, so I guess you would have to time it. Having

said

> > that computers are pretty fast these days, even when running lingo, so I
> > guess again you would need to time it.

>
> [url]http://www.killingmoon.com/director/optimise/speedtest/[/url]
>
> Of course, the fact that recursion is an inherently slow design means that
> if you want to write optimal code you should avoid it anyway, no matter

how

> small the overhead for each iteration might be (it all adds up over a

large

> dataset). Remember though, the stack space overhead is far more

significant

> than the overhead in terms of time.

Yep, I think we'll just disagree on this one. Recursion is handy and elegant
eg traversal of a binary tree or even say a list of lists - it's just easier
and less erorr-prone than an iterative solution.

David.

[David Downie]

BTW, thanks for the test link. If my code ever needs to be quicker I'll make
use of it (I don't think my current project requires it as of yet).
David.

[Robert Tweed]

"David Downie" <david@NOdownieSPAM.net> wrote in message
news:bghgm4$825$1@forums.macromedia.com...

>
> But in this instance, how would you iteratively traverse down a list of
> lists of lists without recording state? It has to go somewhere.

Yes, but this is a problem that /requires/ a recursive solution. My point is
that there are recursive solutions to problems that also have other
solutions, and in such cases you should avoid recursion. In this instance,
the function that uses iteration as far as possible is better because
although it still has the problems associated with recursion, it's not as
bad as the pure recursive solution.

- Robert

[David Downie]

"Robert Tweed" <robertNOSPAM@killingmoon.com> wrote in message
news:bghjfj$bej$1@forums.macromedia.com...

> "David Downie" <david@NOdownieSPAM.net> wrote in message
> news:bghgm4$825$1@forums.macromedia.com...

> >
> > But in this instance, how would you iteratively traverse down a list of
> > lists of lists without recording state? It has to go somewhere.

>
> Yes, but this is a problem that /requires/ a recursive solution.

Well there could be an iterative solution (strictly this isn't recursive)
but you would need a stack to retain state. The recursive solution is
simpler however.
David.

[Robert Tweed]

"David Downie" <david@NOdownieSPAM.net> wrote in message
news:bghker$cgn$1@forums.macromedia.com...

>
> Well there could be an iterative solution (strictly this isn't recursive)
> but you would need a stack to retain state.

I would still call that a recursive solution, if not strictly a recursive
implementation. The difference is semantic, really. This problem is
recursive in nature because of the nested lists; the solution is therefore
going to be recursive no matter what you try to do. It doesn't matter what
steps you might take to obfuscate the recursion, it's still there, eating up
the stack.

However, this gets away from my original point which is simply to avoid
hammering the stack unless you really need to. That means you should use
recursion where it's needed, but think long and hard first about whether you
really do need it or not.

- Robert

[cl]

Hi Robert,

Going to have to disagree with you a bit about LISP/Scheme there ;-)
Recursion can be very annoying to deal with but it has its benefits...
ever seen the code for an interpreter or compiler built in LISP? It
may look more confusing but it's typically much more concise than it
would be in a language like C (whether or not it's easier to implement
really depends on the programmer, I guess :-P). Certain tasks, like
interpretting or list traversal are just naturally suited for
recursive languages. And from what I understand, functional languages
like LISP do not use call stacks and hence do not take a
performance/memory hit for recursion.

> No-one's saying recursion should always be avoided, since it's clearly
> essential for certain things (like Fractals) but for solving general
> programming tasks, it should be avoided like the plague wherever possible
> for the reasons that it is slow and consumes memory extremely quickly.

Actually, anything that can be expressed recursively can also be done
iteratively...the two are interchangable. Certain tasks are just
easier to conceptualize recursively.

> Given two solutions, one of which has one or two lines less code, but runs
> in exponential time instead of linear time, I'd go with the slightly longer
> one.

I agree, but making an iterative solution recursive does not change
the time complexity; if the original solution is linear, then the
recursive solution will also be linear, although, as you've said, will
take slightly more time because of the call stack issue.

> You've also overlooked the problem of memory usage in recursion, which is
> more often a far bigger problem than the issue of running time. Every
> recursive iteration requires some memory; either a few bytes or possibly
> more. Either way, passing a large input to a naive recursive function is an
> easy way to crash your system as you soon run out of stack space and/or heap
> space.

Definitely agree with this.

Anyway, I'm certainly not advocating that LISP-like languages should
become standard ;) But I have to say that learning Scheme really
changed the way I look at iterative problems, and I find thinking
about some things recursively very helpful, even if I implement them
iteratively.

-Chris