Build dynamic Mega Menu using recursion?

Question

I'm trying to create a Mega Menu using PHP and I'm having a problem getting the structure to output correctly. I've hard-coded the Mega Menu to test everything and it works fine, but obviously I need PHP to create it for me.

I have an example with the Mega Menu hard-coded so everyone can see what I'm trying to create:

http://www.libertyeaglearms.com/dev

Or here's the code:

DESIRED OUTPUT:

    <div id="wrapper">
        <ul class="mega-menu">
            <li class="mega-menu-drop">
                <a href="#">Firearms</a>
                 <div class="mega-menu-content">
                     <div class="column">
                         <h4>Rifles</h4>
                          <ul>
                              <li><a href="#">One</a></li>
                              <li><a href="#">Two</a></li>
                              <li><a href="#">Three</a></li>
                              <li><a href="#">Four</a></li>
                              <li><a href="#">Five</a></li>
                          </ul>
                      </div>
                      <div class="column">
                          <h4>Handguns</h4>
                          <ul>
                              <li><a href="#">One</a></li>
                              <li><a href="#">Two</a></li>
                              <li><a href="#">Three</a></li>
                              <li><a href="#">Four</a></li>
                              <li><a href="#">Five</a></li>
                          </ul>
                      </div>
                      <div class="column">
                          <h4>Shotguns</h4>
                          <ul>
                              <li><a href="#">One</a></li>
                              <li><a href="#">Two</a></li>
                              <li><a href="#">Three</a></li>
                              <li><a href="#">Four</a></li>
                              <li><a href="#">Five</a></li>
                          </ul>
                      </div>
                  </div>
              </li>
              <li class="mega-menu-drop">
                  <a href="#">Archery</a>
                  <div class="mega-menu-content">
                      <div class="column">
                          <h4>Bows</h4>
                          <ul>
                              <li><a href="#">One</a></li>
                              <li><a href="#">Two</a></li>
                              <li><a href="#">Three</a></li>
                              <li><a href="#">Four</a></li>
                              <li><a href="#">Five</a></li>
                          </ul>
                      </div> 
                      <div class="column">
                          <h4>Arrows</h4>
                          <ul>
                              <li><a href="#">One</a></li>
                              <li><a href="#">Two</a></li>
                              <li><a href="#">Three</a></li>
                              <li><a href="#">Four</a></li>
                              <li><a href="#">Five</a></li>
                          </ul>
                      </div>
                  </div>
              </li> 
          </ul>
      </div>

CURRENT OUTPUT: (very messed up. be warned, lol)

<div id="wrapper">
    <ul class="mega-menu">
    <li class="mega-menu-drop">
            <a href="#">archery</a>
            <div class="mega-menu-content">
                <div class="column">
                    <h4>compound</h4>
            <ul>
            <h4>bows</h4>
            <ul>
            </div>
        </li>
        <li class="mega-menu-drop">
            <a href="#">firearms</a>
            <div class="mega-menu-content">
                <div class="column">
                    <h4>rifle ammunition</h4>
                    <ul>
            <h4>ammunition</h4>
                    <ul>
            </div>
        </li>
            </ul>  
        </div>

HERE MY PHP:

$json = json_decode($category->buildDepartments(NULL),true);
function buildDepartments($array,$parent)
{
    $html = '';                 
    foreach($array as $category)
    {
        if($category['parent'] == $parent)
        {
             if($category['parent'] == NULL)
             {
                 $html .= '<li class="mega-menu-drop">' . "\n\t\t\t\t";
                 $html .= '<a href="#">'.$category['category_name'].'</a>' . "\n\t\t\t\t";
                 $html .= '<div class="mega-menu-content">' . "\n\t\t\t\t\t";                            
                 $html .= '<div class="column">' . "\n\t\t\t\t\t\t";
                 $html .= buildDepartments($array,$category['category_id']);                            
                 $html .= '</div>' . "\n\t\t\t";
                 $html .= '</li>' . "\n\t\t\t";
              }
              else
              {
                  $html .= buildDepartments($array,$category['category_id']);
                  $html .= '<h4>'.$category['category_name'].'</h4>' . "\n\t\t\t\t\t\t";
                  $html .= '<ul>' . "\n\t\t\t\t";

               }                        
          }
    }
    return $html;
}
print(buildDepartments($json,NULL));

HERE'S MY DATABSE:

EDIT AFTER BOUNTY

Building off what icktoofay suggested, I cannot seem to figure out the foreach() loops. The problem I'm getting is I get the department name inside the mega menu when I should see category and sub categories. I think the problem is I need to perform a loop with a specific parent id in order to get all the children, but I'm not really sure if that's the problem. Here's the code:

<div id="wrapper">
<ul class="mega-menu">         
    <?php $json = json_decode($category->buildDepartments(NULL)); ?>
    <?php foreach($json as $category): ?>
        <li class="mega-menu-drop">
            <a href="#"><?php if($category->parent === NULL){echo $category->category_name;} ?></a>
            <div class="mega-menu-content">                 
                <?php foreach($category as $subcategory): ?>
                <div class="column">
                    <?php if($category->category_id === $category->parent){echo '<h4>' . $category->category_name . '</h4>';}?>
                    <ul>
                        <?php foreach($category as $subcategory)
                        {
                            echo '<li>' . $category->category_name . '</li>';
                        }
                        ?>
                    </ul>
                </div>
                <?php endforeach; ?>                   
            </div>
        </li>
     <?php endforeach; ?>  
</ul>  
</div>

Answer 1

Since it's a fixed depth and the format for each level is different, recursion may not be appropriate. Additionally, putting everything in strings is inelegant. Instead, you may want to try weaving the HTML and loops together like this:

<div id="wrapper">
    <ul class="mega-menu">
        <?php foreach($categories as $category): ?>
            <li class="mega-menu-drop">
                <a href="#"><?php echo $category->name; ?></a>
                <div class="mega-menu-content">
                    <?php foreach($category->subcategories as $subcategory): ?>
                        <!-- and so on -->
                    <?php endforeach; ?>
                </div>
            </li>
        <?php endforeach; ?>
    </ul>
</div>

---

The code I've used here assumes you've already got it from a sort-of-flat-array to a tree-like structure. For example, if we've got a Category class:

class Category {
    public $id;
    public $parentID;
    public $name;
    public $parent;
    public $subcategories;

    public function __construct($id, $parentID, $name) {
        $this->id = $id;
        $this->parentID = $parentID;
        $this->name = $name;
        $this->parent = null;  // will be filled in later
        $this->subcategories = array();  // will be filled in later
    }
}

And an array of associative arrays like you might get from a database call (which we'll call $flatCategories), we can build a bunch of not-yet-connected Category instances like this:

$categories = array();
foreach($flatCategories as $flatCategory) {
    $categories[$flatCategory['id']] =
        new Category($flatCategory['category_id'],
                     $flatCategory['parent'],
                     $flatCategory['category_name']);
}

Then we can connect them all up into a hierarchal structure:

foreach($categories as $category) {
    if($category->parentID !== null) {
        $category->parent = $categories[$category->parentID];
        $category->parent->subcategories[] = $category;
    }
}

Now they're all linked up and we only care about keeping references to the roots:

$roots = array();
// This could, of course, be merged into the last loop,
// but I didn't for clarity.
foreach($categories as $category) {
    if($category->parentID === null) {
        $roots[] = $category;
    }
}

Now $roots contains all the root categories, and it's fairly simple to traverse. In my example at the top, I was assuming $categories had something similar to $roots in it.