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 Ah okay, then it's probably because of that lru_cache, that prevents a stack overflow.

Answer 2

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 to be 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.

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 3

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

Answer 4

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

Answer 5

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

Answer 6

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 7

Jan Nope! I ran the code on my IDE.

Answer 8

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 9

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 10

What happened

Answer 11

+++++

Answer 12

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