The concept of software will obviously be harder to explain to someone unfamiliar with computers - I think the trick is relating it to something they do personally understand, and this is where the analogy to recipes and cooking can be useful: most people are familiar with the idea of carefully following the steps in a recipe in order to cook something.
The problem with the cooking analogy -- which has always bugged me -- is that there aren't complicated control structures in cooking. Most recipes don't contain loops or conditionals.
I think a better, but still pretty bad, analogy is putting together Ikea furniture from the cartoon instructions in that those things usually have something like a for-each loop: do this set of instructions for each of the table's four legs, etc.
An even better analogy, although more arcane, is folding origami from diagrams. In this case there's an actual formal language in play albeit a visual one. Origami diagrams have been standardized since the 60's or so. However, they don't ever contain anything like an if-statement. Is there any simple activity that does contain something like an if branch?