本文介绍了超过了对最大递归深度的理解(动态编程)的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

代码如下:

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将收集大量结果,包括109。因此,下一次调用增加您传递的参数时,它不必一直重复到2,但在达到9或10时已经可以回溯,因为它会发现它已经在memo中可用。

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

这篇关于超过了对最大递归深度的理解(动态编程)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-07 05:13