Sign a plaintext accepted by a secure function without revealing private key
The cryptographic primitive you're looking for is known as functional signature: in a functional signature scheme, there is a standard signature and verification key pair, as well as an algorithm to derive functional signature and verification keys, for any function $f$. The signature scheme then allows to sign any message $m$ in the range of $f$. The notion was introduced in this paper (see also the papers that cite it on Google scholar, for more recent constructions).

To get a solution to your problem out of this, let me call $P$ the program that checks whether $m$ is a good recipe. Define $f$ as follow: $f(m)$ returns $m$ if $P(m) = 1$, and the symbol $\bot$ otherwise. Now, if Bob (who knows the signing key for this function $f$) can sign a recipe $m \neq \bot$, this means that $m$ is in the range of $f$, hence that $P(m)=1$.

From your scenario, I suppose that you additionally have a function-privacy requirement: $f$ should not be publicly known (otherwise anyone could always check whether a recipe is nice, without the help of Alice), hence the functional signature key should hide $f$. This is known as function-private functional signatures, and is also defined and constructed in the paper I mentioned above. Such a scheme can be constructed for any polytime-computable function, assuming one-way functions and succinct non-interactive zero-knowledge arguments. The latter is a strong assumption, but we now have relatively efficient constructions of such arguments for functions of reasonable size (although probably not standardised implementations) - for example, this one was published a few days ago on ePrint, and seems quite efficient.

Note that none of this would be "incredibly efficient", but still fairly feasible.