About Recursion Limit in Python

Python lacks the tail recursion optimizations common in functional languages like lisp. In Python, recursion is limited to 999 calls (see sys.getrecursionlimit).
I dare to say that in Python, pure recursive algorithm implementations are not correct/safe. A fib() implementation limited to 999 is not really correct. It is always possible to convert recursive into iterative, and doing so is trivial.
If you expect to get more than 999 deep, my advice is to convert the algorithm from recursive to iterative. If not, check for a runaway bug (the implementation lacks a condition that stops recursion, or this condition is wrong).

How to set Recursion Limit
You can increment the stack depth allowed - with this, deeper recursive calls will be possible, like this:
import sys
sys.setrecursionlimit(10000) # 10000 is an example, try with different values
... But I'd advise you to first try to optimize your code, for instance, using iteration instead of
recursion.

How to decide Recursion Limit
It is based on the TOTAL stack depth and not really the depth of any particular single function. You are probably already at a stack depth of 5 when you make the first call to rec().
Take for example 5 recursive functions. Each makes 98 recursive calls with the last one being to the next recursive function. With a recursion limit of 100 do you really want to allow each recursive function to make 99 calls for a total depth of ~500 calls? No, that might crash the interpreter at those depths.
Therefore the recursion limit is the maximum depth of all functions globally, not any single named function.