如果你愿意一層一層地剝開(kāi)“遞歸”的心

引言

如果你愿意一層一層 一層地剝開(kāi)我的心 你會(huì)發(fā)現(xiàn) 你會(huì)訝異 “返回條件”是我 最壓抑 最深處的秘密 --- 遞歸函數(shù)寫(xiě)給程序員的歌。

ISCP 中說(shuō)到遞歸，用了一句話：Leap of fatich。——信仰的跳躍。指的是程序設(shè)計(jì)思想的轉(zhuǎn)變，使遞歸成為編程思想的一部分。既然是跳躍，說(shuō)明其與常見(jiàn)編程思想之間存在差異。

無(wú)論是順序、分支、循環(huán)、函數(shù)還是類，哪怕是函數(shù)式編程，其思想大體還在常人思維、生活經(jīng)驗(yàn)范圍內(nèi)。但遞歸不是這樣：遞歸是在數(shù)學(xué)、機(jī)器上進(jìn)行了較多假設(shè)和設(shè)計(jì)，理解起來(lái)較為困難。本文嘗試用 Python 來(lái)理解遞歸。

簡(jiǎn)單地說(shuō)，遞歸是函數(shù)中繼續(xù)調(diào)用自身。比如寫(xiě)一個(gè)函數(shù)，讓阿甘快跑。

def gump():    print('Running...')    gump()

運(yùn)行這個(gè)函數(shù)，如下是這個(gè)函數(shù)運(yùn)行和捕獲異常的結(jié)果。

程序在輸出 997 個(gè) Running 之后，報(bào)出了 RecursionError 異常。其具體信息是：”maximum recursion depth exceeded in comparison“，也就是超過(guò)最大遞歸深度。

超過(guò)最大遞歸深度：就是超過(guò)算機(jī)設(shè)置的遞歸層次限制。在堆棧類設(shè)計(jì)的程序語(yǔ)言（Python 就是基于棧的虛擬機(jī)）中，就是突破了調(diào)用棧的高度，這種異常稱為 Stack Overflow（棧溢出），這也是 IT 界著名網(wǎng)站 Stackoverflow.com 的命名來(lái)源。

以上的程序 gump 函數(shù)中調(diào)用了 gump，這個(gè)函數(shù)就是遞歸函數(shù)。但是這個(gè)遞歸函數(shù)沒(méi)有什么用處，要寫(xiě)一個(gè)有用處的遞歸函數(shù)，需要滿足如下三點(diǎn)。

定義遞歸函數(shù)的三點(diǎn)

定義一個(gè)遞歸函數(shù)，需要指出初始化條件、結(jié)束條件、上下層變化關(guān)系這三點(diǎn)。我們以階乘為例，來(lái)一步步定義這個(gè)函數(shù)。

首先，我們小學(xué)二年級(jí)就知道 5 的階乘的定義是這樣的：5!= 5*4*3*2*1，代數(shù)公式是 n!=n*(n-1)...*2*1 ，進(jìn)而我們能推出如下的公式：n!=n*(n-1)!

其實(shí)，是先發(fā)現(xiàn)了遞歸公式，才能有遞歸函數(shù)。根據(jù)這個(gè)公式，我們就可以寫(xiě)出求階乘的遞歸函數(shù)了：

def factrial(n):    if n <= 1:        return 1    else :        return n * factrial1(n-1)

在這里，三個(gè)條件是這么定義的。

初始條件：定義函數(shù)def factrial(n):這里的 n 就是需要求的階乘。

結(jié)束條件：也就是遞歸函數(shù)調(diào)用到最后（末、深）時(shí)的終結(jié)條件：if n <= 1:return 1。這其實(shí)相當(dāng)于求 1!的結(jié)果，就是 1。

定義上下層之間的變化關(guān)系：意思是定義遞歸函數(shù)的調(diào)用關(guān)系，也就是上層是怎么（深入）調(diào)用下層的。這里是：return n * factrial(n-1)。

我們把這三個(gè)條件組裝起來(lái)，就構(gòu)成了求階乘的遞歸函數(shù)。首先寫(xiě)終結(jié)條件，便于遞歸函數(shù)終結(jié)，然后寫(xiě)變化關(guān)系，構(gòu)成遞歸函數(shù)。

調(diào)用測(cè)試，factrial(5)結(jié)果為 120。結(jié)果正確，運(yùn)行成功。

遞歸相關(guān)特性

Python 中遞歸棧高度的設(shè)置

第一個(gè)實(shí)例程序中，當(dāng)我們超出了系統(tǒng)的限制后，遞歸調(diào)用會(huì)報(bào)出棧溢出錯(cuò)誤。那么這個(gè)限制是多少呢？可以用這個(gè)命令查看：import sys;print(sys.getrecursionlimit())。而且這個(gè)值是可以設(shè)置的：sys.setrecursionlimit(6)。這規(guī)定了函數(shù)調(diào)用棧的最高高度。

尾遞歸優(yōu)化

如上求階乘的程序中，最后一句話中的return n * factrial1(n-1)可以看出，這是一個(gè)表達(dá)式。這個(gè)表達(dá)式是求乘法，其中一個(gè)參數(shù)是常數(shù)，另一個(gè)參數(shù)是函數(shù)調(diào)用的結(jié)果。也就是說(shuō)，這個(gè)表達(dá)式是延遲求解的：只有等程序進(jìn)入執(zhí)行，并返回結(jié)果后，才能再返回給更上一級(jí)結(jié)果。

更容易理解的是，假設(shè)我們是一個(gè) CPU，我們?cè)谶@里需要深入 factrial1(n-1)，進(jìn)而深入 factrial1(n-2)一直深入到 factrial1(0)，才能產(chǎn)生一個(gè)確定的結(jié)果，返回給上一級(jí)調(diào)用函數(shù)，再返回給更上一次的調(diào)用函數(shù)。也就是我們進(jìn)入了函數(shù)調(diào)用鏈，然后再原路返回各個(gè)結(jié)果。

無(wú)疑，如上這個(gè)復(fù)雜的過(guò)程是低效的。怎么加速呢？方法就是尾遞歸優(yōu)化：在調(diào)用函數(shù)式，不使用表達(dá)式，直接調(diào)用函數(shù)。

def factrial2(n,base = 1):    if n <= 1:        return 1     else:        return factrial2(n-1,n*base)

以上是尾遞歸優(yōu)化后的階乘函數(shù)。但遺憾的是，Python 并不支持尾遞歸優(yōu)化，所以在 Python 中執(zhí)行如上代碼，效率并沒(méi)有得到提高。在其他諸如 C 或者 JavaScript 的語(yǔ)言中，這種寫(xiě)法可以提高效率。大家掌握思想即可。

那么，有沒(méi)有優(yōu)化遞歸的方法呢？

緩存優(yōu)化

分析遞歸函數(shù)的執(zhí)行過(guò)程，我們很容易發(fā)現(xiàn)：遞歸函數(shù)都在重復(fù)執(zhí)行之前的計(jì)算。以 factrial1(5)為例，它在執(zhí)行時(shí)，多次執(zhí)行了 factrial1 函數(shù)，但是這些調(diào)用的參數(shù)只有六種：0 , 1 , 2 , 3 , 4 , 5。如果能夠緩存每次運(yùn)算的結(jié)果，想必會(huì)比每次重新計(jì)算要快。

我們作如下修改：

rs = [1, 1]def factrial3 (n):    try:        return rs[n]    except:        if n <= 1:            return 1        else:            rs.append(n*factrial3(n-1))            return rs[-1]

程序 factrial3 定義之前，首先定義了全局變量 rs，他會(huì)保留函數(shù)不同參數(shù)的計(jì)算結(jié)果。當(dāng)調(diào)用時(shí)，首先判斷 rs 變量中有沒(méi)有這個(gè)暫存的結(jié)果，若有，直接采用，若沒(méi)有則計(jì)算之。

Python 標(biāo)準(zhǔn)庫(kù)中的 functools.lru_cache 裝飾器，正是采用這個(gè)機(jī)制，來(lái)實(shí)現(xiàn)遞歸加速。使用裝飾器的代碼是這樣。

import functools
@functools.lru_cache()def factrial4(n):    if n <= 1:        return 1    else:        return n*factrial4(n-1)

如上代碼，真的能加速遞歸調(diào)用么？我們采用如下代碼測(cè)試：

import timeitprint(timeit.timeit('factrial1(10)',globals=globals()))print(timeit.timeit('factrial2(10)',globals=globals()))print(timeit.timeit('factrial3(10)',globals=globals()))print(timeit.timeit('factrial4(10)',globals=globals()))

結(jié)果如下：

1.74919749955135862.0833343959732070.121600316988066390.11237836531568357

可見(jiàn)：

?一、對(duì)比前兩個(gè)函數(shù)可知，尾遞歸優(yōu)化后的函數(shù)并沒(méi)有加速。?二、自編寫(xiě)的緩存優(yōu)化，作用很大。?三、系統(tǒng)自帶的@functools.lru_cache()裝飾器，效果和自編的緩存優(yōu)化相差不大。

總結(jié)

本文分析了遞歸的含義，及定義遞歸函數(shù)的三個(gè)注意事項(xiàng)。分析了遞歸的棧高度設(shè)置，介紹了尾遞歸優(yōu)化，分析了 Python 標(biāo)準(zhǔn)庫(kù)中緩沖裝飾器的設(shè)計(jì)思想。

遞歸在程序設(shè)計(jì)中，有很大實(shí)用意義：深刻掌握遞歸，是我們理解程序設(shè)計(jì)思想、理解遍歷樹(shù)的重要基礎(chǔ)。

贊 賞 作 者

點(diǎn)擊下方閱讀原文加入社區(qū)會(huì)員