Python 理解最大递归深度超过(Dynamic Programming)
Python 理解最大递归深度超过(Dynamic Programming)
我重新学习了一些动态规划的概念，并编写了一个使用记忆化技术计算斐波那契数列的代码。
以下是代码：
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 "", line 1, in File " ", line 6, in fib File " ", line 6, in fib File " ", line 6, in fib [Previous line repeated 995 more times] File " ", 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 "", line 1, in File " ", line 6, in fib File " ", line 6, in fib File " ", line 6, in fib [Previous line repeated 995 more times] File " ", 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)，会发生相同的情况，但是如果我逐渐增加n，它就正常工作。我基本上想了解为什么会这样。memo对象不是全局的，并且应该在第一次调用函数时进行初始化，因此理论上逐渐增加n到1000应该和直接调用fib(1000)没有区别。
Python 理解递归深度超过最大值（动态规划）
在上述内容中，提到了一个问题：当memo为空且没有开始计算时，会重复存储或返回点+参数+其他内容N次，因此唯一的输出要么是递归耗尽，要么是存储（堆栈）耗尽，具体取决于两者的大小。然而，当出现这种情况时，会出现一个异常，因此当出现这种情况时，只需捕获异常，将数字分成几部分（例如除以二/四/...），然后再次返回（递归）。这样，即使递归调用导致堆栈溢出，您也将递归地找到一个较小的数字，该数字将填充memo，然后您可以慢慢地将自己引导到更大的数字。
这个问题的解决方法是，当出现递归深度超过最大值时，将数字分成几部分进行递归计算，直到找到可以计算的值。这样，即使递归调用导致堆栈溢出，也可以逐步通过递归找到较小的数字，填充memo并逐渐扩大到较大的数字。
这个问题出现的原因是，当memo为空且没有开始计算时，会重复存储或返回点+参数+其他内容N次，导致递归耗尽或存储（堆栈）耗尽。
Python处理这个问题的方式与其他语言不同，它使用了半全局状态的概念。在函数执行完毕并返回结果后，我期望它为顶层调用创建一个新的memo对象，但是Python处理方式与其他语言不同。Python中的函数和模块在解析完成后才准备好使用，函数的属性值是一个原始类型（如int）或一个对象（如字典）。对于可变对象来说，这意味着内容（如计算后的斐波那契数）在递归中保持不变，类似于半全局值。
解决该问题的方法是将数字分成几部分进行递归计算，直到填充memo。这样即使递归调用导致堆栈溢出，也可以逐步通过递归找到较小的数字，填充memo并逐渐扩大到较大的数字。Python处理这个问题的方式与其他语言不同，它使用了半全局状态的概念，函数的属性值在函数的生命周期内保持不变。
Python理解递归深度超过最大值（动态规划）
这是因为如果memo为空，递归需要一直进行到基本情况n <= 2。所以，如果你立即开始第一个调用是fib(1000)，你可能会遇到堆栈溢出的问题。
然而，当你从较小的值开始，比如调用fib(10)，memo将收集大量的结果，包括10和9。所以下次你增加传递的参数进行调用时，它不需要递归到2，而是可以在达到9或10时就返回，因为它会在memo中找到已经可用的结果。
需要注意的是，memo只在函数被定义时初始化为{}，所以你只需要不断扩展它，从而减少在深度递归时使用调用堆栈的需求。
啊，你最后一句回答了我的问题。在我脑海中，memo应该在我调用函数如fib(1000)时每次初始化，而递归调用会使用那个memo对象，但是当我调用fib(2000)时，memo应该在第一次调用时再次初始化。你的答案很有道理。非常感谢！
是的，这在Python中是一个奇怪的地方。在大多数其他流行的语言中，默认参数是在调用时进行评估的。
但是你为什么希望它在“第一次调用”时被重置呢？它不被重置的事实正是记忆化工作的原因：因为memo持久存在并在函数调用之间维护其状态。Python没有区分你在shell中明确调用的函数调用和作为源代码的递归函数调用。如果每次都启动一个新的shell，你将得到不同的结果。
只是注意一下，在代码中，递归调用明确传递了memo。这是基于许多其他语言的工作方式。在Python中，你甚至不需要传递参数，因为该参数的默认值不会被评估（无论你是否传递参数）。对于某些人来说，这可能会造成困惑，尤其是当其他语言中的行为不同的时候。
这是因为第一个调用是由我自己进行的，其中memo是一个空字典。对于递归调用，使用的是同一个memo对象。这对我来说是有意义的。然而，一旦递归调用完成并且函数返回，当我再次调用fib(1000)时，我认为memo对象会再次初始化，但事实证明不是这样（参考trincot的评论）。
我的错，没有仔细看！