No cooking recipe is restricted to either the Horde or the Alliance, but some are much easier to obtain for one of them than the other. This has several reasons - a recipe may be sold by a single faction-aligned NPC, rewarded from a faction-aligned quest, or perhaps dropped in in a zone especially populated by a specific faction. Often, these recipes are available from a neutral auction house.
As of Pilgrim's Bounty (2009), the total number of recipes actually in the game was 169. With the recent implements of Cataclysm, the number of recipes increased to 202 with the additional three new recipes from Cooking Trainers, two Feasts from guild achievements, and 28 from new Cooking Dailies. For new players, however, the number of obtainable recipes is slightly less; not only were the quests yielding some recipes removed in 4.0.3a, some vendors selling recipes were also removed due to change to their location (some of these recipes returned in 4.0.6). In addition, one recipe turned out to be bugged and was removed shortly after the expansion launched to be worked on (it later returned in 4.0.6 as well). Some others were returned in 4.1.0. 4.2.0 removed another recipe and returned two more, which places the number of recipes currently available to new chefs (non-Rogues, see below) at 200. Also, keep in mind that some recipes are only available during seasonal events. If you wish to determine which recipes you are missing, you can use the in-game mod Ackis Recipe List.
Patch 8.0.1(2018-07-17): Each expansion now has a separate profession skill bar, with smaller caps for each expansion, instead of one gigantic profession skill bar for all expansions put together
Patch 4.2.0(2011-06-28): The ability to make [Sporeling Snack]s has been removed from the game, and [Recipe: Sporeling Snack] in a player's inventory has been changed into a "Ruined Recipe", a gray quality item. Existing Sporeling Snacks in an inventory have also become gray items with no use, and their flavor text have changed from "Pets love sporeling snacks!" to "Pets hate sporeling snacks!" Thus, Sporeggar (faction) does not offer any cooking recipes past skill 300 anymore. Sporeling Snack has also been removed from [The Outland Gourmet]. [Recipe: Dig Rat Stew] and [Recipe: Undermine Clam Chowder] are now obtainable again. [Kibler's Bits] has been changed to just make your pet larger for 5 min, from previously increasing your pet's happiness (the happiness-system was removed in 4.1). Recipes (and related items) purchased with [Chef's Award] are now sold by NPCs in Darnassus, Ironforge, Thunder Bluff and Undercity in addition to the previous vendors in Stormwind City and Orgrimmar.