Comment by ndriscoll

For basic structural recursion on finite data structures, all you're doing is case analysis and substitution (i.e. "plugging in" values). How is that gatekeeping?

Math majors cover hundreds of algorithms per semester often using recursion without thinking much of it. For that matter, same with "higher order functions" (e.g. derivative operators, or even just translation/scaling of a graph). Even in introductory calculus, students cover things like fixed points (e.g. I remember discussing d^4/(dx)^4 sin = sin almost immediately after introducing derivatives).

Thinking in terms of physical machines is useful for reasoning about performance, but seems like a distraction for learning to think logically/correctly, which seems like a more important first step?