Since non tail recursive recursion calls use stack frames like Java does, I'd be weary to do any recursion that, let's say goes beyond 1,000 times. I would be thus weary to use it for most of things.
Do people actually use non tail recursive recursion in Scala? If so, what are the criteria I can use to determine if it can be non tail recursive?
Also, are there plans to remove this memory restriction in future versions of Scala?
In the situation where you cannot use single tail recursion, for example because you need to alternative between two functions, a mechanism called trampolining has been described.
A more recent and thorough discussion of this topic can be found in Rúnar Bjarnason's paper Stackless Scala With Free Monads.
Personally, I would go the easy route and revert to imperative style if you really have this situation with >1K depths, e.g. use a mutable collection builder.
