递归函数用起来很爽，简洁大方，可以拿来大显编程功底。但是，在大多数情况下，递归函数的时间和空间复杂度都非常高，我们应该避免使用它。更好的解决方案之一是尽可能使用动态规划，对于可以分解为子问题的问题，动态规划可能是最好的方法。然而，一些动态规划状态转移方程不容易定义。今天分享Python的另一项牛逼技术——闭包，它可以作为递归函数的替代品。它可能不会胜过动态规划，但它更容易思考。换句话说，我们有时可能会因为思想的抽象而在动态规划上吃力，但有了闭包就会容易一些。什么是Python闭包？首先，让我用一个简单的例子来解释Python中的闭包是什么。看下面这个函数：defouter():x=1definner():print(f'xinouterfunction:{x}')returninner在一个函数内部定义了另一个函数，并返回这个函数。这个特征是一个闭包。检查外部函数的返回值可确认这是一个函数。>>>defouter():...x=1...definner():...print(f'xinouterfunction:{x}')...returninner...>>>outer>>>outer().innerat0x7fb2ecdaca60>>>>Closure这个特性能做什么？因为函数返回一个函数，所以我们可以调用这个函数，例如：>>>outer()()xinouterfunction:1>>>但是我们一般都是这样使用闭包，太丑了。您可能想知道这与递归有什么关系？别着急，让我们慢慢了解闭包的牛逼。闭包中的变量访问从上述运行结果来看，内层函数可以访问外层函数内部定义的变量x，但不能对其进行修改。以下代码运行时会报错：>>>defouter():...x=1...definner():...print(f'xinouterfunction(beforemodifying):{x}')...x+=1...print(f'xinouterfunction(aftermodifying):{x}')...returninner...>>>f=outer()>>>f()Traceback(mostrecentcallast):File"",line1,inFile"",line4,ininnerUnboundLocalError:localvariable'x'referencedbeforeassignment>>>为了解决这个问题，我们可以添加nonlocal关键字来告诉内部函数这不是局部变量：>>>defouter():...x=1...definner():...nonlocalx...print(f'xinouterfunction(beforemodifying):{x}')...x+=1...打印（f'xinouterfunction（修改后）：{x}'）...returninner。..>>>>>>f=outer()>>>f()xinouterfunction(修改前):1xinouterfunction(修改后):2>>>f()xinouterfunction(修改前):2xinouterfunction(修改后):3>>>f()xinouterfunction(修改前):3xinouterfunction(aftermodifying):4>>>你有没有发现x的值被保存起来，每调用一次就加1，这就是闭包的妙处使用闭包代替递归。上面的闭包会保留调用结果的特征。我们可以用它来代替递归。例如，使用闭包计算斐波那契数列：defib():x1=0x2=1defget_next_number():nonlocalx1,x2x3=x1+x2x1,x2=x2,x3returnx3returnget_next_number可以这样调用生成斐波那契数列：>>>defib():...x1=0...x2=1...defget_next_number():...nonlocalx1,x2...x3=x1+x2...x1,x2=x2,x3...返回x3...返回get_next_number...>>>fibonacci=fib()>>>foriinrange(2,21):...num=fibonacci()...print(f'The{i}thFibonaccinumberis{num}')...The2thFibonaccinumberis1The3thFibonaccinumberis2The4thFibonaccinumberis3The5thFibonaccinumberis5The6thFibonaccinumberis8The7thFibonaccinumberis13The8thFibonaccinumberis21The9thFibonaccinumberis34The10thFibonaccinumberis55The11thFibonaccinumberis89The12thFibonaccinumberis144The13thFibonaccinumberis233The14thFibonaccinumberis377The15thFibonaccinumberis610The16thFibonaccinumberis987The17thFibonaccinumberis1597The18thFibonaccinumberis2584The19thFibonaccinumberis4181The20thFibonaccinumberis6765>>>而使用递归方法计算斐波那契数列的方法如下所示：deffib_recursion(n:int)->int:ifn<=1:returnnreturnfib_recursion(n-1)+fib_recursion(n-2)封装之前的闭包版本：defib():x1=0x2=1defget_next_number():nonlocalx1,x2x3=x1+x2x1,x2=x2,x3returnx3returnget_next_numberdefib_closure(n):f=fib()foriinrange(2,n+1):num=f()returnnum这样用fib_closure(20)计算结果：In[4]:fib_closure(20)Out[4]:6765In[5]:fib_recursion(20)Out[5]:6765In[6]:现在用IPython测试两者的性能：In[6]:%timefib_closure(20)CPUtimes:user10μs,sys:1e+03ns,total:11μsWalltime:14.1μsOut[6]:6765In[7]:%timefib_recursion(20)CPUtimes:user2.76ms,sys:15μs,total:2.78msWalltime:2.8msOut[7]:6765可以看出，两者相差将近1000倍。这只是在计算第20个数字时。如果计算到100，用递归计算时间会很长，甚至计算不出来。闭包的其他用途Python闭包不仅仅用来代替递归，还有很多场景可以使用闭包。例如学生成绩的分类函数：学生成绩数据：students={'Alice':98,'Bob':67,'Chris':85,'David':75,'Ella':54,'Fiona':35,'Grace':69}现在我们需要根据学生的成绩对学生进行分类。通常我们会写多个函数进行分类，分类标准会经常变化。这时候闭包就很方便了：defmake_student_classifier(lower_bound,upper_bound):defclassify_student(exam_dict):return{k:vfor(k,v)inexam_dict.items()iflower_bound<=v
