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.

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).

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.

Honestly, I don't know, Chad.  My suspicion is that, due to the nature of the
interpreter, it's all in heap.

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.

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.

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. 

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.

This response has been erased.

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.

This is the canonical example, and easy to optimize; but how about if you have
something that involves, say, a pointer structure?

Okay Dan you win. Your prize is a rubber chicken. Enjoy.

Can I choke it out?

Btw- the line about the thong made me laugh freakin' hard.

y nlucky

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)

Har har har.

Response not possible - You must register and login before posting.

- Backtalk version 1.3.30 - Copyright 1996-2006, Jan Wolter and Steve Weiss