Designing recursive functions around Python's stack limits
Some functions can be defined clearly and succinctly using a recursive formula. There are two common examples of this.
The factorial function has the following recursive definition:
The recursive rule for computing a Fibonacci number, Fn, has the following definition:
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:
And so on.
To compute F5, we'll compute F3...
