Why is Python recursion so expensive and what can we do about it?
Both will find the answer 996 without issues. We are taking modulos to keep the output size reasonable and using pairs to avoid exponential branching.
Why are recursive calls so much cheaper in C++? Can we somehow modify the Python compiler to make it more receptive to recursion?
Of course, one solution is to replace recursion with iteration. For Fibonacci numbers, this is easy to do. However, this will swap the initial and the terminal conditions, and the latter is tricky for many problems (e.g. alpha–beta pruning). So generally, this will require a lot of hard work on the part of the programmer.
A solution is a trampoline: the recursive function, instead of calling another function, returns a function that makes that call with the appropriate arguments. There's a loop one level higher that calls all those functions in a loop until we have the final result. I'm probably not explaining it very well; you can find resources online that do a better job.
The point is that this converts recursion to iteration. I don't think this is faster, maybe it's even slower, but the recursion depth stays low.
