It's more about having an easily verifiable limit on the size of the call stack. You can still use recursion in algorithms with this rule. It just forces you to allocate a separate stack to manage it.
I agree that the call stack limit is much more important in environments with tight memory but the rule is about the stack limit, not memory in general.
Edit: for 2. I obviously mean recursion as the class of algorithms, not as the property of the functions used to implement it.