|
Grex > Jelly > #54: PHP: A function calling itself from within | |
|
| Author |
Message |
nharmon
|
|
PHP: A function calling itself from within
| 
Oct 27 20:13 UTC 2006 |
Problem: My users are listed in a table called 'users' (unique eh?).
Relevant columns are userid and supervisorid. Each row defines a user
and indicates who that user's supervisor is. With me so far? Now on this
page I want to list a user's subordinates (everyone who has that him/her
listed as their supervisor), their subordinates' subordinates, and so on
for as many layers as is necessary. I also wanted it formated so each
person's subordinates would be indented relative to their supervisor.
At first I could only do this to limited degree. Then I wondered if it
would be possible for a PHP function to call itself. So I wrote one in
and behold...it worked.
function displaysubordinates($userid) {
$subordquery = mysql_query("SELECT * FROM users WHERE
supervisorid=$userid");
if ( mysql_num_rows($subordquery) > 0 ) {
while ( $row = mysql_fetch_assoc($subordquery) ) {
echo "<ul>\n";
echo "<li>".$row['lastname'].", ".$row['firstname']."</li>\n";
displaysubordinates($row['userid']);
echo "</ul>\n";
}
}
}
displaysubordinates($_SESSION["loggedinid"]);
This is probably elementary for most people. But I was surprised that it
let me do this.
|
| 15 responses total. |
cross
|
|
response 1 of 15:
|
Oct 27 20:42 UTC 2006 |
Congratulations. You have discovered the secret of recursion. However, there
is a potentially flaw: Suppose that there is an error in the data, and that
some user somewhere has a subordinate, or subordinate who has a subordinate,
or etc, such that the subordinate has the original user as a subordinate?
Ie, your data isn't a tree, but rather a graph. What would your program do
then? And, how could you fix it? (Hint: look for an associative data
structure).
|
herasleftnut
|
|
response 2 of 15:
|
Oct 28 01:56 UTC 2006 |
Dan, does PHP still use recursion on the stack? Or did they finally give some
kind of switch where you can make recursion on the heap? Nharmon, don't try
to think too hard about what I;m asking Dan. It's beyond youre limited IQ.
|
cross
|
|
response 3 of 15:
|
Oct 28 02:33 UTC 2006 |
Honestly, I don't know, Chad. My suspicion is that, due to the nature of the
interpreter, it's all in heap.
|
herasleftnut
|
|
response 4 of 15:
|
Oct 28 15:10 UTC 2006 |
Mayber later on today, I'll see if I can crash PHP (via recursion). It will
give me another reason to stay away from the language.
|
gull
|
|
response 5 of 15:
|
Oct 28 21:53 UTC 2006 |
If you recurse long enough you'll always crash somehow, in any
language. That's why you limit the maximum recursion depth somehow in
your code.
|
herasleftnut
|
|
response 6 of 15:
|
Oct 28 22:17 UTC 2006 |
I don't think so homegirl. I remember this crap when doing finite element
analysis in undegrad school. Let's see if I can get close. If you are using
a real programming langauge like Lisp, it has something that I think is called
tail end recursion. It basically turns the recursive code into interative
code. Hence, you go go like 2 million nodes deep and not run out of memory.
Under C, you can do this if you crank up the compiler optimization thingy.
I don't think PHP supports tail end recursion. However, I'm sure nhardon will
take the time to google this to prove me wrong. That is about the extent of
his skills.
Dammit, quit laughing and give me some support here. Oh gawd, the thong is
riding up my ass.
|
cross
|
|
response 7 of 15:
|
Oct 28 23:22 UTC 2006 |
Not exactly. Tail recursion is a special case; yes, tail recursive
procedures can be changed to semantically equivalent iterative procedures
(ie, a function call can be changed to a branch). I would tend to doubt
that the (probably rather simple) interpreter behind PHP is smart enough to
do that, but I don't really know, nor am I motivated enough to look it up
(honestly; PHP? Just go straight to Ruby, Python, or Perl. Well, perhaps
in Chad's case, he'd prefer pythong... I don't know).
But, more to the point, not every recursive procedure can be re-arranged
into a semantically-equivalent tail-recursive procedure, which means that
yes, at some point, the depth of the call tree can become significant.
Note: C compilers, due to the prevalence of pointer usage in C, often have
a pretty hard time doing tail recursion -> iteration optimization.
|
herasleftnut
|
|
response 8 of 15:
|
Oct 28 23:44 UTC 2006 |
This response has been erased.
|
herasleftnut
|
|
response 9 of 15:
|
Oct 28 23:47 UTC 2006 |
If I go something like:
#include <stdio.h>
double fact(double n) {
if(n == 0)
return(1);
if(n > 20000) {
fprintf(stderr, "out of range \n");
return 1;
}
return(n * fact(n-1));
}
int main(void) {
double x = fact(170);
printf("n fact is: %f \n", x);
return 0;
}
tail end recursion wont work because of the line
return(n * fact(n-1));
However, if I modify the code such that
return(fact(n-1));
and then crank up the gcc compiler optimization, the assembler code generated
by this function would be the same as if I had written it as an interative
function.
BTW, despite the fact that some grex users have fagged up Perl, I still will
use it over PHP on any given day. I feel Perl's benefits outweigh its
weaknesses. I considered maybe taking up Ruby, but the mailing list is
dominated by a bunch of nharmons.
|
cross
|
|
response 10 of 15:
|
Oct 29 01:29 UTC 2006 |
This is the canonical example, and easy to optimize; but how about if you have
something that involves, say, a pointer structure?
|
herasleftnut
|
|
response 11 of 15:
|
Oct 29 03:28 UTC 2006 |
Okay Dan you win. Your prize is a rubber chicken. Enjoy.
|
cross
|
|
response 12 of 15:
|
Oct 29 04:44 UTC 2006 |
Can I choke it out?
Btw- the line about the thong made me laugh freakin' hard.
|
naftee
|
|
response 13 of 15:
|
Oct 30 02:12 UTC 2006 |
y nlucky
|
remmers
|
|
response 14 of 15:
|
Oct 31 15:20 UTC 2006 |
Here's the index entry for the topic "recursion", found on p. 269 of
K&R, _The C Programming Language_, 2nd Edition:
recursion 86, 139, 141, 182, 202, 269
(This and other in-jokes from science & math books can be found at
http://tal.forum2.org/injokes)
|
cross
|
|
response 15 of 15:
|
Oct 31 17:38 UTC 2006 |
Har har har.
|