No doubt there ways to do it in a pure functional language -- but that requires a bit of thought. Compared to that difficulty, this business of return values seems trivial.
Worse, a language that forces people to Do The Right thing, might be acceptable for experienced programmers who want to work within that limitation. But when given to student, it just encourages closed minded rule-following.
Citation needed. I find the safety net of that kind of language empowering: I can concentrate on thinking about the actual problem, and be confident that the language won't let me shoot myself in the foot.
I think experience shows that freedom to do the wrong thing frequently leads to the wrong thing happening. There are many case studies to be found in security and concurrency.
No problem. Traditional loops with mutable variables translate straight-forward to tail recursive calls, if you want to write your algorithm like that.
Though actually my argument was less about not mutating your functions internal variables---but about interacting with the world outside your function via a well defined interface. (In this case, via arguments and returned values.)
The most 'mainstream' language that encourages such a strong adherence to declared interfaces is Haskell. But the imperative D can do something similar:
"In a slightly less precise way, this means that pure functions always have the same effect and/or return the same result for a given set of arguments. As a consequence, a pure function for example cannot call other impure functions, or perform any kind of I/O (in the classical sense)."
Also, they seem to grasp recursion much better via Haskell than in Python or Java. I believe that's mostly because Haskell makes structural recursion real easy (ie recursion along the structure of your data type, eg like along a tree)---and once they are comfortable with the basic idea from that, other patterns of recursion are easier to understand.
Algebraic datatypes and pattern matching on them are a great benefit for that structural recursion.
Eg when I asks students to do some simple exercise like "write a function that finds the shortest path through a given graph", in impure languages their solutions tend to return a path if they find one, but just give up with eg a message printed to screen when there's no path.
In pure and types languages, I see more people reaching for a Maybe or Either return type to express that the function as asked for might not succeed.