Forum Moderators: coopster
At what 'depth' does it become noticably slow? If I'm only going, say, ten levels deep, is it painfully noticable?
1 - What is being stored at each node of the tree.
In php: what gets returned by each call of the recursive function.
Obviously, returning a small string will use less memory than if you were returning a large array.
2 - How broad the tree is.
You say that the tree will be ten levels deep. Well, if there is only one branch per level there should be no problem - there'll only be 10 nodes. In php: 10 calls to your recursive function (make sure each one doesn't require database access!).
If there are two branches per level, that's 1023 nodes in total: your function will get called 1023 times!
If there are 4 branches per level there'll be almost 350,000 nodes: definitely a problem!
Presumably you can not write it using tail recursion [cis.ksu.edu] (that is a recursive function that has nothing to process after the recursive call) or you would be writing it as a loop.
If you can make your function so that it is properly tail-recursive and you have good garbage collection (can't vouch for PHP here) it should be no different than an a loop. In actuality, both are iterative processes.
Is that recursion? ;-]
Then again, most of the times I use recursion, it doesn't go betond 50 levels or so.
I read about this a while ago, and was assured that PHP has very good internal "garbage cleaning", which is nice to know. As the scope of a function ends, all the temporary memory used by it are cleared, notwithstanding any unwarranted use of the GLOBAL keyword.
I don't have scientific measurements, but I can relate my experience with a few examples;
I have a recursive "tree builder" that looks through a database and displays a simple navigation hierarchy, it has about 1200 nodes and each one displays a URL and some text in nested tables. It takes about 2 seconds to complete. Nothing is put into arrays, so it's fairly easy on the memory resources.
Another one is a forum with threaded replies, which often have between 20-200 items, those are stored temporarily in associative arrays at runtime, but I've never noticed any problems, and the scripts usually take under 1 second.
And once I did create a recursive script to create a "maze" - i.e. it was a pathfinding algorithm that designed random uncrossing paths through a 2-dimensional grid. That loop actually went quite deep - probably 100 levels or more - but it didn't have any problems, and executed fairly quickly, considering the complexity of what it was doing.
Yet another example was a link-following spider, which recursively follows every link on a page and stores their contents in a keyword database table. (it provides a very speedy site search lookup table)
First attempts to run it always timed out after 5, 10, 15, 60 minutes... so I revamped the code and made it into a page that reloads itself every n iterations (I usually set it to 15 at a time). That script usually takes between 13-16 *hours* to run, so I start it on Friday at 5:00pm and let it run over the weekend.
I realize this advice is probably of little practical use to you, but I can tell you that you probably won't know how efficient or speedy your recursion is until you try it. Put a microtimer on the script to display the start and end times, and tweak your code in different ways to make it run as efficiently as possible.
good luck!
I don't even notice the time it takes, and on top of it all, I'm caching most of the pages that use it so if it was to be a problem it would be minimized...
I've done much recursing in my time
I know what you mean. Just a few minutes ago I was recursing something I had cursed only a short time ago.
As for the link provided....
Tail recursion is a good thing to know about. If it is at all possible to write a prgram so that it is tail recursive and the programming language in question has good garbage collection, this gives the simplicity/elegance of recursion with the overhead of looping.
In languages like Scheme, there are no looping constructs so everything you do with for and while in PHP must be done with recursion. If you do just a little programming in Scheme you get used to looking for the tail-recursive solution. I believe in PHP anything that would be tail-recursive could be rewritten as a loop, but not always as simply.
Tom
