Firstly, bear in mind that a language is not the same as the implementation of a language. The call stack size in Python varies by implementation. The limit of 1000 applies to CPython but not necessarily all implementations.
Is it reasonable to use recursion to process balanced trees?
Recursion is reasonable for balanced trees. As you’ve described quite clearly, the maximum call stack depth is a logarithmic factor on the size of the structure. You’d need a huge input to blow the stack.
With a list or degenerate unbalanced tree, recursion is inappropriate because the maximum call stack depth is linear on the structure length.
That said, I don’t find it necessary to use self-balancing trees often in Python. Most work is done on lists and dicts, occasionally nested and recursively defined. The fact that recursion happens to be a good fit for structures like trees doesn’t imply that it’s widely applicable in general in Python.
Is it true that for most problems it is just not an option (lists, non-balanced trees, etc)?
Yes, but recursion is inhibited by design in CPython. Python is not a functional language. CPython doesn’t support tail call optimization and “never” will.
Guido has a great blog post that defends CPython’s anti-recursion design. Regardless of whether you agree with this design or not, tools should generally be used as intended, not as one wishes them to be.
In a pinch, Python (as a multi-paradigm language) can support code written in a functional style and there are workarounds to make long recursion work, but that doesn’t change the fact that they’re workarounds.
Anything else that I should take into account here? I am just trying to learn more about when recursion is the good option in general when using Python.
Function calls in CPython have more overhead (time and space) than iteration, so there are performance issues to consider even when the structure size fits in the call stack or you use a trick to support deep recursion.
Using setrecursionlimit is unsafe and almost never necessary. Such an option is not available in most languages. Increasing it means you’re running the risk of the operating system killing the CPython interpreter. Sure, fiddling with the limit can come in handy for quick scripts and debugging, but it’s not a general solution.
The recursion tag is flooded with questions from well-meaning CS students tasked with solving problems with recursion similar to your example that blows the stack using Python and other non-functional languages. The quantity of these posts and the confusion on the part of the students suggests that the CS education system has a role in pushing recursion as the default option for iteration. Recursion is only as elegant as the extent to which the language was designed for it. The fact that recursion tends to be confusing to students is more a symptom of the misapplication of it to imperative languages where recursion is a second-class citizen after loops than anything inherent in recursion itself.
You’ll probably never need recursion in Python other than school assignments, algorithm coding challenges and the rare practical business application use. But if you have a hammer, everything looks like a nail, so this isn’t to say you can’t apply recursion to each and every problem you see, it’s that you probably shouldn’t.
Recursive thinking is very valuable, and this isn’t an attack on recursion as a tool in general, just recognizing that Python is particularly ill-suited for using it (as are most other imperative languages).
Unrelated to recursion and I understand your code is just a demonstration, but max is a builtin function, so I’d pick a different name. Taken alone, max(list(range(999))) looks like it should work.