I Dont Get The Order Of Execution Of This Recursive Function

[meshealv]

HELP! HELP!. I CAN'T EAT IF I DON'T GET THIS CODE. By my previous understanding, due to the order of execution of recursive functions, when it is called it does not go on to execute the remaining part of the code but creates a new instance of the function in memory, the execution of the rest part of the function occurs at the last instance when the base case is fulfilled. In this light the code snippet

 

$row++;

}

// call display on each of this node's children

// note a node will only have children in its list if expanded

$num_children = sizeof($this->m_childlist);

for($i = 0; $i<$num_children; $i++)

{

$row = $this->m_childlist[$i]->display($row, $sublist); // Note that this is the recursive call, meaning this call to display() function is inside the display function as can be seen from the main code below

}

return $row;

}

will create several instances of the display() function which display the tree, but only return $row at last instance which in turn returns $row to the instance that calls it until it get to the first. But the writer of the book says the snippet of code sends $row from one call to the next and then the next. How is this possible when the return of $row occurs after the call to the recursive function. What am I getting wrong?

The entire class code is shown below:

<?php

// functions for loading, contructing and

// displaying the tree are in this file

class treenode

{

// each node in the tree has member variables containing

// all the data for a post except the body of the message

var $m_postid;

var $m_title;

var $m_poster;

var $m_posted;

var $m_children;

var $m_childlist;

var $m_depth;

function treenode($postid, $title, $poster, $posted, $children,

$expand, $depth, $expanded, $sublist)

{

// the constructor sets up the member variables, but more

// importantly recursively creates lower parts of the tree

$this->m_postid = $postid;

$this->m_title = $title;

$this->m_poster = $poster;

$this->m_posted = $posted;

$this->m_children =$children;

$this->m_childlist = array();

$this->m_depth = $depth;

// we only care what is below this node if it

// has children and is marked to be expanded

// sublists are always expanded

if(($sublist||$expand) && $children)

{

$conn = db_connect();

$query = "select * from header where parent = $postid order by posted";

$result = mysql_query($query);

for ($count=0; $row = @mysql_fetch_array($result); $count++)

{

if($sublist||$expanded[ $row['postid'] ] == true)

$expand = true;

else

$expand = false;

$this->m_childlist[$count]= new treenode($row['postid'],$row['title'],

$row['poster'],$row['posted'],

$row['children'], $expand,

$depth+1, $expanded, $sublist);

}

}

}

function display($row, $sublist = false)

{

// as this is an object, it is responsible for displaying itself

// $row tells us what row of the display we are up to

// so we know what color it should be

// $sublist tells us whether we are on the main page

// or the message page. Message pages should have

// $sublist = true.

// On a sublist, all messages are expanded and there are

// no "+" or "-" symbols.

// if this is the empty root node skip displaying

if($this->m_depth>-1)

{

//color alternate rows

echo '<tr><td bgcolor="';

if ($row%2)

echo '#cccccc">';

else

echo '#ffffff">';

// indent replies to the depth of nesting

for($i = 0; $i<$this->m_depth; $i++)

{

echo '<img src="images/spacer.gif" height="22"

width="22" alt="" valign="bottom">';

}

// display + or - or a spacer

if ( !$sublist && $this->m_children && sizeof($this->m_childlist))

// we're on the main page, have some children, and they're expanded

{

// we are expanded - offer button to collapse

echo '<a href="index.php?collapse='.

$this->m_postid.'#'.$this->m_postid.'"

><img src="images/minus.gif" valign="bottom"

height="22" width="22" alt="Collapse Thread" border="0"></a>';

}

else if(!$sublist && $this->m_children)

{

// we are collapsed - offer button to expand

echo '<a href="index.php?expand='.

$this->m_postid.'#'.$this->m_postid.'"><img src="images/plus.gif"

height="22" width="22" alt="Expand Thread" border="0"></a>';

}

else

{

// we have no children, or are in a sublist, do not give button

echo '<img src="images/spacer.gif" height="22" width="22"

alt="" valign="bottom">';

}

echo " <a name = $this->m_postid ><a href =

'view_post.php?postid=$this->m_postid'>$this->m_title -

$this->m_poster - ".reformat_date($this->m_posted).'</a>';

echo '</td></tr>';

// increment row counter to alternate colors

$row++;

}

// call display on each of this node's children

// note a node will only have children in its list if expanded

$num_children = sizeof($this->m_childlist);

for($i = 0; $i<$num_children; $i++)

{

$row = $this->m_childlist[$i]->display($row, $sublist);

}

return $row;

}

};

?>lt;

Edited December 13, 2012 by meshealv

[Christian F.]

Please use the [code][/code] tags around your code, as it helps make both your post and your code a lot easier to read. Also, if you either turn off the Rich Text editor (top left icon), or use the "paste plain text" (second from the right, top row) it'll preserve the indenting.

[meshealv]

OK, here it is:

 

 

 

By my previous understanding, due to the order of execution of recursive functions, when it is called it does not go on to execute the remaining part of the code but creates a new instance of the function in memory, the execution of the rest part of the function occurs at the last instance when the base case is fulfilled. In that light the code snippet

$row++;
}
// call display on each of this node's children
// note a node will only have children in its list if expanded
$num_children = sizeof($this->m_childlist);
for($i = 0; $i<$num_children; $i++)
{
$row = $this->m_childlist[$i]->display($row, $sublist); // Note that this is the recursive call, meaning this call to display() function is inside the display function as can be seen from the main code below
}
return $row;
}

will create several instances of the display() function which display the tree, but only return $row at last instance which is in turn returns $row to the instance that calls it until it get to the first. But the writer of the book says the snippet of code sends $row from one call to the next and then the next. How is this possible when the return of $row occurs after the call to the recursive function. What am I getting wrong?

 

The entire class code is shown below:

 

<?php
// functions for loading, contructing and
// displaying the tree are in this file
class treenode
{
// each node in the tree has member variables containing
// all the data for a post except the body of the message
var $m_postid;
var $m_title;
var $m_poster;
var $m_posted;
var $m_children;
var $m_childlist;
var $m_depth;
function treenode($postid, $title, $poster, $posted, $children,
$expand, $depth, $expanded, $sublist)
{
// the constructor sets up the member variables, but more
// importantly recursively creates lower parts of the tree
$this->m_postid = $postid;
$this->m_title = $title;
$this->m_poster = $poster;
$this->m_posted = $posted;
$this->m_children =$children;
$this->m_childlist = array();
$this->m_depth = $depth;
// we only care what is below this node if it
// has children and is marked to be expanded
// sublists are always expanded
if(($sublist||$expand) && $children)
{
$conn = db_connect();
$query = "select * from header where parent = $postid order by posted";
$result = mysql_query($query);
for ($count=0; $row = @mysql_fetch_array($result); $count++)
{
if($sublist||$expanded[ $row['postid'] ] == true)
$expand = true;
else
$expand = false;
$this->m_childlist[$count]= new treenode($row['postid'],$row['title'],
$row['poster'],$row['posted'],
$row['children'], $expand,
$depth+1, $expanded, $sublist);
}
}
}
function display($row, $sublist = false)
{
// as this is an object, it is responsible for displaying itself
// $row tells us what row of the display we are up to
// so we know what color it should be
// $sublist tells us whether we are on the main page
// or the message page. Message pages should have
// $sublist = true.
// On a sublist, all messages are expanded and there are
// no "+" or "-" symbols.
// if this is the empty root node skip displaying
if($this->m_depth>-1)
{
//color alternate rows
echo '<tr><td bgcolor="';
if ($row%2)
echo '#cccccc">';
else
echo '#ffffff">';
// indent replies to the depth of nesting
for($i = 0; $i<$this->m_depth; $i++)
{
echo '<img src="images/spacer.gif" height="22"
width="22" alt="" valign="bottom">';
}
// display + or - or a spacer
if ( !$sublist && $this->m_children && sizeof($this->m_childlist))
// we're on the main page, have some children, and they're expanded
{
// we are expanded - offer button to collapse
echo '<a href="index.php?collapse='.
$this->m_postid.'#'.$this->m_postid.'"
><img src="images/minus.gif" valign="bottom"
height="22" width="22" alt="Collapse Thread" border="0"></a>';
}
else if(!$sublist && $this->m_children)
{
// we are collapsed - offer button to expand
echo '<a href="index.php?expand='.
$this->m_postid.'#'.$this->m_postid.'"><img src="images/plus.gif"
height="22" width="22" alt="Expand Thread" border="0"></a>';
}
else
{
// we have no children, or are in a sublist, do not give button
echo '<img src="images/spacer.gif" height="22" width="22"
alt="" valign="bottom">';
}
echo " <a name = $this->m_postid ><a href =
'view_post.php?postid=$this->m_postid'>$this->m_title -
$this->m_poster - ".reformat_date($this->m_posted).'</a>';
echo '</td></tr>';
// increment row counter to alternate colors
$row++;
}
// call display on each of this node's children
// note a node will only have children in its list if expanded
$num_children = sizeof($this->m_childlist);
for($i = 0; $i<$num_children; $i++)
{
$row = $this->m_childlist[$i]->display($row, $sublist);
}
return $row;
}
};
?>

[meshealv]

Finally after a 3 hour brain storm, victory!!

Here's the explanation

 

 

Assuming we are in a child instance that has a for loop, the loop passes on the value of $row from out of it to the first instance, but if this instance does not have children and thus does not produce a loop, it has to return $row to the instance that called it, and that is still stuck in its for loop with the variable $row waiting to catch this value and set it to the next instance in the loop, or if looping has ended, return this value to the instance that called it............................................................................................... Until the whole tree is created and $row will be returned to the parent loop, which now executes the last line since its own looping has ended, and returns $row to the script that called it, where it is discarded.

 

Beautiful script.