Çok kabataslak yazdım ama test ettim. Aşağıdaki kod işinizi görür:

function footer_menu_walk($list=[],$children=false,$opt=[]){
    $string = (!$children ? '<div class="col">' : '<ul>') .  PHP_EOL;
    foreach ($list AS $menu){
        if($menu['parent'] == '0') {
            $string .= '<div class="primary-btn">';
        } else {
            $string .= '<li>'.PHP_EOL;    
        }
        
        $string .= $menu['title'];
        if($menu['parent']== '0') {
            $string .= '</div>' . PHP_EOL;
        }
        if($menu['children'])
            $string .= footer_menu_walk($menu['children'], true);
        if($menu['parent'] != '0') {
            $string .= '</li>' . PHP_EOL;
        } 
        
    }
    $string .= (!$children ? '</div>' : '</ul>') . PHP_EOL;
    return $string;
}
echo footer_menu_walk($footer_menus,false);