Python understanding Max Recursion Depth exceeded (Dynamic Programming)

I was revisiting some dynamic programming concepts and I wrote a code to calculate Fibonacci with memoization.

Here is the code:

def fib(n,memo={}):
    if(n in memo):
        return memo[n]
    if(n <= 2):
        return 1
    memo[n]=fib(n-1,memo) + fib(n-2,memo)
    return memo[n]

Now I ran some test cases and here are the results

>>> fib(2)
1
>>> fib(1000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 6, in fib
  File "<stdin>", line 6, in fib
  File "<stdin>", line 6, in fib
  [Previous line repeated 995 more times]
  File "<stdin>", line 4, in fib
RecursionError: maximum recursion depth exceeded in comparison
>>> fib(6)
8
>>> fib(10)
55
>>> fib(100)
354224848179261915075
.
.
.
.
>>> fib(980)
2873442049110331124686847975839596483580184681281842823699466692000268066325404550898791458706068536914736664630537864515125212890415097163803163111745199726085365105
>>> fib(990)
3534100091787525753399448335204590682849450463581549776041091752538906966342713601215835661100647255108360758515849851434123968685864251091027232911065706187500753920
>>> fib(999)
2686381002448535938614672720214292396761660931898695234012317599761798170024788168933836965448335656419182785616144335631297667364221035032463485041037768036733415116
>>> fib(1000)
4346655768693745643568852767504062580256466051737178040248172908953655541794905189040387984007925516929592259308032263477520968962323987332247116164299644090653318795

When I ran fib(1000) the first time, it said maximum recursion depth exceeded. However, when I gradually increased n, fib(1000) worked fine.
Then I tried fib(2000) and got the same exception.

>>> fib(2000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 6, in fib
  File "<stdin>", line 6, in fib
  File "<stdin>", line 6, in fib
  [Previous line repeated 995 more times]
  File "<stdin>", line 4, in fib
RecursionError: maximum recursion depth exceeded in comparison

I tried gradually increasing n and it worked fine again:

>>> fib(1200)
2726988445540627015799161531364219870500077999291772582118050289497472647637302680948250928456231003117017238012762721449359761674385644301603997220584740591763466070
>>> fib(1500)
1355112566856310195163693686714840837778601071241849724213354315322148731087352875061225935403571726530037377881434732025769925708235655004534991410292424959599748390
>>> fib(1700)
8501653935514177120246392248625833924052052390491381030300605977750345588982825628424071479174753549360050542305550855066813804919653208931716726270523366654632196915
>>> fib(1900)
5333735470177196739708654380013216364182711606231750028692155598599810955874132791398352277818697705852238294681640540003099177608752396895596802978549351480795061055
>>> fib(2000)
4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555805
>>> fib(2500)
1317090516751949629522763087125316412066606964992507141887746936727530870405038425764503130123186407746570862185871925952766836352119119528156315582632460790383834605
>>> fib(2900)
5184080332847202181832545365520373859688699234105705045492742368770388504951261158081878962852500283133276036303031796698449718008155302155556519351587134410081144235
>>> fib(3000)
4106158863079712603335683787192671052201251086373692524088854309269055842741134037313304916608500445608300368357069422745885693621454765026743730454468521604866062920

Same thing happens if I run fib(4000) immediately afterwards, but it works fine if I gradually increase. I am basically trying to understand why is that the case. The memo object is not global and should be initialized in the first call to the function, so successively increasing n to 1000 should, in theory, be no different than directly calling fib(1000).

>Solution :

This is because if memo is empty, the recursion needs to go all the way to the base case of n <= 2. So if you immediately start with a first call that is fib(1000) you may bump into a stack overflow.

However, when you start with smaller values, like the call of fib(10), memo will collect lots of results, including for 10 and 9. And so the next time you make a call increasing the argument that you pass, it doesn’t have to recur all the way to 2, but can already back track when it reaches 9 or 10, as it will find it already available in memo.

Note that memo only initialises to {} at the moment the function is defined, so you just keep extending it, thereby reducing the need to use the call stack for deep recursions.