The newer Android versions normally try and restore the stock "recovery" partition after each boot, unless you have specifically taken action to prevent that. This could be what "saved" you.

So.. your N4 may (or may not) have the stock recovery on it now.