My suggestion is, create the generic id column with auto_increment first, to have a primary key in the table. Then create a unique key for both recipeId and stepNumber together so you won't have any duplicate combination of these 2 fields.
To be able to add multiple steps for a single recipe you will need to make sure none of recipeId, stepNumber or instruction is set to auto-increment. The only column set to auto_increment remains id.
So the table schema for these 2 tables would look like (ignore the category column)
CREATE TABLE `recipies` (
`id` int(11) unsigned NOT NULL AUTO_INCREMENT,
`name` varchar(30) NOT NULL DEFAULT '',
`category` enum('Salad','Dessert','Meat','Pastry') DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
CREATE TABLE `instructions` (
`id` int(11) unsigned NOT NULL AUTO_INCREMENT,
`recipeId` int(11) unsigned NOT NULL,
`stepNumber` int(11) NOT NULL DEFAULT '1',
`instruction` text NOT NULL,
PRIMARY KEY (`id`),
UNIQUE KEY `recipeId` (`recipeId`,`stepNumber`),
CONSTRAINT `instructions_ibfk_1` FOREIGN KEY (`recipeId`) REFERENCES `recipies` (`id`) ON DELETE CASCADE ON UPDATE NO ACTION
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
Let's add a record in the recipies table first
INSERT INTO `recipies` (`name`,`category`)
VALUES ('Pumpkin Pie','Pastry');
Then let's add a row
INSERT INTO `instructions` (`recipeId`,`instruction`,`stepNumber`)
SELECT
1,
'You will need plenty of pumpkins!',
IFNULL(MAX(`stepNumber`),0)+1
FROM `instructions`
WHERE `recipeId`=1
- 1 after
SELECT and 1 in the WHERE condition both refer to the row with id=1 in the recipies table
IFNULL(MAX(stepNumber),0)+1 will select the highest step number for that recipe (if it doesn't exist it will select "0") +1
Here's a SQL fiddle if you want to see it working.
[EDIT]
I have never needed using a combo for the primary key but apparently following works on InnoDB provided you don't already have a primary key in the table.
ALTER TABLE `instructions`
ADD PRIMARY KEY(`recipeId`,`stepNumber`)