Che bell'esecizietto! Adorabile la ricorsione, mi sono divertito a risolverlo (anche se c'è voluto più tempo a mettere i doppi apici intorno all'array recordset che a scrivere il codice):

Il codice prescinde dalla profondità delle categorie.
Codice PHP:
<?php
//diciamo che esegui una query select * from menu order by struttura
$recordset=array(
"elettrodomestici",
"elettrodomestici>cucine>elettriche",
"elettrodomestici>cucine>gas",
"forni",
"forni>da incasso",
"forni>da incasso>a gas",
"forni>da incasso>elettrici",
"forni>esterni",
"forni>esterni>a gas",
"forni>esterni>elettrici",
"televisori",
"televisori>LED",
"televisori>LED>32 pollici",
"televisori>LED>40 pollici",
"televisori>plasma",
"televisori>plasma>32 pollici",
"televisori>plasma>40 pollici"
);

function addToMenu(&$menu,$voci){
    if(!is_null($voce =  array_pop($voci))){        
        if(!isset($menu[$voce]))            
            $menu[$voce]=array();        
        addToMenu($menu[$voce],$voci);
    }
}

function showMenu($menu,$indent){
    foreach ($menu as $key => $value) {
        printf("%{$indent}s","");
        printf($key."
");
        if(is_array($menu[$key]))
            showMenu($menu[$key],$indent+4);        
    }
}

$menu=array();
foreach ($recordset as $value) {//qui sostituisci con mysql_fetch_array
    $voci =  array_reverse(explode(">", $value));
    addToMenu($menu,$voci);
}

echo "<pre>";
showMenu($menu,0);
echo "</pre>";

?>
l'output prodotto:
codice:
elettrodomestici
    cucine
        elettriche
        gas
forni
    da incasso
        a gas
        elettrici
    esterni
        a gas
        elettrici
televisori
    LED
        32 pollici
        40 pollici
    plasma
        32 pollici
        40 pollici