Python 理解超出最大递归深度（动态编程）

Question

我正在重新审视一些动态编程概念，我编写了一个代码来计算带有记忆的斐波那契。

代码如下：

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

Answer 1

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

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

请注意，memo 仅在函数 已定义 时初始化为 {}，因此您只需继续扩展它，从而减少对使用调用堆栈进行深度递归。

Answer 2

正如 trincot 提到的，不存在任何数据，因此代码将继续寻找对该函数的另一个调用而不是该值，直到该值在堆栈限制内可计算为止。从理论上讲，对函数的调用会在某处（堆栈）保留一些 space ，其中有来自函数的 returning 点，func 的参数，也许还有其他东西。你正在发生的事情是，当备忘录为空并且你还没有开始任何计算时，你重复存储或 return point + args + 其他东西 N 次，因此唯一的输出是递归耗尽或存储（堆栈）耗尽，具体取决于两个大小。

然而，你会得到一个很好的异常，所以当这种情况发生时，只需捕获它，将数字分成几部分（例如除以 two/four/...）并再次 return （递归地）。这样，即使您用递归调用破坏了堆栈，您也会递归地找到一个较小的数字来填充备忘录，然后您慢慢 bootstrap 找到更大的数字。

Python 理解超出最大递归深度（动态编程）

Python understanding Max Recursion Depth exceeded (Dynamic Programming)

python

memoization

dynamic-programming

fibonacci