Why not use a better non-recursive method for creating your menu tree [eg modified preorder tree traversal], no recursion required, no complicated CTE required, just a simple select?
Although it is slightly more expensive / complicated to update / insert, menu's seem to be the perfect tree for that as the chances of the tree changing that often are relatively slim.