Computing Fibonacci NumbersStack Overflow (not the site)
When a function calls a function, it creates a stack of evaluations. Imagine an evaluation tree like the one before, but for . We call memoized_fib(10_000), which calls memoized_fib(9999) and memoized_fib(9998), and so on all the way down to 0 and 1. This stack takes up memory (we need to store which function call to return to when we're done evaluating this one, for each of these calls), and it looks an awful lot like an infinite loop: Python can't deduce that this will stop at some point. To prevent stack overflow (running out of memory on this stack of function calls) and infinite loops, there's a recursion limit that CPython (the standard Python implementation) enforces: a maximum number of function calls inside function calls before the program is halted. We've just hit that limit.
We could change the recursion bound, but eventually we'd run out of memory instead. A better solution is what is known, somewhat misleadingly, as dynamic programming.
3000
Stack Overflow (not the site)
When a function calls a function, it creates a stack of evaluations. Imagine an evaluation tree like the one before, but for . We call memoized_fib(10_000), which calls memoized_fib(9999) and memoized_fib(9998), and so on all the way down to 0 and 1. This stack takes up memory (we need to store which function call to return to when we're done evaluating this one, for each of these calls), and it looks an awful lot like an infinite loop: Python can't deduce that this will stop at some point. To prevent stack overflow (running out of memory on this stack of function calls) and infinite loops, there's a recursion limit that CPython (the standard Python implementation) enforces: a maximum number of function calls inside function calls before the program is halted. We've just hit that limit.
We could change the recursion bound, but eventually we'd run out of memory instead. A better solution is what is known, somewhat misleadingly, as dynamic programming.
3000