Elimination of non-tail recursion is not a thing I'd like to rely on...

Most compilers are smart enough to perform tail recursion optimization. Sometimes even if the function isn't tail recursive.

found some formula on stackoverflow (no credit due to limited space here)
Maximum recursion depth = ((Stack size) - (Total size of stack frames in call chain up to the recursive function)) / (Stack frame size of recursive function)
though it depends on tail recursion optimization. 8 MB stack size as usual, but tunable on OS.
I have readed somewhere around 800 recursions on gcc and 400 in microsoft visual, but you have to check for yourself.