超过了对最大递归深度的理解(动态编程)

问题描述

我正在重温一些动态编程概念，我写了一段代码，用记忆法计算斐波纳契数。

代码如下：

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]

现在我运行了一些测试用例，结果如下

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

当我第一次运行fib(1000)时，它显示超过了最大递归深度。然而，当我逐渐增加n时，fib(1000)工作得很好。 然后我尝试了fib(2000)，得到了同样的异常。

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

我尝试逐渐增加n，但再次正常工作：

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

如果我之后立即运行fib(4000)，也会发生同样的事情，但如果我逐渐增加，它就可以很好地工作。我基本上是在试图理解为什么会这样。Memo对象不是全局对象，应该在第一次调用函数时进行初始化，因此从理论上讲，将n连续增加到1000应该与直接调用fib(1000)没有什么不同。

---

解决方案

这是因为如果memo为空，则递归需要一直到n <= 2的基本情况。因此，如果您立即从fib(1000)的第一个调用开始，可能会遇到堆栈溢出。

但是，当您从较小的值开始时，如调用fib(10)，memo将收集大量结果，包括10和9。因此，下一次调用增加您传递的参数时，它不必一直重复到2，但在达到9或10时已经可以回溯，因为它会发现它已经在memo中可用。

请注意，memo仅在定义时才初始化为{}，因此您只需不断扩展它，从而减少使用调用堆栈进行深度递归的需要。