[RESOLVED] Recursive function - what am I doing wrong?

bodzan

Greetings PHP guru's!
It's been a while since I bothered you, but I have a problem that bothered me for a week and since I couldn't solve it on my own I need your wisdom and guidance with it...

It was a test I took when I applied for a web developer job in a firm in my home town and I since I never did anything like it I spent the whole week trying to solve it and came close but never quite finished it...

Here goes:

I got an array that I am to convert it in a navigation menu using whatever means I have at my disposal (PHP, then HTML, and CSS)...
here's the array:

$navigation = array(
	array('id'=>'1', 'name'=>'Tel', 'parent'=>'0'),
	array('id'=>'2', 'name'=>'Cam', 'parent'=>'0'),
	array('id'=>'3', 'name'=>'DVD', 'parent'=>'0'),
	array('id'=>'101', 'name'=>'LCD', 'parent'=>'1'),
	array('id'=>'102', 'name'=>'Plasma', 'parent'=>'1'),
	array('id'=>'103', 'name'=>'MiniDV', 'parent'=>'2'),
	array('id'=>'104', 'name'=>'DVD Camcorders', 'parent'=>'2'),
	array('id'=>'105', 'name'=>'Hoome theaters', 'parent'=>'3'),
	array('id'=>'1001', 'name'=>'20LC1RB-ZG', 'parent'=>'101'),
	array('id'=>'1002', 'name'=>'RZ-20LS3R-ZA', 'parent'=>'101'),
	array('id'=>'1003', 'name'=>'TX-20LA70P', 'parent'=>'101'),
	array('id'=>'1100', 'name'=>'TH-42PV80P', 'parent'=>'102'),
	array('id'=>'1301', 'name'=>'NV-GS37EP-S', 'parent'=>'103'),
	array('id'=>'1302', 'name'=>'NV-GS80EP-S', 'parent'=>'103'),
	array('id'=>'1401', 'name'=>'DCR-DVD106E', 'parent'=>'104'),
	array('id'=>'1402', 'name'=>'VDR-D310EP-S', 'parent'=>'104'),
	array('id'=>'1501', 'name'=>'SC-PT250E-S', 'parent'=>'105')
);

Sound's simple doesn't it? Well, the trouble is - I have to make it so that ti would first list only top level nodes that I like to call categories (those that have parent = 0) and when a user is to click on any of them only it's subcategories are to be shown on a page and then each subcategory can also be clicked on to show it's children.

Basically, from an array that has something like this

id     name                  parent
------------------------------------------------------
1      Sports                        0
2      TV program                 0
3      Football                       1
4      Basketball                   1
5      EURO 2008                  3
6      WorldCup 2010           3

I am to create a menu that would look like this:

   - Sports
   - TV Program

And then if I am to click Sports it should show me this:

    -Sports
        -Football
        -Basketball
    -TV Program

And if I am to click Football I would get this:

    -Sports
        -Football
            -Euro 2008
            -WorldCup 2010
        -Basketball
    -TV Program

Now, what I managed to do is to get subcategories to show when I click on a category - which is first step, cool. But when I click on a subcategory that is upper in list i.e. Football in my example I get Euro and WorldCup sub-subcategories, but Basketball won't show... Again, if I am to click on a Basketball, it's subcategories will show and the Football would show as well, but only in this case it would work... 🙁

Now, my code is this:

$crumb = array();
$nav = array();
function neez($array,$eed){
	global $crumb;
	global $nav;
	foreach($array as $value){
		if($value['parent']==$eed){
			$nav[$value['parent']][$value['id']] = "$value[name]";

		$crumb[$value['id']][$eed] = $value['name'];
		neez($array,$value['id']);
	}
}
return $nav;
}
$elem = array();

function find_children($eid){//
	global $navigation;
	global $iid;
	global $elem;
	global $id;
	while(list($k,$v) = each($navigation)){		
		if($v['parent']==$eid){
			if(in_array($v['id'],$iid)){
				$elem[$k] = $v;
				if($v['id']==$id){
					find_children($v['id']);
				}
			}
			else{
				$elem[$k] = $v;
			}
		}
	}
}


$arr = array();
$iid = array();
function find_crumb($array,$eed){
	global $arr;
	global $iid;
	while(list($k,$v) = each($array)){
			if(is_array($v)){
				$nw = (list($key,$value) = each($v));
				if($eed==$k){
					$arr[$k] = $value;
					$iid[$k] = $k;
					find_crumb($array,$key);
				}
			}
	}
}

And then, on a display end I have this:

neez($navigation,0);
krsort($crumb);
find_crumb($crumb,$id);
ksort($arr);
$path = "<a href=\"$page\" class=\"admin\">Home</a>";
while(list($k,$v) = each($arr)){
	$path .= "/";
	if($k == $id){
		$path .= "$v";
	}
	else{
		$path .= "<a href=\"$page?id=$k\" class=\"admin\">$v</a>";
	}
}
echo $path."<br />\n<br />\n";
reset($navigation);
foreach($navigation as $value){
	if($value['parent']==0){
		if(in_array($value['id'],$iid)){
			echo "<span class=\"big\">";
		}
		else{
			echo "<a href=\"$page?id=$value[id]\" class=\"adminC\">";
		}
		echo "$value[name]";
		if(in_array($value['id'],$iid)){
			echo "</span>";
		}
		else{
			echo "</a>";
		}
		echo "<br />\n";
		if(in_array($value['id'],$iid)){
			find_children($value['id']);
			while(list($ket,$vet)= each($elem)){
				echo "<a href=\"$page?id=$vet[id]\" class=\"adminM\">";
				echo "$vet[name]";
				echo "</a><br />\n";
			}
		}
	}
}

Of course, $page is page name I am using...
Also, here is a function to show path from where user is coming to each page and it is working like a charm...

Can anybody lend a hand for me here? I clearly need a fresh set of ideas as to what am I doing wrong and how to make it happen...

I delivered my failed solution to the employer, so the answer here will only have a academic purpose, for I am intrigued by this problem...

And if possible I would like to understand the solution and not just to have a new code that would work since I REALLY need to understand this and to change my sig somewhat... 🙂

Thanx in advance for bothering!

sneakyimp

Learning to write recursive functions requires you to start thinking about problems in a certain way. Recursive functions are extremely useful for rendering structures that repeat in some way. Think of things like trees, nested menus, a file system of directories which contain directories.

One thing I noticed is that your variable names make no sense to me. I guess you're serbian so they probably make perfect sense to you but I'm going to use English names.

First, I'll write a function that looks at the big array of menu items and, given a parent id, tells me which ones are children of that parent_id

function get_children($menu_array, $parent_id) {
  $children = array();
  foreach($menu_array as $menu_item) {
    if ($menu_item['parent'] == $parent_id) {
      $children[] = $menu_item;
    }
  }
  return $children;
}

That should come in handy because it will make the rest of our code simpler.

I should also make a function which retrieves a the menu item corresponding to a particular id. Note that I only realized that I needed these functions once I started writing the recursive function below

function get_menu_item($menu_array, $id) {
  foreach($menu_array as $menu_item) {
    if ($menu_item['id'] == $id) return $menu_item;
  }
}

You might be thinking "I need a function to render my tree. I should be able to give it an array of all the items and it should render it". This is where you need to start training your mind to think recursively. You should be thinking "Rendering the whole tree is a repeatable process of rendering every branch of the tree, then rendering all the child branches of that branch. I can think of the trunk as merely the biggest branch with parent_id=0".

So I need a 'render_menu' function. It will output the HTML I need for one particular branch and then it will call itself to repeat that process on the child menus that belong to that particular branch. I should be able to give it the menu items data and also the id of the branch I am rendering.

function render_menu($menu_array, $menu_id) {
  // step 1, grab the menu item we are trying to render
  $menu_item = get_menu_item($menu_array, $menu_id);

  // step 2 start the HTML for this menu item
  echo '<div style="border:1px solid black; margin-left:5px;">';

  // step 3, output the name of this menu item
  echo $menu_item['name'];

  // step 4, grab all the children of the current item (if any exist)
  $children = get_children($menu_array, $menu_id);

  // step 5 render those children
  foreach($children as $child) {
    render_menu($menu_array, $child['id']);
  }

  // step 6 finish the HTML we started previously
  echo '</div>';
}

Unfortunately, we can't just feed our entire menu array into that function and spit it out because there is no menu item with an id of zero. We have to grab the top-level items ourself--but this should be easy because we have the function to grab children. This should render a basic version of the menu.

$root_children = get_children($navigation, 0);
foreach($root_children as $root_child) {
  render_menu($navigation, $root_child['id']);
}

You'll probably need to put in some extra DIV elements so that you can separate a menu item's name from its children and also some javascript to show or hide the child div when you click on a particular name.

bodzan

First of all - thank you for bothering yourself with this!

And of your code: it works as it should but you misunderstood me in my intentions - well, as I said not mine, but the guy that tested me...

The point is not to show the whole tree, but to have only categories listed (those that have parent = '0') and only AFTER you click on any of it to show you it's children, and if you click on any of the children to show you their children as well...

So fist I would have:

- parent1
- parent2
- parent3
- parent4
- parent5
- parent6
... etc

Then after a click on say parent4:

- parent1
- parent2
- parent3
- parent4
     - child4.1
     - child4.2
     - child4.3
- parent5
- parent6
... etc

And after click on say child4.2:

- parent1
- parent2
- parent3
- parent4
     - child4.1
     - child4.2
          - grandchild4.2.1
          - grandchild4.2.2
          - grandchild4.2.3
          - grandchild4.2.4
     - child4.3
- parent5
-parent6
... etc

Also these have to be made in PHP and not JavaScript, so all these should be shown in a single page and depending on an id that I pass to the page the menu would create itself like what I shown...

My code shown above works in first two steps, but not the last since, although it lists grandchildren of a clicked child element, it disregards all the children bellow selected one, so if I click on a child4.2 I would see

- parent1
- parent2
- parent3
- parent4
     - child4.1
     - child4.2
          - grandchild4.2.1
          - grandchild4.2.2
          - grandchild4.2.3
          - grandchild4.2.4
//here is missing child4.3 which my code wouldn't show for some reason
- parent5
-parent6
... etc

Basically, although I gather that I made an error somewhere in start of the code my code is up right to this last situation...
Oh, and one more thing: If I were to click on a child4.3 it would show me everything that is needed... It just doesn't work if the clicked child is not the last in selection...

sneakyimp

Sounds to me then that you should determine the breadcrumb for the menu item you are currently viewing (this would also be a recursive function) and store all the parent items of the current menu item in an array called 'open items'. You could then modify the render menu function I wrote to only render the children of the current menu item it its id is in the 'open items'.

bodzan

Thanx bro'!

I solved this problem with your latest input and it was a lot simpler using your code than it was with mine... 😃

The solution is here for people who ever encounter a problem like this:

$id=0;
if(isset($_GET['id']) && is_numeric($_GET['id'])){
	$id = intval($_GET['id']);
	if(!in_array_multi($id,$navigation)){
		$id = 0;
	}
}
function get_children($menu_array, $parent_id) {
  $children = array();
  foreach($menu_array as $menu_item) {
    if ($menu_item['parent'] == $parent_id) {
      $children[] = $menu_item;
    }
  }
  return $children;
} 
function get_menu_item($menu_array, $id) {
  foreach($menu_array as $menu_item) {
    if ($menu_item['id'] == $id) return $menu_item;
  }
} 

function render_menu($menu_array, $menu_id) {
	global $id;
	global $page;
	global $open_items;
  // step 1, grab the menu item we are trying to render
  $menu_item = get_menu_item($menu_array, $menu_id);

  // step 2 start the HTML for this menu item
  echo "<div style=\"margin-left:5px;\">\n";


  if($id!=$menu_id){//this is a part that I added to make current page without a link
	  echo "<a href=\"$page?id=$menu_item[id]\" class=\"admin\">";
  }



  // step 3, output the name of this menu item
  echo $menu_item['name'];



  if($id!=$menu_id){//there shouldn't be closing tag if there wasn't opening tag
  	echo "</a>";
  }



  // step 4, grab all the children of the current item (if any exist)
  if(in_array($menu_id,$open_items)){
  $children = get_children($menu_array, $menu_id);

  // step 5 render those children
  foreach($children as $child) {
    render_menu($menu_array, $child['id']);
  }
  }
  // step 6 finish the HTML we started previously
  echo "</div>\n";
}

function find_crumb($eed){
	global $navigation;
	reset($navigation);//I need this to reset the array to the original listing since it gets passed every time this function passes and this reset allows me to reuse the array
	global $arr;
	global $iid;
	while(list($k,$v) = each($navigation)){
		if(is_array($v)){
			$nw = (list($key,$value) = each($v));
			if($eed==$v['id']){
				$arr[$v['id']] = $v['name'];
				$iid[] = $v['id'];
				if($v['parent']>0){
					find_crumb($v['parent']);
				}
			}
		}
	}
}


function in_array_multi($what, $array){
	if(!is_array($array)){
		return $what == $array;
	}
	foreach($array as $value){
		if(in_array_multi($what, $value)){
			return true;
		}
	}
	return false;
}

And in the BODY section of the page there is following code


$path = "<a href=\"$page\" class=\"admin\">Home</a>";
$open_items = array();
if($id!=0){	
	find_crumb($id);
	ksort($arr);
	while(list($k,$v) = each($arr)){
		$path .= "/";
			$open_items[] = $k;
		if($k == $id){
			$path .= "$v";
		}
		else{
			$path .= "<a href=\"$page?id=$k\" class=\"admin\">$v</a>";
		}
	}
}
echo $path."<br />\n<br />\n";
$root_children = get_children($navigation, 0);
foreach($root_children as $root_child) {
  render_menu($navigation, $root_child['id']);
}

And that is it...

Basically I used almost all of Snaky's code and just added find_crumb function and modified the render_menu function as he suggested...

Thanx again... It all makes sense now...