函數(shù)的遞歸調(diào)用
成都網(wǎng)絡(luò)公司-成都網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián)十載經(jīng)驗(yàn)成就非凡，專業(yè)從事網(wǎng)站設(shè)計(jì)制作、成都做網(wǎng)站，成都網(wǎng)頁設(shè)計(jì)，成都網(wǎng)頁制作，軟文發(fā)稿，廣告投放等。十載來已成功提供全面的成都網(wǎng)站建設(shè)方案，打造行業(yè)特色的成都網(wǎng)站建設(shè)案例，建站熱線：13518219792，我們期待您的來電！
遞歸問題是一個(gè)說簡(jiǎn)單也簡(jiǎn)單，說難也有點(diǎn)難理解的問題.我想非常有必要對(duì)其做一個(gè)總結(jié).
首先理解一下遞歸的定義，遞歸就是直接或間接的調(diào)用自身.而至于什么時(shí)候要用到遞歸，遞歸和非遞歸又有那些區(qū)別？又是一個(gè)不太容易掌握的問題，更難的是對(duì)于遞歸調(diào)用的理解.下面我們就從程序+圖形的角度對(duì)遞歸做一個(gè)全面的闡述.
我們從常見到的遞歸問題開始:
1 階層函數(shù)
#include iostream
using namespace std;
int factorial(int n)
{
if (n == 0)
{
return 1;
}
else
{
int result = factorial(n-1);
return n * result;
}
}
int main()
{
int x = factorial(3);
cout x endl;
return 0;
}
這是一個(gè)遞歸求階層函數(shù)的實(shí)現(xiàn)。很多朋友只是知道該這么實(shí)現(xiàn)的，也清楚它是通過不斷的遞歸調(diào)用求出的結(jié)果.但他們有些不清楚中間發(fā)生了些什么.下面我們用圖對(duì)此做一個(gè)清楚的流程:
根據(jù)上面這個(gè)圖，大家可以很清楚的看出來這個(gè)函數(shù)的執(zhí)行流程。我們的階層函數(shù)factorial被調(diào)用了4次.并且我們可以看出在調(diào)用后面的調(diào)用中，前面的調(diào)用并不退出。他們同時(shí)存在內(nèi)存中?？梢娺@是一件很浪費(fèi)資源的事情。我們?cè)摯蔚膮?shù)是3.如果我們傳遞10000呢。那結(jié)果就可想而知了.肯定是溢出了.就用int型來接收結(jié)果別說10000，100就會(huì)產(chǎn)生溢出.即使不溢出我想那肯定也是見很浪費(fèi)資源的事情.我們可以做一個(gè)粗略的估計(jì):每次函數(shù)調(diào)用就單變量所需的內(nèi)存為:兩個(gè)int型變量.n和result.在32位機(jī)器上占8B.那么10000就需要10001次函數(shù)調(diào)用.共需10001*8/1024 = 78KB.這只是變量所需的內(nèi)存空間.其它的函數(shù)調(diào)用時(shí)函數(shù)入口地址等仍也需要占用內(nèi)存空間?？梢娺f歸調(diào)用產(chǎn)生了一個(gè)不小的開銷.
2 斐波那契數(shù)列
int Fib(int n)
{
if (n = 1)
{
return n;
}
else
{
return Fib(n-1) + Fib(n-2);
}
}
這個(gè)函數(shù)遞歸與上面的那個(gè)有些不同.每次調(diào)用函數(shù)都會(huì)引起另外兩次的調(diào)用.最后將結(jié)果逐級(jí)返回.
我們可以看出這個(gè)遞歸函數(shù)同樣在調(diào)用后買的函數(shù)時(shí)，前面的不退出而是在等待后面的結(jié)果，最后求出總結(jié)果。這就是遞歸.
3
#include iostream
using namespace std;
void recursiveFunction1(int num)
{
if (num 5)
{
cout num endl;
recursiveFunction1(num+1);
}
}
void recursiveFunction2(int num)
{
if (num 5)
{
recursiveFunction2(num+1);
cout num endl;
}
}
int main()
{
recursiveFunction1(0);
recursiveFunction2(0);
return 0;
}
運(yùn)行結(jié)果:
1
2
3
4
4
3
2
1
該程序中有兩個(gè)遞歸函數(shù)。傳遞同樣的參數(shù)，但他們的輸出結(jié)果剛好相反。理解這兩個(gè)函數(shù)的調(diào)用過程可以很好的幫助我們理解遞歸:
我想能夠把上面三個(gè)函數(shù)的遞歸調(diào)用過程理解了，你已經(jīng)把遞歸調(diào)用理解的差不多了.并且從上面的遞歸調(diào)用中我們可以總結(jié)出遞歸的一個(gè)規(guī)律：他是逐級(jí)的調(diào)用，而在函數(shù)結(jié)束的時(shí)候是從最后面往前反序的結(jié)束.這種方式是很占用資源，也很費(fèi)時(shí)的。但是有的時(shí)候使用遞歸寫出來的程序很容易理解，很易讀.
為什么使用遞歸:
1 有時(shí)候使用遞歸寫出來的程序很容易理解，很易讀.
2 有些問題只有遞歸能夠解決.非遞歸的方法無法實(shí)現(xiàn).如:漢諾塔.
遞歸的條件:
并不是說所有的問題都可以使用遞歸解決，他必須的滿足一定的條件。即有一個(gè)出口點(diǎn).也就是說當(dāng)滿足一定條件時(shí)，程序可以結(jié)束，從而完成遞歸調(diào)用，否則就陷入了無限的遞歸調(diào)用之中了.并且這個(gè)條件還要是可達(dá)到的.
遞歸有哪些優(yōu)點(diǎn):
易讀，容易理解，代碼一般比較短.
遞歸有哪些缺點(diǎn):
占用內(nèi)存資源多，費(fèi)時(shí)，效率低下.
因此在我們寫程序的時(shí)候不要輕易的使用遞歸，雖然他有他的優(yōu)點(diǎn)，但是我們要在易讀性和空間，效率上多做權(quán)衡.一般情況下我們還是使用非遞歸的方法解決問題.若一個(gè)算法非遞歸解法非常難于理解。我們使用遞歸也未嘗不可.如:二叉樹的遍歷算法.非遞歸的算法很難與理解.而相比遞歸算法就容易理解很多.
對(duì)于遞歸調(diào)用的問題，我們?cè)谇耙欢螘r(shí)間寫圖形學(xué)程序時(shí)，其中有一個(gè)四連同填充算法就是使用遞歸的方法。結(jié)果當(dāng)要填充的圖形稍微大一些時(shí)，程序就自動(dòng)關(guān)閉了.這不是一個(gè)人的問題，所有人寫出來的都是這個(gè)問題.當(dāng)時(shí)我們給與的解釋就是堆棧溢出。就多次遞歸調(diào)用占用太多的內(nèi)存資源致使堆棧溢出，程序沒有內(nèi)存資源執(zhí)行下去，從而被操作系統(tǒng)強(qiáng)制關(guān)閉了.這是一個(gè)真真切切的例子。所以我們?cè)谑褂眠f歸的時(shí)候需要權(quán)衡再三.
def Sum(m): #函數(shù)返回兩個(gè)值：遞歸次數(shù)，所求的值 if m==1:return 1,m return 1+Sum(m-1)[0],m+Sum(m-1)[1]cishu=Sum(10)[0] print cishu def Sum(m,n=1): ... if m==1:return n,m ... return n,m+Sum(m-1,n+1)[1] print Sum(10)[0] 10 print Sum(5)[0] 5
for 變量 in range(次數(shù))：被執(zhí)行的語句? ? ? ? ? ? ? ? ? ? ? ?變量：表示每次循環(huán)的次數(shù)，0-1之間
range（n）n表示產(chǎn)生0到n-1的整數(shù)序列共N個(gè)? ? ? ? ? ? ? ?range(m,n)? 產(chǎn)生m到n-1的整數(shù)序列，共n-m個(gè)
循環(huán)for語句? ：for 循環(huán)變量 in遍歷結(jié)構(gòu)：語句體1? else：語句體2?
無限循環(huán)： while條件： 語句塊
while 條件：語句體1 else: 語句體2
循環(huán)保留字：break? ? ?continue
方法1：from random import random
from time import perf_counter
DARTS=1000
hits=0.0
start =perf_counter()
for i in range(1,DARTS+1):
x,y=random(),random()
dist=pow(x**2+y**2,0.5)
if dist=1.0:
? ? hits =hits+1
pi=4*(hits/DARTS)
print("圓周率是:{}".format(pi))
print("運(yùn)行時(shí)間是{:.5f}s".format(perf_counter()-start))
方法2：
pi=0
n=100
for k in range(n):
pi += 1/pow(16,k)*(\
? ? 4/(8*k+1)-2/(8*k+4) - \
? ? 1/(8*k+5) - 1/(8*k+6))
print("圓周率值是:{}".format(pi))
def 函數(shù)名 （0個(gè)或者多個(gè)）：函數(shù)體? renturn 返回值
def 函數(shù)名 （非可選參數(shù)，可選參數(shù)）：函數(shù)體? renturn 返回值
參數(shù)傳遞的兩種方式：位置傳遞，名稱傳遞
科赫雪花：
import turtle
def koch(size,n):
if n==0:
? ? turtle.fd(size)
else:
? ? for angle in [0,60,-120,60]:
? ? ? ? turtle.left(angle)
? ? ? ? koch(size/3,n-1)
def main():
turtle.setup(400,200)
turtle.penup()
turtle.pendown()
turtle.pensize(2)
l=3
koch(600,l)
turtle.right(120)
turtle.pencolor('blue')
koch(600,l)
turtle.right(120)
turtle.pencolor('red')
koch(600,l)
turtle.speed(3000)
turtle.hideturtle()
main()
階乘：
def fact(n):
s=1
for i in range(1,n+1):
? ? s*=i
return s
c=eval(input("從鍵盤輸入一個(gè)數(shù)字"))
print("階乘結(jié)果",fact(c))
可以看出來的是，該題可以用斐波那契數(shù)列解決。
樓梯一共有n層，每次只能走1層或者2層，而要走到最終的n層。不是從n-1或者就是n-2來的。
F(1) = 1
F(2) = 2
F(n) = F(n-1) + F(n-2) (n=3)
這是遞歸寫法，但是會(huì)導(dǎo)致棧溢出。在計(jì)算機(jī)中，函數(shù)的調(diào)用是通過棧進(jìn)行實(shí)現(xiàn)的，如果遞歸調(diào)用的次數(shù)過多，就會(huì)導(dǎo)致棧溢出。
針對(duì)這種情況就要使用方法二，改成非遞歸函數(shù)。
將遞歸進(jìn)行改寫，實(shí)現(xiàn)循環(huán)就不會(huì)導(dǎo)致棧溢出
單元測(cè)試（Unit Testing）
為程序編寫測(cè)試——如果做的到位——有助于減少bug的出現(xiàn)，并可以提高我們對(duì)程序按預(yù)期目標(biāo)運(yùn)行的信心。通常，測(cè)試并不能保證正確性，因?yàn)閷?duì)大多數(shù)程序而言， 可能的輸入范圍以及可能的計(jì)算范圍是如此之大，只有其中最小的一部分能被實(shí)際地進(jìn) 行測(cè)試。盡管如此，通過仔細(xì)地選擇測(cè)試的方法和目標(biāo)，可以提高代碼的質(zhì)量。
大量不同類型的測(cè)試都可以進(jìn)行，比如可用性測(cè)試、功能測(cè)試以及整合測(cè)試等。這里, 我們只講單元測(cè)試一對(duì)單獨(dú)的函數(shù)、類與方法進(jìn)行測(cè)試，確保其符合預(yù)期的行為。
TDD的一個(gè)關(guān)鍵點(diǎn)是，當(dāng)我們想添加一個(gè)功能時(shí)——比如為類添加一個(gè)方法—— 我們首次為其編寫一個(gè)測(cè)試用例。當(dāng)然，測(cè)試將失敗，因?yàn)槲覀冞€沒有實(shí)際編寫該方法?，F(xiàn)在，我們編寫該方法，一旦方法通過了測(cè)試，就可以返回所有測(cè)試，確保我們新添加的代碼沒有任何預(yù)期外的副作用。一旦所有測(cè)試運(yùn)行完畢（包括我們?yōu)樾鹿δ芫帉懙臏y(cè)試），就可以對(duì)我們的代碼進(jìn)行檢查，并有理有據(jù)地相信程序行為符合我們的期望——當(dāng)然，前提是我們的測(cè)試是適當(dāng)?shù)摹?/p>
比如，我們編寫了一個(gè)函數(shù)，該函數(shù)在特定的索引位置插入一個(gè)字符串，可以像下面這樣開始我們的TDD：
def insert_at（string, position, insert）:
"""Returns a copy of string with insert inserted at the position
string = "ABCDE"
result =[]
for i in range(-2, len(string) + 2):
... result.append(insert_at(string, i,“-”))
result[:5]
['ABC-DE', 'ABCD-E', '-ABCDE','A-BCDE', 'AB-CDE']
result[5:]
['ABC-DE', 'ABCD-E', 'ABCDE-', 'ABCDE-']
"""
return string
對(duì)不返回任何參數(shù)的函數(shù)或方法（通常返回None）,我們通常賦予其由pass構(gòu)成的一個(gè)suite,對(duì)那些返回值被試用的，我們或者返回一個(gè)常數(shù)（比如0）,或者某個(gè)不變的參數(shù)——這也是我們這里所做的。（在更復(fù)雜的情況下，返回fake對(duì)象可能更有用一一對(duì)這樣的類，提供mock對(duì)象的第三方模塊是可用的。）
運(yùn)行doctest時(shí)會(huì)失敗，并列出每個(gè)預(yù)期內(nèi)的字符串（'ABCD-EF'、'ABCDE-F' 等），及其實(shí)際獲取的字符串（所有的都是'ABCD-EF'）。一旦確定doctest是充分的和正確的，就可以編寫該函數(shù)的主體部分，在本例中只是簡(jiǎn)單的return string[:position] + insert+string[position:]。（如果我們編寫的是 return string[:position] + insert,之后復(fù)制 string [:position]并將其粘貼在末尾以便減少一些輸入操作，那么doctest會(huì)立即提示錯(cuò)誤。）
Python的標(biāo)準(zhǔn)庫(kù)提供了兩個(gè)單元測(cè)試模塊，一個(gè)是doctest,這里和前面都簡(jiǎn)單地提到過，另一個(gè)是unittest。此外，還有一些可用于Python的第三方測(cè)試工具。其中最著名的兩個(gè)是nose (code.google.com/p/python-nose)與py.test (codespeak.net/py/dist/test/test.html), nose 致力于提供比標(biāo)準(zhǔn)的unittest 模塊更廣泛的功能，同時(shí)保持與該模塊的兼容性，py.test則采用了與unittest有些不同的方法，試圖盡可能消除樣板測(cè)試代碼。這兩個(gè)第三方模塊都支持測(cè)試發(fā)現(xiàn)，因此沒必要寫一個(gè)總體的測(cè)試程序——因?yàn)槟K將自己搜索測(cè)試程序。這使得測(cè)試整個(gè)代碼樹或某一部分 (比如那些已經(jīng)起作用的模塊)變得很容易。那些對(duì)測(cè)試嚴(yán)重關(guān)切的人，在決定使用哪個(gè)測(cè)試工具之前，對(duì)這兩個(gè)(以及任何其他有吸引力的)第三方模塊進(jìn)行研究都是值 得的。
創(chuàng)建doctest是直截了當(dāng)?shù)模何覀冊(cè)谀K中編寫測(cè)試、函數(shù)、類與方法的docstrings。 對(duì)于模塊，我們簡(jiǎn)單地在末尾添加了 3行：
if __name__ =="__main__":
import doctest
doctest.testmod()
在程序內(nèi)部使用doctest也是可能的。比如，blocks.py程序(其模塊在后面)有自己函數(shù)的doctest，但以如下代碼結(jié)尾：
if __name__== "__main__":
main()
這里簡(jiǎn)單地調(diào)用了程序的main()函數(shù)，并且沒有執(zhí)行程序的doctest。要實(shí)驗(yàn)程序的 doctest,有兩種方法。一種是導(dǎo)入doctest模塊，之后運(yùn)行程序---比如，在控制臺(tái)中輸 入 python3 -m doctest blocks.py (在 Wndows 平臺(tái)上，使用類似于 C:Python3 lpython.exe 這樣的形式替代python3)。如果所有測(cè)試運(yùn)行良好，就沒有輸出，因此，我們可能寧愿執(zhí)行python3-m doctest blocks.py-v,因?yàn)檫@會(huì)列出每個(gè)執(zhí)行的doctest,并在最后給出結(jié)果摘要。
另一種執(zhí)行doctest的方法是使用unittest模塊創(chuàng)建單獨(dú)的測(cè)試程序。在概念上， unittest模塊是根據(jù)Java的JUnit單元測(cè)試庫(kù)進(jìn)行建模的，并用于創(chuàng)建包含測(cè)試用例的測(cè)試套件。unittest模塊可以基于doctests創(chuàng)建測(cè)試用例，而不需要知道程序或模塊包含的任何事物——只要知道其包含doctest即可。因此，為給blocks.py程序制作一個(gè)測(cè)試套件，我們可以創(chuàng)建如下的簡(jiǎn)單程序(將其稱為test_blocks.py)：
import doctest
import unittest
import blocks
suite = unittest.TestSuite()
suite.addTest(doctest.DocTestSuite(blocks))
runner = unittest.TextTestRunner()
print(runner.run(suite))
注意，如果釆用這種方法，程序的名稱上會(huì)有一個(gè)隱含的約束：程序名必須是有效的模塊名。因此，名為convert-incidents.py的程序的測(cè)試不能寫成這樣。因?yàn)閕mport convert-incidents不是有效的，在Python標(biāo)識(shí)符中，連接符是無效的（避開這一約束是可能的，但最簡(jiǎn)單的解決方案是使用總是有效模塊名的程序文件名，比如，使用下劃線替換連接符）。這里展示的結(jié)構(gòu)（創(chuàng)建一個(gè)測(cè)試套件，添加一個(gè)或多個(gè)測(cè)試用例或測(cè)試套件，運(yùn)行總體的測(cè)試套件，輸出結(jié)果）是典型的機(jī)遇unittest的測(cè)試。運(yùn)行時(shí)，這一特定實(shí)例產(chǎn)生如下結(jié)果：
...
.............................................................................................................
Ran 3 tests in 0.244s
OK
每次執(zhí)行一個(gè)測(cè)試用例時(shí)，都會(huì)輸出一個(gè)句點(diǎn)（因此上面的輸出最前面有3個(gè)句點(diǎn)），之后是一行連接符，再之后是測(cè)試摘要（如果有任何一個(gè)測(cè)試失敗，就會(huì)有更多的輸出信息）。
如果我們嘗試將測(cè)試分離開（典型情況下是要測(cè)試的每個(gè)程序和模塊都有一個(gè)測(cè)試用例），就不要再使用doctests,而是直接使用unittest模塊的功能——尤其是我們習(xí)慣于使用JUnit方法進(jìn)行測(cè)試時(shí)ounittest模塊會(huì)將測(cè)試分離于代碼——對(duì)大型項(xiàng)目（測(cè)試編寫人員與開發(fā)人員可能不一致）而言，這種方法特別有用。此外，unittest單元測(cè)試編寫為獨(dú)立的Python模塊，因此，不會(huì)像在docstring內(nèi)部編寫測(cè)試用例時(shí)受到兼容性和明智性的限制。
unittest模塊定義了 4個(gè)關(guān)鍵概念。測(cè)試夾具是一個(gè)用于描述創(chuàng)建測(cè)試（以及用完之后將其清理）所必需的代碼的術(shù)語，典型實(shí)例是創(chuàng)建測(cè)試所用的一個(gè)輸入文件，最后刪除輸入文件與結(jié)果輸出文件。測(cè)試套件是一組測(cè)試用例的組合。測(cè)試用例是測(cè)試的基本單元—我們很快就會(huì)看到實(shí)例。測(cè)試運(yùn)行者是執(zhí)行一個(gè)或多個(gè)測(cè)試套件的對(duì)象。
典型情況下，測(cè)試套件是通過創(chuàng)建unittest.TestCase的子類實(shí)現(xiàn)的，其中每個(gè)名稱 以“test”開頭的方法都是一個(gè)測(cè)試用例。如果我們需要完成任何創(chuàng)建操作，就可以在一個(gè)名為setUp()的方法中實(shí)現(xiàn)；類似地，對(duì)任何清理操作，也可以實(shí)現(xiàn)一個(gè)名為 tearDown()的方法。在測(cè)試內(nèi)部，有大量可供我們使用的unittest.TestCase方法，包括 assertTrue()、assertEqual()、assertAlmostEqual()（對(duì)于測(cè)試浮點(diǎn)數(shù)很有用）、assertRaises() 以及更多，還包括很多對(duì)應(yīng)的逆方法，比如assertFalse()、assertNotEqual()、failIfEqual()、 failUnlessEqual ()等。
unittest模塊進(jìn)行了很好的歸檔，并且提供了大量功能，但在這里我們只是通過一 個(gè)非常簡(jiǎn)單的測(cè)試套件來感受一下該模塊的使用。這里將要使用的實(shí)例,該練習(xí)要求創(chuàng)建一個(gè)Atomic模塊，該模塊可以用作一 個(gè)上下文管理器，以確?；蛘咚懈淖兌紤?yīng)用于某個(gè)列表、集合或字典，或者所有改變都不應(yīng)用。作為解決方案提供的Atomic.py模塊使用30行代碼來實(shí)現(xiàn)Atomic類， 并提供了 100行左右的模塊doctest。這里，我們將創(chuàng)建test_Atomic.py模塊，并使用 unittest測(cè)試替換doctest,以便可以刪除doctest。
在編寫測(cè)試模塊之前，我們需要思考都需要哪些測(cè)試。我們需要測(cè)試3種不同的數(shù)據(jù)類型：列表、集合與字典。對(duì)于列表，需要測(cè)試的是插入項(xiàng)、刪除項(xiàng)或修改項(xiàng)的值。對(duì)于集合，我們必須測(cè)試向其中添加或刪除一個(gè)項(xiàng)。對(duì)于字典，我們必須測(cè)試的是插入一個(gè)項(xiàng)、修改一個(gè)項(xiàng)的值、刪除一個(gè)項(xiàng)。此外，還必須要測(cè)試的是在失敗的情況下，不會(huì)有任何改變實(shí)際生效。
結(jié)構(gòu)上看，測(cè)試不同數(shù)據(jù)類型實(shí)質(zhì)上是一樣的，因此，我們將只為測(cè)試列表編寫測(cè)試用例，而將其他的留作練習(xí)。test_Atomic.py模塊必須導(dǎo)入unittest模塊與要進(jìn)行測(cè)試的Atomic模塊。
創(chuàng)建unittest文件時(shí)，我們通常創(chuàng)建的是模塊而非程序。在每個(gè)模塊內(nèi)部，我們定義一個(gè)或多個(gè)unittest.TestCase子類。比如，test_Atomic.py模塊中僅一個(gè)單獨(dú)的 unittest-TestCase子類，也就是TestAtomic (稍后將對(duì)其進(jìn)行講解)，并以如下兩行結(jié)束:
if name == "__main__":
unittest.main()
這兩行使得該模塊可以單獨(dú)運(yùn)行。當(dāng)然，該模塊也可以被導(dǎo)入并從其他測(cè)試程序中運(yùn)行——如果這只是多個(gè)測(cè)試套件中的一個(gè)，這一點(diǎn)是有意義的。
如果想要從其他測(cè)試程序中運(yùn)行test_Atomic.py模塊，那么可以編寫一個(gè)與此類似的程序。我們習(xí)慣于使用unittest模塊執(zhí)行doctests,比如：
import unittest
import test_Atomic
suite = unittest.TestLoader().loadTestsFromTestCase(test_Atomic.TestAtomic)
runner = unittest.TextTestRunner()
pnnt(runner.run(suite))
這里，我們已經(jīng)創(chuàng)建了一個(gè)單獨(dú)的套件，這是通過讓unittest模塊讀取test_Atomic 模塊實(shí)現(xiàn)的，并且使用其每一個(gè)test*()方法(本實(shí)例中是test_list_success()、test_list_fail()，稍后很快就會(huì)看到)作為測(cè)試用例。
我們現(xiàn)在將查看TestAtomic類的實(shí)現(xiàn)。對(duì)通常的子類(不包括unittest.TestCase 子類)，不怎么常見的是，沒有必要實(shí)現(xiàn)初始化程序。在這一案例中，我們將需要建立 一個(gè)方法，但不需要清理方法，并且我們將實(shí)現(xiàn)兩個(gè)測(cè)試用例。
def setUp(self)：
self.original_list = list(range(10))
我們已經(jīng)使用了 unittest.TestCase.setUp()方法來創(chuàng)建單獨(dú)的測(cè)試數(shù)據(jù)片段。
def test_list_succeed(self):
items = self.original_list[:]
with Atomic.Atomic(items) as atomic:
atomic.append(1999)
atomic.insert(2, -915)
del atomic[5]
atomic[4]= -782
atomic.insert(0, -9)
self.assertEqual(items,
[-9, 0, 1, -915, 2, -782, 5, 6, 7, 8, 9, 1999])
def test_list_fail(self):
items = self.original_list[:]
with self.assertRaises(AttributeError):
with Atomic.Atomic(items) as atomic:
atomic.append(1999)
atomic.insert(2, -915)
del atomic[5]
atomic[4] = -782
atomic.poop() # Typo
self.assertListEqual(items, self.original_list)
這里，我們直接在測(cè)試方法中編寫了測(cè)試代碼，而不需要一個(gè)內(nèi)部函數(shù)，也不再使用unittest.TestCase.assertRaised()作為上下文管理器(期望代碼產(chǎn)生AttributeError)。 最后我們也使用了 Python 3.1 的 unittest.TestCase.assertListEqual()方法。
正如我們已經(jīng)看到的，Python的測(cè)試模塊易于使用，并且極為有用，在我們使用 TDD的情況下更是如此。它們還有比這里展示的要多得多的大量功能與特征——比如，跳過測(cè)試的能力，這有助于理解平臺(tái)差別——并且這些都有很好的文檔支持。缺失的一個(gè)功能——但nose與py.test提供了——是測(cè)試發(fā)現(xiàn)，盡管這一特征被期望在后續(xù)的Python版本(或許與Python 3.2—起)中出現(xiàn)。
性能剖析（Profiling）
如果程序運(yùn)行很慢，或者消耗了比預(yù)期內(nèi)要多得多的內(nèi)存，那么問題通常是選擇的算法或數(shù)據(jù)結(jié)構(gòu)不合適，或者是以低效的方式進(jìn)行實(shí)現(xiàn)。不管問題的原因是什么， 最好的方法都是準(zhǔn)確地找到問題發(fā)生的地方,而不只是檢査代碼并試圖對(duì)其進(jìn)行優(yōu)化。 隨機(jī)優(yōu)化會(huì)導(dǎo)致引入bug,或者對(duì)程序中本來對(duì)程序整體性能并沒有實(shí)際影響的部分進(jìn)行提速，而這并非解釋器耗費(fèi)大部分時(shí)間的地方。
在深入討論profiling之前，注意一些易于學(xué)習(xí)和使用的Python程序設(shè)計(jì)習(xí)慣是有意義的，并且對(duì)提高程序性能不無裨益。這些技術(shù)都不是特定于某個(gè)Python版本的， 而是合理的Python程序設(shè)計(jì)風(fēng)格。第一，在需要只讀序列時(shí)，最好使用元組而非列表； 第二，使用生成器，而不是創(chuàng)建大的元組和列表并在其上進(jìn)行迭代處理；第三，盡量使用Python內(nèi)置的數(shù)據(jù)結(jié)構(gòu) dicts、lists、tuples 而不實(shí)現(xiàn)自己的自定義結(jié)構(gòu)，因?yàn)閮?nèi)置的數(shù)據(jù)結(jié)構(gòu)都是經(jīng)過了高度優(yōu)化的；第四，從小字符串中產(chǎn)生大字符串時(shí)， 不要對(duì)小字符串進(jìn)行連接，而是在列表中累積，最后將字符串列表結(jié)合成為一個(gè)單獨(dú)的字符串；第五，也是最后一點(diǎn)，如果某個(gè)對(duì)象(包括函數(shù)或方法)需要多次使用屬性進(jìn)行訪問(比如訪問模塊中的某個(gè)函數(shù))，或從某個(gè)數(shù)據(jù)結(jié)構(gòu)中進(jìn)行訪問，那么較好的做法是創(chuàng)建并使用一個(gè)局部變量來訪問該對(duì)象，以便提供更快的訪問速度。
Python標(biāo)準(zhǔn)庫(kù)提供了兩個(gè)特別有用的模塊，可以輔助調(diào)査代碼的性能問題。一個(gè)是timeit模塊——該模塊可用于對(duì)一小段Python代碼進(jìn)行計(jì)時(shí)，并可用于諸如對(duì)兩個(gè)或多個(gè)特定函數(shù)或方法的性能進(jìn)行比較等場(chǎng)合。另一個(gè)是cProfile模塊，可用于profile 程序的性能——該模塊對(duì)調(diào)用計(jì)數(shù)與次數(shù)進(jìn)行了詳細(xì)分解，以便發(fā)現(xiàn)性能瓶頸所在。
為了解timeit模塊，我們將查看一些小實(shí)例。假定有3個(gè)函數(shù)function_a()、 function_b()、function_c(), 3個(gè)函數(shù)執(zhí)行同樣的計(jì)算，但分別使用不同的算法。如果將這些函數(shù)放于同一個(gè)模塊中(或分別導(dǎo)入)，就可以使用timeit模塊對(duì)其進(jìn)行運(yùn)行和比較。下面給出的是模塊最后使用的代碼：
if __name__ == "__main__":
repeats = 1000
for function in ("function_a", "function_b", "function_c"):
t = timeit.Timer("{0}(X, Y)".format(function),"from __main__ import {0}, X, Y".format(function))
sec = t.timeit(repeats) / repeats
print("{function}() {sec:.6f} sec".format(**locals()))
賦予timeit.Timer()構(gòu)造子的第一個(gè)參數(shù)是我們想要執(zhí)行并計(jì)時(shí)的代碼，其形式是字符串。這里，該字符串是“function_a(X,Y)”；第二個(gè)參數(shù)是可選的，還是一個(gè)待執(zhí)行的字符串，這一次是在待計(jì)時(shí)的代碼之前，以便提供一些建立工作。這里，我們從 __main__ (即this)模塊導(dǎo)入了待測(cè)試的函數(shù)，還有兩個(gè)作為輸入數(shù)據(jù)傳入的變量(X 與Y),這兩個(gè)變量在該模塊中是作為全局變量提供的。我們也可以很輕易地像從其他模塊中導(dǎo)入數(shù)據(jù)一樣來進(jìn)行導(dǎo)入操作。
調(diào)用timeit.Timer對(duì)象的timeit()方法時(shí)，首先將執(zhí)行構(gòu)造子的第二個(gè)參數(shù)(如果有)， 之后執(zhí)行構(gòu)造子的第一個(gè)參數(shù)并對(duì)其執(zhí)行時(shí)間進(jìn)行計(jì)時(shí)。timeit.Timer.timeit()方法的返回值是以秒計(jì)數(shù)的時(shí)間，類型是float。默認(rèn)情況下，timeit()方法重復(fù)100萬次，并返回所 有這些執(zhí)行的總秒數(shù)，但在這一特定案例中，只需要1000次反復(fù)就可以給出有用的結(jié)果, 因此對(duì)重復(fù)計(jì)數(shù)次數(shù)進(jìn)行了顯式指定。在對(duì)每個(gè)函數(shù)進(jìn)行計(jì)時(shí)后，使用重復(fù)次數(shù)對(duì)總數(shù)進(jìn)行除法操作，就得到了平均執(zhí)行時(shí)間，并在控制臺(tái)中打印出函數(shù)名與執(zhí)行時(shí)間。
function_a() 0.001618 sec
function_b() 0.012786 sec
function_c() 0.003248 sec
在這一實(shí)例中，function_a()顯然是最快的——至少對(duì)于這里使用的輸入數(shù)據(jù)而言。 在有些情況下一一比如輸入數(shù)據(jù)不同會(huì)對(duì)性能產(chǎn)生巨大影響——可能需要使用多組輸入數(shù)據(jù)對(duì)每個(gè)函數(shù)進(jìn)行測(cè)試，以便覆蓋有代表性的測(cè)試用例，并對(duì)總執(zhí)行時(shí)間或平均執(zhí)行時(shí)間進(jìn)行比較。
有時(shí)監(jiān)控自己的代碼進(jìn)行計(jì)時(shí)并不是很方便，因此timeit模塊提供了一種在命令行中對(duì)代碼執(zhí)行時(shí)間進(jìn)行計(jì)時(shí)的途徑。比如，要對(duì)MyModule.py模塊中的函數(shù)function_a()進(jìn)行計(jì)時(shí)，可以在控制臺(tái)中輸入如下命令：python3 -m timeit -n 1000 -s "from MyModule import function_a, X, Y" "function_a(X, Y)"(與通常所做的一樣，對(duì) Windows 環(huán)境，我們必須使用類似于C:Python3lpython.exe這樣的內(nèi)容來替換python3)。-m選項(xiàng)用于Python 解釋器，使其可以加載指定的模塊(這里是timeit),其他選項(xiàng)則由timeit模塊進(jìn)行處理。 -n選項(xiàng)指定了循環(huán)計(jì)數(shù)次數(shù)，-s選項(xiàng)指定了要建立，最后一個(gè)參數(shù)是要執(zhí)行和計(jì)時(shí)的代碼。命令完成后，會(huì)向控制臺(tái)中打印運(yùn)行結(jié)果，比如：
1000 loops, best of 3: 1.41 msec per loop
之后我們可以輕易地對(duì)其他兩個(gè)函數(shù)進(jìn)行計(jì)時(shí)，以便對(duì)其進(jìn)行整體的比較。
cProfile模塊(或者profile模塊，這里統(tǒng)稱為cProfile模塊)也可以用于比較函數(shù) 與方法的性能。與只是提供原始計(jì)時(shí)的timeit模塊不同的是，cProfile模塊精確地展示 了有什么被調(diào)用以及每個(gè)調(diào)用耗費(fèi)了多少時(shí)間。下面是用于比較與前面一樣的3個(gè)函數(shù)的代碼：
if __name__ == "__main__":
for function in ("function_a", "function_b", "function_c"):
cProfile.run("for i in ranged 1000): {0}(X, Y)".format(function))
我們必須將重復(fù)的次數(shù)放置在要傳遞給cProfile.run()函數(shù)的代碼內(nèi)部，但不需要做任何創(chuàng)建，因?yàn)槟K函數(shù)會(huì)使用內(nèi)省來尋找需要使用的函數(shù)與變量。這里沒有使用顯式的print()語句，因?yàn)槟J(rèn)情況下，cProfile.run()函數(shù)會(huì)在控制臺(tái)中打印其輸出。下面給出的是所有函數(shù)的相關(guān)結(jié)果(有些無關(guān)行被省略，格式也進(jìn)行了稍許調(diào)整，以便與頁面適應(yīng))：
1003 function calls in 1.661 CPU seconds
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.003 0.003 1.661 1.661 :1 ( )
1000 1.658 0.002 1.658 0.002 MyModule.py:21 (function_a)
1 0.000 0.000 1.661 1.661 {built-in method exec}
5132003 function calls in 22.700 CPU seconds
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.487 0.487 22.700 22.700 : 1 ( )
1000 0.011 0.000 22.213 0.022 MyModule.py:28(function_b)
5128000 7.048 0.000 7.048 0.000 MyModule.py:29( )
1000 0.00 50.000 0.005 0.000 {built-in method bisectjeft}
1 0.000 0.000 22.700 22.700 {built-in method exec}
1000 0.001 0.000 0.001 0.000 {built-in method len}
1000 15.149 0.015 22.196 0.022 {built-in method sorted}
5129003 function calls in 12.987 CPU seconds
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.205 0.205 12.987 12.987 :l ( )
1000 6.472 0.006 12.782 0.013 MyModule.py:36(function_c)
5128000 6.311 0.000 6.311 0.000 MyModule.py:37( )
1 0.000 0.000 12.987 12.987 {built-in method exec}
ncalls ("調(diào)用的次數(shù)")列列出了對(duì)指定函數(shù)(在filename:lineno(function)中列出) 的調(diào)用次數(shù)?；叵胍幌挛覀冎貜?fù)了 1000次調(diào)用，因此必須將這個(gè)次數(shù)記住。tottime (“總的時(shí)間”)列列出了某個(gè)函數(shù)中耗費(fèi)的總時(shí)間，但是排除了函數(shù)調(diào)用的其他函數(shù)內(nèi)部花費(fèi)的時(shí)間。第一個(gè)percall列列出了對(duì)函數(shù)的每次調(diào)用的平均時(shí)間(tottime // ncalls)。 cumtime ("累積時(shí)間")列出了在函數(shù)中耗費(fèi)的時(shí)間，并且包含了函數(shù)調(diào)用的其他函數(shù)內(nèi)部花費(fèi)的時(shí)間。第二個(gè)percall列列出了對(duì)函數(shù)的每次調(diào)用的平均時(shí)間，包括其調(diào)用的函數(shù)耗費(fèi)的時(shí)間。
這種輸出信息要比timeit模塊的原始計(jì)時(shí)信息富有啟發(fā)意義的多。我們立即可以發(fā)現(xiàn)，function_b()與function_c()使用了被調(diào)用5000次以上的生成器，使得它們的速度至少要比function_a()慢10倍以上。并且，function_b()調(diào)用了更多通常意義上的函數(shù)，包括調(diào)用內(nèi)置的sorted()函數(shù)，這使得其幾乎比function_c()還要慢兩倍。當(dāng)然,timeit() 模塊提供了足夠的信息來查看計(jì)時(shí)上存在的這些差別，但cProfile模塊允許我們了解為什么會(huì)存在這些差別。正如timeit模塊允許對(duì)代碼進(jìn)行計(jì)時(shí)而又不需要對(duì)其監(jiān)控一樣，cProfile模塊也可以做到這一點(diǎn)。然而，從命令行使用cProfile模塊時(shí)，我們不能精確地指定要執(zhí)行的 是什么——而只是執(zhí)行給定的程序或模塊，并報(bào)告所有這些的計(jì)時(shí)結(jié)果。需要使用的 命令行是python3 -m cProfile programOrModule.py,產(chǎn)生的輸出信息與前面看到的一 樣，下面給出的是輸出信息樣例，格式上進(jìn)行了一些調(diào)整，并忽略了大多數(shù)行：
10272458 function calls (10272457 primitive calls) in 37.718 CPU secs
ncalls tottime percall cumtime percall filename:lineno(function)
10.000 0.000 37.718 37.718 :1 ( )
10.719 0.719 37.717 37.717 :12( )
1000 1.569 0.002 1.569 0.002 :20(function_a)
1000 0.011 0.000 22.560 0.023 :27(function_b)
5128000 7.078 0.000 7.078 0.000 :28( )
1000 6.510 0.007 12.825 0.013 :35(function_c)
5128000 6.316 0.000 6.316 0.000 :36( )
在cProfile術(shù)語學(xué)中，原始調(diào)用指的就是非遞歸的函數(shù)調(diào)用。
以這種方式使用cProfile模塊對(duì)于識(shí)別值得進(jìn)一步研究的區(qū)域是有用的。比如，這里 我們可以清晰地看到function_b()需要耗費(fèi)更長(zhǎng)的時(shí)間，但是我們?cè)鯓荧@取進(jìn)一步的詳細(xì)資料？我們可以使用cProfile.run("function_b()")來替換對(duì)function_b()的調(diào)用。或者可以保存完全的profile數(shù)據(jù)并使用pstats模塊對(duì)其進(jìn)行分析。要保存profile,就必須對(duì)命令行進(jìn)行稍許修改:python3 -m cProfile -o profileDataFile programOrModule.py。 之后可以對(duì) profile 數(shù)據(jù)進(jìn)行分析，比如啟動(dòng)IDLE,導(dǎo)入pstats模塊，賦予其已保存的profileDataFile,或者也可以在控制臺(tái)中交互式地使用pstats。
下面給出的是一個(gè)非常短的控制臺(tái)會(huì)話實(shí)例，為使其適合頁面展示，進(jìn)行了適當(dāng)調(diào)整，我們自己的輸入則以粗體展示：
$ python3 -m cProfile -o profile.dat MyModule.py
$ python3 -m pstats
Welcome to the profile statistics browser.
% read profile.dat
profile.dat% callers function_b
Random listing order was used
List reduced from 44 to 1 due to restriction
Function was called by...
ncalls tottime cumtime
:27(function_b) - 1000 0.011 22.251 :12( )
profile.dat% callees function_b
Random listing order was used
List reduced from 44 to 1 due to restriction
Function called...
ncalls tottime cumtime
:27(function_b)-
1000 0.005 0.005 built-in method bisectJeft
1000 0.001 0.001 built-in method len
1000 1 5.297 22.234 built-in method sorted
profile.dat% quit
輸入help可以獲取命令列表，help后面跟隨命令名可以獲取該命令的更多信息。比如, help stats將列出可以賦予stats命令的參數(shù)。還有其他一些可用的工具，可以提供profile數(shù)據(jù)的圖形化展示形式，比如 RunSnakeRun (), 該工具需要依賴于wxPython GUI庫(kù)。
使用timeit與cProfile模塊，我們可以識(shí)別出我們自己代碼中哪些區(qū)域會(huì)耗費(fèi)超過預(yù)期的時(shí)間；使用cProfile模塊，還可以準(zhǔn)確算岀時(shí)間消耗在哪里。
以上內(nèi)容部分摘自視頻課程 05后端編程Python-19調(diào)試、測(cè)試和性能調(diào)優(yōu)(下) ，更多實(shí)操示例請(qǐng)參照視頻講解。跟著張員外講編程，學(xué)習(xí)更輕松，不花錢還能學(xué)習(xí)真本領(lǐng)。
一、使用遞歸的背景
先來看一個(gè)??接口結(jié)構(gòu)：
這個(gè)孩子，他是一個(gè)列表，下面有6個(gè)元素
展開children下第一個(gè)元素[0]看看：
發(fā)現(xiàn)[0]除了包含一些字段信息，還包含了 children 這個(gè)字段（喜當(dāng)?shù)?，同時(shí)這個(gè)children下包含了2個(gè)元素：
展開他的第一個(gè)元素，不出所料，也含有children字段（人均有娃）
可以理解為children是個(gè)對(duì)象，他包含了一些屬性，特別的是其中有一個(gè)屬性與父級(jí)children是一模一樣的，他包含父級(jí)children所有的屬性。
比如每個(gè)children都包含了一個(gè)name字段，我們要拿到所有children里name字段的值，這時(shí)候就要用到遞歸啦～
二、find_children.py
拆分理解：
1.首先import requests庫(kù)，用它請(qǐng)求并獲取接口返回的數(shù)據(jù)
2.若children以上還有很多層級(jí)，可以縮小數(shù)據(jù)范圍，定位到children的上一層級(jí)
3.來看看定義的函數(shù)
我們的函數(shù)調(diào)用：find_children(node_f, 'children')
其中，node_f：json字段
??? children：遞歸對(duì)象
?以下這段是實(shí)現(xiàn)遞歸的核心：
?? if items['children']:
?items['children']不為None，表示該元素下的children字段還有子類數(shù)據(jù)值，此時(shí)滿足if條件，可理解為 if 1。
?items['children']為None，表示該元素下children值為None，沒有后續(xù)可遞歸值，此時(shí)不滿足if條件，可理解為 if 0，不會(huì)再執(zhí)行if下的語句（不會(huì)再遞歸）。
至此，每一層級(jí)中children的name以及下一層級(jí)children的name就都取出來了
希望到這里能幫助大家理解遞歸的思路，以后根據(jù)這個(gè)模板直接套用就行
（晚安啦～）
源碼參考：
重慶分公司
重慶分公司
