Some problems are naturally better defined recursively than iteratively; the Minesweeper blank space uncovering algorithm is a prime example of that. "Push this button. If it's blank, execute push button for all surrounding buttons." Yet because the word "recursion" is primed with "hard" in the minds of undergrad students, some of them shut down on the word and don't attempt to figure out the problem. Instead they remember "recursion is hard, we'll cover that later".

Assuming subproblems are solved is a more sophisticated way of thinking about some recursive algorithms, like sorting. I don't think that is quite as naturally easy for most people. But I think the difficulty there is in the layering of concepts, not because the algorithm is recursive.