Recursive Queries/Functions

[bluewalrus]

Can someone provide me some example when a recursive function or query is better to use than a for/foreach? I can't seem to find any online so far but have heard that recursive are more efficient so I'm interested to see the difference. Thanks.

[Nile]

One great example is here (http://www.dynamicdrive.com/forums/showpost.php?p=249655&postcount=4):



function echo_array($ar) {
foreach($ar as $key=>$a) {
if (is_array($a)) { echo_array($a); } //recursive loop
else { echo $key.': '.$a."<br />\n"; } //echo the string along with a line break
}
}
echo_array($my_array); //execute
How would you do the above without using a recursive function?

You can also use it for things like factorial:


function factorial($n){
return ($n == 0) ? 1 : $n * factorial($n-1);
// 0! = 1
// subtract one from $n and run it through factorial again, eventually $n will equal 0
}
//runs in 2.88486480713E-5


But then there's also:


function factorial($n){ //one
for($i = 0, $b = 1; $i < $n; $i++, $b *= $i);
return $b;
}
//runs in 2.71797180176E-5

function factorial($n){ // two, very similar to one
$b = 1;
for($i = 1; $i <= $n; $i++){
$b *= $i;
}
return $b;
}
//runs in 2.8133392334E-5

function factorial($n){ //three, also recursive
while($n != 1){
return $n * factorial($n-1);
}
return $n;
}
//runs in 3.21865081787E-5

function factorial($n){ //four
$b = 1;
while($n != 1){
$b *= $n;
$n -= 1;
}
return $b;
}
//runs in 3.00407409668E-5

[djr33]

I'm not sure about efficiency as a general property of recursive functions. I imagine it could be more or less efficient either way in terms of processing time. But if recursive functions make sense, they are probably more compact code.

The example nile posted above, from a thread I replied to yesterday (actually not the answer the OP was looking for, but still a good example here), is designed to print out information from an array. With a bit more work you could make it closely resemble the print_r() function.

The interesting thing about recursive functions is that they are actually required in some complicated situations. One example of this is when you want to list the contents of a directory and all of its subdirectories.
(The only possibility I can think of for getting around that requirement would be to use the goto operator of PHP > 5.3 [I think], but that seems messy and having not tried it I'm not confident it would work in all situations-- plus you'd need to deal with variable scope/instances which is already handled by functions... that helps a lot.)

If you attempt to program something like that using loops, you will need to hardcode a number of loops. So you might have 3 layers. Or 50. But with a recursive function all you need is 1, plus the recursive call to itself. Loop through a directory and for each item either return info about a file or recursively return the function for a subdirectory.

Thinking about it logically, recursive functions apply when you are dealing with a thing of type X in which there may be more things of type X that you want to handle the same way. And especially when the layering is unpredictable.


There are also other ways that recursive functions work, such as in Javascript. You create a function that checks the position of the mouse, then at the end it does settimeout() to run the same function again 50 milliseconds later. That's a slightly indirect version, but it's the same idea.


As a concrete example, here's a way to delete a directory and its contents:

function rmdir_recursive($dir) {
$d = opendir($dir);
while ($f=readdir($d)) { //go through each file
if (is_dir($dir.$f)) { rmdir_recursive($dir.$f); } //recursively run to delete subdirectory
else { unlink($dir.$f); } //delete a file
}
rmdir($dir); //remove this directory
}
NOTE: This assumes that you have permissions to delete for all of the files. It will probably give an error if you don't. I haven't tested that and it may or may not work in all cases-- I recommend using it only if you aren't worried about the files on your server. There are lots of practical examples here:
http://php.net/manual/en/function.rmdir.php
I wrote this one though so that it would be easier to read-- the examples there are more complicated.