Recursion is natural and easy to understand when the argument of the function is a recursive data structure, and the cases are patterns on the constructors. These are natural and useful cases, much better than the alternative. Starting with misguided examples like factorial is demotivating.

You're not wrong, but I think there's still something missing in terms of how to get from there to a place where people can see how (and more importantly, how to recognize _when_) to apply the concepts towards what they work on after they've learned the basics. In my first semester in college, I took a course that was half in OCaml and half in Java. During the first half, we used recursion extensively, modeled everything via closures rather than objects, and generally learned to think about things functionally. Then when we transitioned to Java, where we didn't apply any of that and instead used objects and for loops and imperative logic. That was the last class required for CS majors that used functional programming; after that, all of the requirements were either Java, C, or didn't use any programming language (but maybe used pseudocode, like our algorithms course). I personally took a number of other functional language courses as electives, like one where we learned Haskell, one about the theory of programming languages that used Coq, and a compilers course that used OCaml again, and while I wasn't the only one, it certainly wasn't a majority who went out of their way to take courses like this.

The first time I tried to implement something recursively in C++ at my job after college, my more senior teammates were concerned about whether we could safely assume that all of the different compilers would correctly optimize the tail recursion to avoid blowing up the stack, and they preferred rewriting the logic to be iterative rather than spend time trying to figure that out. This was something I was vaguely aware of as a real-world issue, but it hadn't occurred to my naive junior engineer mind that I couldn't just assume that prestigious "professional" compilers like GCC and Clang and MSVC wouldn't take care of this for me when I never had to worry about it in OCaml. After all, everyone in the world seemed to writing code in C++ with one of these compilers, and the OCaml toolchain didn't exactly have a glowing reputation in my mind when the only place I had heard of using the language didn't even use the default standard library!

I'm not saying that I think this is necessarily a good way to teach recursion generally, but I definitely think there's room for resources like this that help bridge the gap between understanding how recursion works in the best possible environment for it and showing how it works (warts and all) for specific real-world ecosystems.

Call stacks help form a mental model for some people. It’s a way to help get an initial grip on the topic, one of many. Teaching usually involves many simplified models which in my experience helps a lot with initial understanding.

We don't need detailed call stacks to help with understanding recursion. Just the somewhat more abstract concept of a procedure/function activation. Calling a function suspends the caller and create a new activation for the callee. When the callee returns, it's activation is disposed and suspended color resumes in its original activation.

The point was pedagogical, sometimes the “best” explanation just doesn’t work for a student. Some might get confused about where the state of the caller goes and get hung up.