I would find it very unintuitive that in a language I couldn't write a function that calls itself. That feels like an obvious thing (if we ignore all the implementation details).
When I first started programming I used recursion without knowing that it's called like that and I didn't expect it to be called in any special way at all.
Here's one way to see why recursion is special. Look at it from the perspective of implementing the language.
If your language doesn't have recursion, you can treat every local variable in your program as if it were a static global variable. It's local in terms of name scope, but you can give it a fixed blob of memory that you pick at compile time.
This is exactly what early Fortran compilers did. foo()'s local variables go here, bar()s go here, etc. You can do away with the stack entirely, I believe.
So, without recursion, you can make your entire program only use statically allocated memory. You can be sure it will never, ever ever run out of memory.
This meant you could support function calling without the need for a stack. However you can't directly support recursive (or co-recursive) functions. Nor could you ever do things like multithreading or shared libraries, although hose obviously weren't concerns at that time.
Today we think of the callstack as a fundamental part of the machine architecture, but at the time of algol-60 it was still a very contentious subject.
I am curious to know if modern Fortran compilers still use static allocation for local variables when compiling in Fortran 77 mode. I'd guess the cache advantages of keeping parameters close together in memory compensates for the extra work of manipulating the stack, but who knows...
> And this is what they wanted to remove because they wanted static allocation of procedure activation records.
From what I can tell with a bit of digging, machines/compilers back then didn't even use return stacks for subroutines. Instead, they used self-modifying code (!).
To return from a subroutine call, you'd do something like this:
1. When compiling a subroutine, add a JUMP followed by an address to the end.
2. When you call a subroutine, modify the code to change that address to point back to the callee.
3. Jump to the subroutine.
4. When it's done running, it hits the last JUMP and jumps back to the caller.
With this, you don't need any concept of a call stack at all. But it obviously prohibits recursion since the later call would trash the earlier one's return address.
I think even the most die-hard functional programming fans among us secretly know that this is a problem. It's why virtually every functional language implements tail call optimization, and why one of the earliest things that's taught to new students of functional programming is how to ensure that functions use tail recursion whenever possible. Sometimes we even go through some pretty impressive contortions because of this. Consider the case of continuation passing style.
The other is that a lot of people find recursion hard to understand. Others seem to naturally think in terms of recursion and think iteration is a headache. I'm not sure the two camps ever see eye to eye. It might be a brain wiring thing. Though perhaps practice rewires your brain - I wouldn't be surprised if making someone spend a decade writing mostly imperative code causes them to become more comfortable with iteration, and making someone spend a decade writing mostly declarative code causes them to become more comfortable with recursion.
I have spent a decade doing a mix of both. It really really really depends on the problem at hand what's easier to understand
Have to traverse a tree? Recursion.
Have to make a big thing out of small things? Recursion.
Have to add +1 to a bunch of numbers? Loop.