How can a recursive function works perfectly in a for loop with large numbers while calling it too many times raises an error?

Question

What I know is, a recursive function is a function that calls itself multiple times. It raises a RecursionError if it is called too many times.
However, in the code example below, the fib() function works perfectly inside a for loop that iterates from 1 to 2000, while calling it outside the loop, passing only 1000 to it immediately raises a RecursionError.
Can someone explain me why?
https://sololearn.com/compiler-playground/ctNkN4ckuEjK/?ref=app

Answer 1

Dragon RB
The lru cache seems to work better if used repeatedy in the for loop.

Jan ,
i was thinking the same thing, but I modified the code to be able to see the end values and it seems that fib is performing better inside the for loop.

I played around with the code a bit...
clearing the cache after each iteration stopped the strange performance boost. So the lru_cache is indeed doing something unexpected when used repeatedly.

perhaps some memory swapping is happening which allows the cache to store the bigger values in the for loop as opposed to the fib function being called only once when it's outside the for loop... not sure.

https://sololearn.com/compiler-playground/chW9m3fjo6p4/?ref=app

Answer 2

Dragon RB Ah okay, then it's probably because of that lru_cache, that prevents a stack overflow.

Answer 3

Bob_Li and Jan , you guys are stars! Thanks for your efforts and sharing of knowledge.

Answer 4

Bob_Li I can only speak for myself now, but the best thing is to avoid recursive functions.

Answer 5

Dragon RB , In the for loop, each call to fib(x) always uses the results of previous calls to fib(for n<x) so it doesn't use recursion. Whereas a single call to a single fib(for any x greater than 499) violates the limit on recursive calls set in the system by default. By changing this limit, you can get the calculations you need.
https://sololearn.com/compiler-playground/ckgvJ9sMW9g5/?ref=app

Answer 6

Vitaly Sokol wow. There's a lot of good to know techniques in your code. 👍

but Jan's iterative fib code can do that, too, with less resource allocations.

https://sololearn.com/compiler-playground/c3tI84FhqYgQ/?ref=app

Answer 7

Jan
agreed. it's easy to write, but often resource-heavy to execute.

Answer 8

Vitaly Sokol , Jan
👍👍👍

Answer 9

BroFar , Bob_Li , Dragon RB
https://sololearn.com/compiler-playground/cLZPuwSt1XSt/?ref=app

Answer 10

Bob_Li your right, so, probably my solution is related to Dragon RB's question, it's not only to calculate the nth Fibonacci term, but also to be able to instantly access any fibo value from the range(n)

Answer 11

It only works perfect in the loop because of "Execution Timet Out" when it reach 70 in the loop. It's the limitation on the playground that prevents it from causing a stack overflow.

If you run the code on a pc, then you would probably quite quickly get a stack overflow.

Answer 12

Jan Nope! I ran the code on my IDE.

Answer 13

Vitaly Sokol ,
I am not so sure.. As I use the sys.setrecursionlimit() (let's say I'll set the limit to 100000)
And then call the fib() function (with lru_cache to significantly boost the performance) with high values like 50000, it instead says "Segmentation fault" even with the use of sys.set_int_max_str_digits(). I did a little research and it's probably kind of like C's problem, not Python's. But how?

Answer 14

My understanding is that recursion can be fairly intensive on resources, so maybe that's what occurs here.
I think I read some good threads here about it:

https://www.sololearn.com/discuss/1671835/?ref=app
https://www.sololearn.com/discuss/307407/?ref=app
https://www.sololearn.com/discuss/120350/?ref=app

Answer 15

Bob_Li Thank you!! I understand now.

Answer 16

What happened

Answer 17

+++++

Answer 18

https://sololearn.com/compiler-playground/crRPf1Hea1eZ/?ref=app

Answer 19

You can using try and catch