IMO, the two challenging parts of recursion are: First, realizing that you can have separate instances of functions at the same time -- different stack frames.

IMO, the two challenging parts of recursion are: First, realizing that you can have separate instances of functions at the same time -- different stack frames. Making the mental leap from "the content of x in function f" to "the content of x in f(0), and also the content of x in f(1)" is a leap of abstraction, but not necessarily a tremendous one. Second, mentally modeling recursion when it gets complicated. Simple recursive cases are easy to model in your head, because either there is little state to keep track of, or because you can extrapolate the pattern between function calls, mentally compressing the state of the whole call tree. Tail-call optimization, for example, is really easy to mentally model because you only have to keep track of the state of one function's variables at a time -- unless you start passing continuations or thunks into your function calls, in which case you're carrying a stack of unlimited complexity into each function call. It's still just a function call, with the same number and types of arguments, but now one or more of those arguments contains turing-complete, recursive programs of unlimited complexity. This similar to the worst-case mentally-complicated recursion without TCO, where you can build a complex graph of function calls, scopes, shared data accesses, and mutated copies of what used to be the same data, that can all be present at once, and where you might need to keep track of all of them in order to track down and understand something that you need to understand. You can, of course, build similarly tangled-up structures in a purely-iterative manner, but the upside is that the complexity will be confined to the data state -- there will be no call tree to mentally model, and no need to track variable scope. --- Shorter version: if the efficiency and elegance of recursion (with appropriate compiler/runtime optimizations, like TCO) is like zip compression for your mental model of code complexity, then there exist recursive-program equivalents of zip bombs. --- Even shorter version: recursion itself isn't hard to reason about, but recursive programs can be very hard to reason about