Python 编程别再用递归了

递归函数使用起来非常酷，简洁优雅，可以用来炫耀编程技巧。但是，在大多数情况下，递归函数具有非常高的时间和空间复杂性，我们应该避免使用它。更好的解决方案之一是在可能的情况下使用动态规划，对于能够分解为子问题的问题，动态规划可能是最佳方法。然而某些动态规划的状态转移方程不太容易定义。

今天分享 Python 的另一种牛逼的技术--闭包，可以用来作为替代递归函数。它可能不会胜过动态规划，但在思考方面要容易得多。换句话说，由于思想的抽象，我们有时可能难以使用动态规划，但是使用闭包会容易一些。

什么是 Python 闭包？

首先，让我使用一个简单的示例来说明什么是 Python 中的闭包。看下面的函数：

在一个函数内部定义另外一个函数，并返回这个函数，这种特性就是闭包。检查 outer 函数的返回值，可以确认这是一个函数。

闭包这种特性能做什么呢？因为函数返回的是一个函数，我们就可以调用这个函数，比如：

不过我们一般会这么使用闭包，这样太丑陋了。你可能会好奇这个跟递归有什么关系？别着急，让我们慢慢体会闭包的牛逼之处。

闭包内的变量访问

从前述的运行结果来看，inner 函数可以访问 outer 函数内部定义的变量 x，但是却无法修改它，下面的代码运行时会报错：

为了解决这个问题，我们可以加上 nonlocal 关键字，告诉 inner 函数，这不是一个本地变量：

有没有发现，x 的值竟然被保存了下来，每次调用一下，就增加了 1，这就是闭包的妙处。

用闭包来替换递归

利用上述闭包会保留调用结果的特性，我们可以用这个来替换递归，比如利用闭包计算斐波那契数列：

可以这样调用来生产斐波那契数列：

而使用递归方法计算斐波那契数列的方法如下所示：

把之前的闭包版本封装一下：

这样使用 fib_closure(20) 就可以计算出结果：

现在使用 IPython 来测试下这两者的性能：

可以看出两差相差近 1000 倍，这还只是计算到第 20 个数的情况下，如果计算到 100，那使用递归会计算很久甚至无法计算出来。

闭包的其他用处

Python 的闭包不仅仅用于替换递归，还有很多场景可以使用闭包。比如学生成绩的分类函数：

学生成绩数据：

现在需要根据学生成绩进行分类，通常情况下我们会写多个函数来进行分类，而分类的标准又会经常变化，这时候闭包就很方便了：

如果分类标准变化，直接个性函数的参数即可，主要代码逻辑不变，如果想查找成绩分类为 A 的学生，只需要调用 grade_A(students) 即可：

闭包使用上述分类函数很容易修改且更加易读。

最后的话

本文介绍了一种称为 Python 闭包的技术。在大多数情况下，可以使用它来重写递归函数，并且在很大程度上优于后者。

实际上，从性能的角度来看，闭包可能不是某些问题的最佳解决方案，尤其是在使用动态规划的情况下。但是，闭包写起来要容易一些，比递归性能高。当我们对性能不是很敏感时，有时写动态计划会有点浪费时间，但是闭包可能就足够了。

闭包也可以用来定义一些逻辑相同但命名不同的函数，比如本文中的分类函数，在这些情况下，它更加整洁而优雅，更加易读。

下次试试闭包吧，别用效率低下的递归了。