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.

>I am curious what you mean that recursion is a natural way of thinking. Can you expand on that?

>I found that recursion made sense to me as well, but that seems like selection bias.

If you look at "describing", some things are naturally described in a recursive fashion. At least a significant part of thinking is encoding non-verbal ideas in natural language. These include the obvious factorial function, but also such things as the chain rule for derivatives, or the use of subordinate clauses in a sentence, such that a grammatically valid sentence may become arbitrarily long, this achieved by continually attaching further thoughts, the process of doing such being predicated on an underlying -- metahumor.

I think recursion is best explained by doing. This is the definition of the divisor function, you implement it like this, etc.