Python understanding Max Recursion Depth exceeded (Dynamic Programming)

Question

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).

Try to run `memo={}` before you call `fib` function. – PM 77-1 Jan 10 '22 at 16:40 — PM 77-1, Jan 10 '22 at 16:40

trincot · Accepted Answer · 2022-01-10T16:44:54.713

3

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.

edited Jan 10 '22 at 16:44

answered Jan 10 '22 at 16:36

trincot

317,000
35
244
286

1

Ah, your last sentence answers my query. In my head, memo should initialize every time I call the function like fib(1000) and the recursive calls would use that memo object, but when I call fib(2000), memo should be initialized again during the first call. Your answer makes a lot of sense. Thanks a lot! – Khizar Amin Jan 10 '22 at 16:43
1

Yes, that is an oddity in Python. In most other popular languages, default arguments are evaluated at the time of the *call*. – trincot Jan 10 '22 at 16:46
@KhizarAmin Why would you expect it be reset in the "first call", though? The fact that it's not reset is the whole reason why the memoization works in the first place: because `memo` persists and maintains its state between function invocations. Python does not differentiate between a function call that you invoked explicitly in the shell, and a recursive function call that's part of your source code. You WOULD get different results if you would start up a new shell each time. – Paul M. Jan 10 '22 at 16:47
@PaulM., just to note that in the code the recursive calls explicitly pass `memo`. This stems from how it would have worked in many other languages. In Python you don't even have to pass the argument, since the default for that parameter will not be evaluated either way (whether you pass an argument or not). It is that which can be confusing for some, certainly when that behaviour is different in other languages. – trincot Jan 10 '22 at 16:50
@PaulM. that is because the first call is made by me, where memo is an empty dict. For the recursive calls, the same memo object is used. This made sense to me. However once the recursive calls are complete and the function returns, and I call fib(1000) again, I thought that the memo object would be initialized again, but it turns out that is not the case (refer to trincot's comment). – Khizar Amin Jan 10 '22 at 16:52
My bad, wasn't looking closely! – Paul M. Jan 10 '22 at 17:22

Peter Badida · Answer 2 · 2022-01-10T17:08:44.363

0

As trincot mentioned, there's no data present, so the code will just go and find another call to the function instead of the value until the value is computable within the stack limit. A call to the function, in theory, reserves some space somewhere (stack) where there is a returning point from the function, func's arguments and perhaps something else. What's happening for you is, that you repeat the storing or return point + args + other stuff N times when the memo is empty AND you haven't started with any computation yet, therefore the only output is either recursion exhaustion or storage (stack) exhaustion, depending on the two sizes.

However, you get a nice exception, so when such a case occurs, simply catch it, split the number into parts (e.g. divide by two/four/...) and return again (recursively). This way, even if you blow the stack with your recursion calls, you'll recursively find a smaller number which will fill the memo and then you slowly bootstrap your way to the larger numbers.

edited Jan 10 '22 at 17:08

answered Jan 10 '22 at 16:42

Peter Badida

11,310
10
44
90

Thats a nice idea, I was trying to understand how python is creating/handling the memo object. I thought it would be created everytime I call fib, and then used for the recursive calls. Splitting into parts suggestion is neat, I'll add that too. – Khizar Amin Jan 10 '22 at 16:46
@KhizarAmin Put yourself to the role of a code parser. When is a module created/ready for use? Once everything is parsed. A module consists of funcs(and other stuff). When is a func ready? Once its code is readable (not yet executed) and its properties (args, name, etc) created. A func's "property" value is a primitive, such as int (immutable) or an object such as dict (mutable). Once it's created for a function, it's global through the func's lifetime. For mutable objects it means the content (such as computed fibs) is preserved through the recursion, kind of like a semi-global value. – Peter Badida Jan 10 '22 at 16:53
Yes, I understand that. But once the function has completed the execution and returned me the result for say fib(5), I was expecting it to create a new memo object for the top level call of fib(10) but python handles it differently than other languages as mentioned by trincot – Khizar Amin Jan 10 '22 at 16:55
1

@KhizarAmin yes, that's the semi-global state you see. Try to run `print(id(memo))` vs `id(fib.__defaults__[idx])` and you'll see. – Peter Badida Jan 10 '22 at 17:02

Python understanding Max Recursion Depth exceeded (Dynamic Programming)

2 Answers2

Linked