if you want to add the data in the increment order inside your associative array you can do this:
$newdata = array (
'wpseo_title' => 'test',
'wpseo_desc' => 'test',
'wpseo_metakey' => 'test'
);
// for recipe
$md_array["recipe_type"][] = $newdata;
//for cuisine
$md_array["cuisine"][] = $newdata;
this will get added to the recipe or cuisine depending on what was the last index.
Array push is usually used in the array when you have sequential index: $arr[0] , $ar[1].. you cannot use it in associative array directly. But since your sub array is had this kind of index you can still use it like this
array_push($md_array["cuisine"],$newdata);