your custom post type will likely work if you visit your permalinks page and save, which forces a flush of the rewrite rules. however, you probably won’t be able to get the taxonomy to work using the same slug, custom post types seem to supersede taxonomies if they share a slug. anyway, it would probably be a big performance hit even if it did work, WP would have to generate a rewrite rule for every term or post you create, or look in two different places for every request.
also- your register_taxonomy should be wrapped in a function that gets called on init, like your recipes_register function.