python函數遞歸和生成器

一、什麼是遞歸

如果函數包含了對其自身的調用，該函數就是遞歸的。遞歸做為一種演算法在程式設計語言中廣泛應用，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程式就可描述出解題過程所需要的多次重覆計算，大大地減少了程式的代碼量。例如，要計算1-9的9位數字的乘積，直觀的演算法是1*2*3*4*5*6*7*8*9，如果要計算1-10000的乘積，直觀的演算法就難於實現出，而遞歸就可以很簡單的實現。請看示例：

1 def fact(n):#計算給定數字到一的乘積
2     if n<=1:
3         return 1
4     else:
5         return n * fact(n-1)  
6 print (fact(7))

結果為：5040

下麵我們用示例來看看遞歸的執行過程：

1 def calc(n):
2     print(n)
3     if n/2 > 1:
4         res = calc(n/2)
5     return n
6 calc(8)

結果為：

1 8
2 4.0
3 2.0

再看這一個示例：

1 def calc(n):
2     print(n)
3     if n/2 > 1:
4         res = calc(n/2)
5         print('res:',res)
6     print("N:",n)
7     return n
8 calc(8)

結果為：

1 8
2 4.0
3 2.0
4 N: 2.0
5 res: 2.0
6 N: 4.0
7 res: 4.0
8 N: 8

二、生成器

生成器是一個帶 yield 語句的函數。一個函數或者子 程式只返回一次，但一個生成器能暫停執行並返回一個中間的結果，返 回一個值給調用者並暫停執行。當生成器的 next()方法被調用的時候，它會準確地從離開地方繼續

下麵看示例：

 1 def func():
 2     print('11111111')
 3     yield [1]
 4     print(2222222222)
 5     yield 2
 6     print(3333333333)
 7     yield 3
 8 
 9 ret=func()
10 r1=ret.__next__()
11 print(r1)
12 r2=ret.__next__()
13 print(r2)
14 r3=ret.__next__()
15 print(r3)

結果為：

1 11111111
2 [1]
3 2222222222
4 2
5 3333333333
6 3

由於 python 的 for 迴圈有 next()調用和對 StopIteration 的處理， 使用一個 for 迴圈而不是手 動迭代穿過一個生成器（或者那種事物的迭代器）總是要簡潔漂亮得多。例：

 1 def func():
 2     print('11111111')
 3     yield [1]
 4     print(2222222222)
 5     yield 2
 6     print(3333333333)
 7     yield 3
 8 ret=func()
 9 for i in ret:
10     print(i)

結果同前面相同。

這些簡單的例子應該讓你有點明白生成器是如何工作的。除了 next()來獲得下個生成的值，用戶 可以將值回送給生成器[send()]，在生成器中拋出異常，以及要求生成器退出[close()]

下麵是一個展示了這些特性的，簡單的例子。

1 def counter(start_at=0):
2 　　count = start_at
3 　　while True:
4 　　　　val = (yield count) if val is not None:
5 　　　　count = val
6 　　else:
7 　　　　count += 1

生成器帶有一個初始化的值，對每次對生成器[next()]調用以 1 累加計數。用戶已可以選擇重 置這個值，如果他們非常想要用新的值來調用 send()不是調用 next()。這個生成器是永遠運行的，所以如果你想要終結它，調用 close()方法。如果我們交互的運行這段代碼，會得到如下輸出：

 1 >>> count = counter(5)
 2 >>> count.next()
 3 5
 4 >>> count.next()
 5 6
 6 >>> count.send(9)
 7 9
 8 >>> count.next()
 9 10
10 >>> count.close()
11 >>> count.next()
12 Traceback (most recent call last):
13 File "<stdin>", line 1, in <module>
14 StopIteration