|
|
Posted by "Richard Lynch" on 07/07/05 01:15
On Tue, July 5, 2005 3:08 pm, Rene Brehmer said:
> Documented research indicate that on Tue, 5 Jul 2005 14:07:21 -0700 (PDT),
> "Richard Lynch" wrote:
>
>> You'd think having done a zillion of these in my Grad School days would
>> have made more of an impression...
>>
>> Mostly it impressed me that recursion wasn't "cool" -- just another
>> "tool"
>> and one that you only should pull out 1% of the time.
>
> When we learned about recursion it took our teacher 15 minutes to come up
> with an example for what the heck it was good for ... and it wasn't even a
> good one (can't remember what it was).
There are some husband/wife functions in Mathematics/CS that are easiest
to define recursively...
I think there may even be proofs that certain functions CANNOT be
expressed as iterations, but that's digging through 10-20 years old
memories of courses I sometimes barely passed...
> I only use recursion when I need to output data stored in a tree format
> (you know, each child has a parent, each parent can have multiple
> children), otherwise I don't really know what to use recursion for.
If you're willing to spend the extra storage space for next/prev fields,
and if you INSERT/CHANGE less frequently than you OUTPUT, you can make a
"threaded tree" where essentially you use the inherent tree structure to
fairly quickly maintain a second "path" through the tree that's basically
a linked list.
Picture a tree that got TP'ed at Halloween, and you get the basic idea. :-)
I had a CS prof in grad school that must have hated recursion and loved
iteration, cuz we spent most of the semester converting recursive
functions into iterative for homework.
And, it must be admitted, the iterative solution was invariable MUCH
faster, and the code to do it was a little bit more work, but seldom was
it, like, totally gnarly. (To use the vernacular then current.)
> Mostly I have database queries where the results are built into 2-3 D
> arrays, and then used as the data the recursions work from ... found it to
> be the only way doing those trees fast when the data is variable and
> stored
> in a database...
There was a HUGE long-ass thread/argument on PHP-General (or maybe it was
just PHP back then) about Forum threads and whether they could be
converted to iterative or not, with or without limiting the number of
posts in a forum, with or without "too much" overhead in the SQL/DB/PHP
code and storage space.
It raged on for months, it seemed like, and quite a bit of inventive code
and invective messages were posted.
Several theories were shot down. I'm not sure anybody ever really got
into it deep enough to build a threaded tree in SQL or anything like
that... Since I had little interest in Forums, I only sorta followed the
whole thread anyway...
You may (or may not) find it useful if you can find the thread and read it.
Something like "forum thread limit recursion iteration" in MARC might turn
it up... If MARC goes back that far...
--
Like Music?
http://l-i-e.com/artists.htm
Navigation:
[Reply to this message]
|