Using recursion to build navigation

Question

I'm building navigation for a site and for the life of me I can't figure out recursion. I have all my data stored via MySQL using this design:

enter image description here

I've read several links on how recursion works and I must be slow because it's difficult for me to grasp. I've tried to write something and I know it is not even close to what I really need, but it's a start:

PDO

public function viewCategories()
{
    $viewSQL = "SELECT * FROM categories";  
    try
    {
        $pdo = new PDO('mysql:host=localhost;dbname=store','root','');
        $pdo->setAttribute(PDO::ATTR_ERRMODE,PDO::ERRMODE_EXCEPTION);
        $categoryVIEW = $pdo->prepare($viewSQL);
        $categoryVIEW->execute();
        $array = $categoryVIEW->fetchAll(PDO::FETCH_ASSOC);
        $categoryVIEW->closeCursor();
        $json = json_encode($array);
        return $json;
    }
    catch(PDOexception $e)
    {
        return $e->getMessage();
        exit();
    }
}

Recursion

$return = json_decode($category->viewCategories(),true);

function buildNavigation($json)
{
    foreach($json as $item)
    {
        if($item['category_id'] === $item['parent'])
        {
            print('<li>'.$item['category_name'].'</li>');
            if($item['category_id'] === $item['parent'])
            {
                print('<li>match'.$item['category_name'].'</li>');
                buildNavigation($json);
            }
        }
}
buildNavigation($return);

as expected this will never enter the condition. I did try to figure this out on my own since this is a good thing to have knowledge of, but I guess it's beyond my mental capacity :(

Thanks for having a look :)

UPDATE

I know this has been answered already, but is there a way I can do this to build an associative array? I have been playing around with a function that ALMOST works for me that I got from HERE, but it adds an extra array that I do NOT want.

Method

private function buildCategories($array,$parent)
{
    $result = array();
    foreach($array as $row)
    {
        if($row['parent'] == $parent)
        {
            $result[$row['category_name']] = $this->buildCategories($array,$row['category_id']);
        }
    }
    return $result;
}
$json = json_encode($this->buildCategories($array,NULL));
return $json;

I want this:

{"reloading":{"components","presses and dies","tumblers & scales","tools & accessories","shotshell reloading"}

but what I get is this:

{"reloading":{"components":[],"presses and dies":[],"tumblers & scales":[],"tools & accessories":[],"shotshell reloading":[]}

MySQL doesn't support recursive functions, so it is not well suited to this adjacency list model of storing hierarchical data. You ought to consider restructuring your data to use either nested sets or a transitive closure table. See [this answer](http://stackoverflow.com/a/192462/623041) for more information. — eggyal, Oct 21 '12 at 21:26
Hey eggyal, can't I accomplish this through PHP rather than MySQL? I figured I could iterate through my PDO output? — Mike, Oct 21 '12 at 21:32
Hm, that's good to know. I guess I'm traveling down the wrong path. — Mike, Oct 21 '12 at 21:37
Recursion means that the function *calls itself* from within the function, typically depending on certain conditions. Your `buildNavigation` function calls `buildCategories` - where's the code for that function? — random_user_name, Oct 21 '12 at 21:37
Do you only have 2 levels of navigation? If so, you don't need recursion. — Maxime Morin, Oct 21 '12 at 21:38
Whoops, forgive me. I wrote the wrong function name. I will update, thanks. — Mike, Oct 21 '12 at 21:38
@ Maxime Morin - Yep, all I have is one parent and one child. — Mike, Oct 21 '12 at 21:40
Well there could be infinite amount of children, but the children will only have one parent. — Mike, Oct 21 '12 at 21:41
That loop/recursion thing going on there looks pretty infinite too.. The function calls itself with the same argument. — cerealy, Oct 21 '12 at 22:01

score 17 · Accepted Answer · answered Oct 21 '12 at 22:09

17

Here's an example with recursion.

function buildNavigation($items, $parent = NULL)
{
    $hasChildren = false;
    $outputHtml = '<ul>%s</ul>';
    $childrenHtml = '';

    foreach($items as $item)
    {
        if ($item['parent'] == $parent) {
            $hasChildren = true;
            $childrenHtml .= '<li>'.$item['category_name'];         
            $childrenHtml .= buildNavigation($items, $item['category_id']);         
            $childrenHtml .= '</li>';           
        }
    }

    // Without children, we do not need the <ul> tag.
    if (!$hasChildren) {
        $outputHtml = '';
    }

    // Returns the HTML
    return sprintf($outputHtml, $childrenHtml);
}

print buildNavigation($items);

That script produces the following output :

<ul>
    <li>Menu 1</li>
    <li>Menu 2
        <ul>
            <li>Sub Menu 2.1</li>
            <li>Sub Menu 2.2</li>
            <li>Sub Menu 2.3
                <ul>
                    <li>Sub Menu 2.2.1</li>
                    <li>Sub Menu 2.2.2</li>
                    <li>Sub Menu 2.2.3</li>
                </ul>
            </li>
        </ul>
    </li>
    <li>Menu 3</li>
</ul>

answered Oct 21 '12 at 22:09

Maxime Morin

2,008
1
21
26

THERE IT IS! Nice job! I'm not sure if I will ever understand this, but thank you very much :) – Mike Oct 21 '12 at 22:14
Quick question, would it be better to do this in my class then pass it formatted? – Mike Oct 21 '12 at 22:16
I'm not sure what you mean by formatted, but the buildNavigation function should be in a MenuHelper, HTMLHelper or somewhere close to your view (HTML). I wouldn't put this in a model or data object. – Maxime Morin Oct 21 '12 at 22:18
Great awnser @MaximeMorin only i have one question, how can you seperate the parent
– Jarno van Rhijn Jan 18 '13 at 12:09
@JarnovanRhijn Where we initialize the `$outputHtml` variable, you can check if `$parent == null` and change the content of `$outputHtml` accordingly. For example, if `$parent == null` then `
` else `
`. This should only mark the root UL with a parent class. I haven't tested this, let me know how it goes.
– Maxime Morin Jan 18 '13 at 14:35
working for me....was tired...finally google shown ur question url....hats off to u – Chintan_chiku Mar 14 '14 at 11:43

score 0 · Answer 2 · answered Nov 21 '13 at 22:47

I have the same above code with little bit modification, so that a user can apply different css on each level of menu, now its showing classes of sub menu like child-class1 when its in 1st sub menu , and it will show child-class2 when its in 2nd sub menu and so on...

  <?php
 function buildNavigation($items, $parent = NULL, $n=NULL)
    {
$hasChildren = false;
if ($parent == NULL)
{
    $level=0;
    $outputHtml = '<ul class="parent-class">%s</ul>';
}
else
{
    if($n==NULL)
    {
        $level=1;
    }
    else
    {
        $level=$n;
    }
    $outputHtml = '<ul class="child-class'.$level.'">%s</ul>';  
} 
$childrenHtml = '';
foreach($items as $item)
{
    if ($item['parent'] == $parent) {
        $hasChildren = true;
        $childrenHtml .= '<li><a href="/'.$item['slug'].'">'.$item['ptitle'].'</a>';
        $next = ++$level;
        $childrenHtml .= buildNavigation($items, $item['pageid'],$next);         
        $childrenHtml .= '</li>';           
    }
}

// Without children, we do not need the <ul> tag.
if (!$hasChildren) {
    $outputHtml = '';
}

// Returns the HTML
return sprintf($outputHtml, $childrenHtml);
}
echo  buildNavigation($ppages);
?>

it will show out put like this

    <ul class="parent-class">
      <li>
        <a href="http://example.com/page-1">page 1</a>
           <ul class="child-class1">
              <li>
                 <a href="http://example.com/this-is-child-page">this is child page</a>
                  <ul class="child-class2">
                     <li>
                        <a href="http://example.com/child-of-child">child of child</a>                 </li>
                  </ul>
              </li>
          </ul>
      </li>
 </ul>

I would like to thanks Mr @Maxime Morin.

Using recursion to build navigation

2 Answers2

Linked