[[385610]]

遞歸函數使用起來非常酷，簡潔優雅，可以用來炫耀編程技巧。但是，在大多數情況下，遞歸函數具有非常高的時間和空間復雜性，我們應該避免使用它。更好的解決方案之一是在可能的情況下使用動態規劃，對于能夠分解為子問題的問題，動態規劃可能是最佳方法。然而某些動態規劃的狀態轉移方程不太容易定義。

今天分享 Python 的另一種牛的技術--閉包，可以用來作為替代遞歸函數。它可能不會勝過動態規劃，但在思考方面要容易得多。換句話說，由于思想的抽象，我們有時可能難以使用動態規劃，但是使用閉包會容易一些。

什么是 Python 閉包?

首先，讓我使用一個簡單的示例來說明什么是 Python 中的閉包。看下面的函數：

def outer(): 
    x = 1 
    def inner(): 
        print(f'x in outer function: {x}') 
    return inner 

在一個函數內部定義另外一個函數，并返回這個函數，這種特性就是閉包。檢查 outer 函數的返回值，可以確認這是一個函數。

>>> def outer(): 
...     x = 1 
...     def inner(): 
...         print(f'x in outer function: {x}') 
...     return inner 
... 
>>> outer 
<function outer at 0x7fb2ecdac9d0> 
>>> outer() 
<function outer.<locals>.inner at 0x7fb2ecdaca60> 
>>> 

閉包這種特性能做什么呢?因為函數返回的是一個函數，我們就可以調用這個函數，比如：

>>> outer()() 
x in outer function: 1 
>>> 

不過我們一般會這么使用閉包，這樣太丑陋了。你可能會好奇這個跟遞歸有什么關系?別著急，讓我們慢慢體會閉包的牛逼之處。

閉包內的變量訪問

從前述的運行結果來看，inner 函數可以訪問 outer 函數內部定義的變量 x，但是卻無法修改它，下面的代碼運行時會報錯：

>>> def outer(): 
...     x = 1 
...     def inner(): 
...         print(f'x in outer function (before modifying): {x}') 
...         x += 1 
...         print(f'x in outer function (after modifying): {x}') 
...     return inner 
... 
>>> f = outer() 
>>> f() 
Traceback (most recent call last): 
  File "<stdin>", line 1, in <module> 
  File "<stdin>", line 4, in inner 
UnboundLocalError: local variable 'x' referenced before assignment 
>>> 

為了解決這個問題，我們可以加上 nonlocal 關鍵字，告訴 inner 函數，這不是一個本地變量：

>>> def outer(): 
...     x = 1 
...     def inner(): 
...         nonlocal x 
...         print(f'x in outer function (before modifying): {x}') 
...         x += 1 
...         print(f'x in outer function (after modifying): {x}') 
...     return inner 
... 
>>> 
>>> f = outer() 
>>> f() 
x in outer function (before modifying): 1 
x in outer function (after modifying): 2 
>>> f() 
x in outer function (before modifying): 2 
x in outer function (after modifying): 3 
>>> f() 
x in outer function (before modifying): 3 
x in outer function (after modifying): 4 
>>> 

有沒有發現，x 的值竟然被保存了下來，每次調用一下，就增加了 1，這就是閉包的妙處。

用閉包來替換遞歸

利用上述閉包會保留調用結果的特性，我們可以用這個來替換遞歸，比如利用閉包計算斐波那契數列：

def fib(): 
    x1 = 0 
    x2 = 1 
    def get_next_number(): 
        nonlocal x1, x2 
        x3 = x1 + x2 
        x1, x2 = x2, x3 
        return x3 
    return get_next_number 

可以這樣調用來生產斐波那契數列：

>>> def fib(): 
...     x1 = 0 
...     x2 = 1 
...     def get_next_number(): 
...         nonlocal x1, x2 
...         x3 = x1 + x2 
...         x1, x2 = x2, x3 
...         return x3 
...     return get_next_number 
... 
>>> fibonacci = fib() 
>>> for i in range(2, 21): 
...     num = fibonacci() 
...     print(f'The {i}th Fibonacci number is {num}') 
... 
The 2th Fibonacci number is 1 
The 3th Fibonacci number is 2 
The 4th Fibonacci number is 3 
The 5th Fibonacci number is 5 
The 6th Fibonacci number is 8 
The 7th Fibonacci number is 13 
The 8th Fibonacci number is 21 
The 9th Fibonacci number is 34 
The 10th Fibonacci number is 55 
The 11th Fibonacci number is 89 
The 12th Fibonacci number is 144 
The 13th Fibonacci number is 233 
The 14th Fibonacci number is 377 
The 15th Fibonacci number is 610 
The 16th Fibonacci number is 987 
The 17th Fibonacci number is 1597 
The 18th Fibonacci number is 2584 
The 19th Fibonacci number is 4181 
The 20th Fibonacci number is 6765 
>>> 

而使用遞歸方法計算斐波那契數列的方法如下所示：

def fib_recursion(n:int) -> int: 
    if n <= 1: 
        return n 
    return fib_recursion(n-1) + fib_recursion(n-2) 

把之前的閉包版本封裝一下：

def fib(): 
    x1 = 0 
    x2 = 1 
    def get_next_number(): 
        nonlocal x1, x2 
        x3 = x1 + x2 
        x1, x2 = x2, x3 
        return x3 
    return get_next_number 
 
def fib_closure(n): 
    f = fib() 
    for i in range(2, n+1): 
        num = f() 
    return num 

這樣使用 fib_closure(20) 就可以計算出結果：

In [4]: fib_closure(20) 
Out[4]: 6765 
 
In [5]: fib_recursion(20) 
Out[5]: 6765 
 
In [6]: 

現在使用 IPython 來測試下這兩者的性能：

In [6]: %time fib_closure(20) 
CPU times: user 10 µs, sys: 1e+03 ns, total: 11 µs 
Wall time: 14.1 µs 
Out[6]: 6765 
 
In [7]: %time fib_recursion(20) 
CPU times: user 2.76 ms, sys: 15 µs, total: 2.78 ms 
Wall time: 2.8 ms 
Out[7]: 6765 

可以看出兩差相差近 1000 倍，這還只是計算到第 20 個數的情況下，如果計算到 100，那使用遞歸會計算很久甚至無法計算出來。

閉包的其他用處

Python 的閉包不僅僅用于替換遞歸，還有很多場景可以使用閉包。比如學生成績的分類函數：

學生成績數據：

students = { 
    'Alice': 98, 
    'Bob': 67, 
    'Chris': 85, 
    'David': 75, 
    'Ella': 54, 
    'Fiona': 35, 
    'Grace': 69 
} 

現在需要根據學生成績進行分類，通常情況下我們會寫多個函數來進行分類，而分類的標準又會經常變化，這時候閉包就很方便了：

def make_student_classifier(lower_bound, upper_bound): 
    def classify_student(exam_dict): 
        return {k:v for (k,v) in exam_dict.items() if lower_bound <= v < upper_bound} 
    return classify_student 
 
grade_A = make_student_classifier(80, 100) 
grade_B = make_student_classifier(70, 80) 
grade_C = make_student_classifier(50, 70) 
grade_D = make_student_classifier(0, 50) 

如果分類標準變化，直接個性函數的參數即可，主要代碼邏輯不變，如果想查找成績分類為 A 的學生，只需要調用 grade_A(students) 即可：

In [13]: grade_A(students) 
Out[13]: {'Alice': 98, 'Chris': 85} 

閉包使用上述分類函數很容易修改且更加易讀。

最后的話

本文介紹了一種稱為 Python 閉包的技術。在大多數情況下，可以使用它來重寫遞歸函數，并且在很大程度上優于后者。

實際上，從性能的角度來看，閉包可能不是某些問題的最佳解決方案，尤其是在使用動態規劃的情況下。但是，閉包寫起來要容易一些，比遞歸性能高。當我們對性能不是很敏感時，有時寫動態計劃會有點浪費時間，但是閉包可能就足夠了。

閉包也可以用來定義一些邏輯相同但命名不同的函數，比如本文中的分類函數，在這些情況下，它更加整潔而優雅，更加易讀。

下次試試閉包吧，別用效率低下的遞歸了。

本文轉載自微信公眾號「Python七號」，可以通過以下二維碼關注。轉載本文請聯系Python七號公眾號。