I definitely don't think in terms of recursion (and I don't think I've seen it explicitly in a recipe!), but I'm not sure loops and interation are necessarily that intuitive, either. I learned programming at an early age and I still distinctly remember the period when loop constructs "made sense".
I can believe that recursion is even less easy to teach than iteration, but it may be that this is a pedagological issue, or that we have yet to work out the best way to convey or document computation.