This deletes referenced categories before the category that refers to them, which I think leaves open a window of brokenness, at least of referential integrity.

It might be better to do it the other way round:

  sub rec_delete {
    my $id = shift;
    my @kids = (... select id where parent = $id ...);
    delete($id);
    rec_delete($_) for @kids;
  }
[download]

Update: this is wrong - I was thinking "delete the categories this category refers to" rather than "delete the categories that refer to this category".