カテゴリ階層メニューのロジック

商品を検索した時に、検索結果の商品に紐づくカテゴリを下の表の様に表示したいです。

グルメ(99)
    お酒(50)
        ワイン(25)
        ビール(25)
    スイーツ(49)
        スナック(49)
メンズ(999)
    アウター(800)
        ジャケット(100)
        コート(700)
    トップス(99)
        シャツ(99)
    バッグ(100)

商品テーブルは下の様になっていて、カテゴリは小カテゴリに属すものも中カテゴリに属すものもあります。

integer item_id
integer category_id
varchar name

カテゴリテーブルは

integer category_id
integer parent_id
varchar name

の様になっています。

DBから取得した1次元の商品レコード配列（カテゴリID配列）からどのようにデータを作成するべきなのか（再帰処理になりそうなのはわかるのですが、まだ再帰処理をしたことがなく）、
また、MVCのモデルの中でループ処理をすると思うのですが、htmlもこのモデル内のループで作成するものなのでしょうか、それともモデル内でメニュー用データ配列を作成して、ビューで再度ループを回してhtmlを作成するものなのでしょうか？

ご教示頂けますとありがたく思います。
phpを使用しています。