Some functions can be defined clearly and succinctly using a recursive formula. There are two common examples:
The factorial function:
The rule for computing Fibonacci numbers:
Each of these involves a case that has a simple defined value and a case that involves computing the function's value based on other values of the same function.
The problem we have is that Python imposes a limitation on the upper limit for these kinds of recursive function definitions. While Python's integers can easily represent 1000!, the stack limit prevents us from doing this casually.
Computing Fn Fibonacci numbers involves an additional problem. If we're not careful, we'll compute a lot of values more than once:
F5 = F4 + F3
F5 = (F3 + F2) + (F2 + F1)
And so on.
To compute F5, we'll compute F3 twice, and F2 three times. This is extremely costly.