復習
<pre>
sum = 0
i = 0
while i <= 100:
sum = sum + i
i = i + 1
print(sum)
</pre>
- for循環(huán)
<pre>
sum = 0
for i in range(101):
sum = sum + 1
print(sum)
</pre>
函數(shù)
函數(shù)是組織好的结笨，可重復使用的款慨，用來實現(xiàn)單一挣菲，或相關聯(lián)功能的代碼段羔味。
函數(shù)能提高應用的模塊性，和代碼的重復利用率。你已經(jīng)知道Python提供了許多內建函數(shù)，比如print()。但你也可以自己創(chuàng)建函數(shù)弟翘，這被叫做用戶自定義函數(shù)。
如何定義函數(shù)
參數(shù)
如何調用函數(shù)
如何返回函數(shù)
函數(shù)體內部的語句在執(zhí)行時骄酗，一旦執(zhí)行到return時稀余，函數(shù)就執(zhí)行完畢，并將結果返回趋翻。
例子:求和n
類比
函數(shù):廚房
參數(shù):食材
多個參數(shù)
<pre>
import math
def abs(num):
if num < 0:
return -num;
else:
return num;
</pre>
練習:
- 定義一個函數(shù),傳入兩個數(shù)字參數(shù), 返回最大值
- 定義一個函數(shù),傳入兩個數(shù)字參數(shù), 返回最小值
- 定義一個函數(shù),傳入兩個數(shù)字參數(shù)a,b. 返回a的b次方
- 定義一個函數(shù),傳入一個數(shù)字參數(shù)a, 作為圓的半徑,返回圓的面積
- 定義一個函數(shù),傳入三個數(shù)字參數(shù), 返回最小值
- 定義一個函數(shù),傳入數(shù)字數(shù)組, 返回最小值
調用其他函數(shù)
遞歸函數(shù)
在函數(shù)內部睛琳，可以調用其他函數(shù)。如果一個函數(shù)在內部調用自身本身，這個函數(shù)就是遞歸函數(shù)师骗。
舉個例子历等，我們來計算階乘n! = 1 x 2 x 3 x ... x n，用函數(shù)fact(n)表示辟癌，可以看出：
fact(n) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = fact(n-1) x n
所以寒屯，fact(n)可以表示為n x fact(n-1)，只有n=1時需要特殊處理黍少。
于是寡夹，fact(n)用遞歸的方式寫出來就是：
<pre>
def fact(n):
if n==1:
return 1
return n * fact(n - 1)
</pre>
上面就是一個遞歸函數(shù)〕е茫可以試試：
如果我們計算fact(5)要出，可以根據(jù)函數(shù)定義看到計算過程如下：
===> fact(5)
===> 5 * fact(4)
===> 5 * (4 * fact(3))
===> 5 * (4 * (3 * fact(2)))
===> 5 * (4 * (3 * (2 * fact(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120
遞歸函數(shù)的優(yōu)點是定義簡單，邏輯清晰农渊。理論上，所有的遞歸函數(shù)都可以寫成循環(huán)的方式或颊，但循環(huán)的邏輯不如遞歸清晰砸紊。
使用遞歸函數(shù)需要注意防止棧溢出。在計算機中囱挑，函數(shù)調用是通過棧（stack）這種數(shù)據(jù)結構實現(xiàn)的醉顽，每當進入一個函數(shù)調用，棧就會加一層棧幀平挑，每當函數(shù)返回游添，棧就會減一層棧幀。由于棧的大小不是無限的通熄，所以唆涝，遞歸調用的次數(shù)過多，會導致棧溢出唇辨±群ǎ可以試試fact(1000)：
遞歸函數(shù)
閱讀: 310046
在函數(shù)內部，可以調用其他函數(shù)赏枚。如果一個函數(shù)在內部調用自身本身亡驰，這個函數(shù)就是遞歸函數(shù)。
舉個例子饿幅，我們來計算階乘n! = 1 x 2 x 3 x ... x n
凡辱，用函數(shù)fact(n)
表示，可以看出：
fact(n) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = fact(n-1) x n
所以栗恩，fact(n)
可以表示為n x fact(n-1)
透乾，只有n=1時需要特殊處理。
于是，fact(n)
用遞歸的方式寫出來就是：
def fact(n): if n==1: return 1 return n * fact(n - 1)
上面就是一個遞歸函數(shù)续徽◎韭可以試試：
fact(1)1>>> fact(5)120>>> fact(100)93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
如果我們計算fact(5)
，可以根據(jù)函數(shù)定義看到計算過程如下：
===> fact(5)===> 5 * fact(4)===> 5 * (4 * fact(3))===> 5 * (4 * (3 * fact(2)))===> 5 * (4 * (3 * (2 * fact(1))))===> 5 * (4 * (3 * (2 * 1)))===> 5 * (4 * (3 * 2))===> 5 * (4 * 6)===> 5 * 24===> 120
遞歸函數(shù)的優(yōu)點是定義簡單钦扭，邏輯清晰纫版。理論上，所有的遞歸函數(shù)都可以寫成循環(huán)的方式客情，但循環(huán)的邏輯不如遞歸清晰其弊。
使用遞歸函數(shù)需要注意防止棧溢出。在計算機中膀斋，函數(shù)調用是通過棧（stack）這種數(shù)據(jù)結構實現(xiàn)的梭伐，每當進入一個函數(shù)調用，棧就會加一層棧幀仰担，每當函數(shù)返回糊识，棧就會減一層棧幀。由于棧的大小不是無限的摔蓝，所以赂苗，遞歸調用的次數(shù)過多，會導致棧溢出贮尉“枳蹋可以試試fact(1000)
：
fact(1000)Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 4, in fact ... File "<stdin>", line 4, in factRuntimeError: maximum recursion depth exceeded in comparison
解決遞歸調用棧溢出的方法是通過尾遞歸優(yōu)化，事實上尾遞歸和循環(huán)的效果是一樣的猜谚，所以败砂，把循環(huán)看成是一種特殊的尾遞歸函數(shù)也是可以的。
尾遞歸是指魏铅，在函數(shù)返回的時候昌犹，調用自身本身，并且览芳，return語句不能包含表達式祭隔。這樣，編譯器或者解釋器就可以把尾遞歸做優(yōu)化路操，使遞歸本身無論調用多少次疾渴，都只占用一個棧幀，不會出現(xiàn)棧溢出的情況屯仗。
上面的fact(n)
函數(shù)由于return n * fact(n - 1)
引入了乘法表達式搞坝，所以就不是尾遞歸了。要改成尾遞歸方式魁袜，需要多一點代碼桩撮，主要是要把每一步的乘積傳入到遞歸函數(shù)中：
def fact(n): return fact_iter(n, 1)def fact_iter(num, product): if num == 1: return product return fact_iter(num - 1, num * product)
可以看到敦第，return fact_iter(num - 1, num * product)
僅返回遞歸函數(shù)本身，num - 1
和num * product
在函數(shù)調用前就會被計算店量，不影響函數(shù)調用芜果。
fact(5)
對應的fact_iter(5, 1)
的調用如下：
===> fact_iter(5, 1)===> fact_iter(4, 5)===> fact_iter(3, 20)===> fact_iter(2, 60)===> fact_iter(1, 120)===> 120
尾遞歸調用時，如果做了優(yōu)化融师，棧不會增長右钾，因此，無論多少次調用也不會導致棧溢出旱爆。
遺憾的是舀射，大多數(shù)編程語言沒有針對尾遞歸做優(yōu)化，Python解釋器也沒有做優(yōu)化怀伦，所以脆烟，即使把上面的fact(n)
函數(shù)改成尾遞歸方式，也會導致棧溢出房待。
小結
使用遞歸函數(shù)的優(yōu)點是邏輯簡單清晰邢羔，缺點是過深的調用會導致棧溢出。
針對尾遞歸優(yōu)化的語言可以通過尾遞歸防止棧溢出桑孩。尾遞歸事實上和循環(huán)是等價的张抄，沒有循環(huán)語句的編程語言只能通過尾遞歸實現(xiàn)循環(huán)。
Python標準的解釋器沒有針對尾遞歸做優(yōu)化洼怔，任何遞歸函數(shù)都存在棧溢出的問題。
練習
漢諾塔的移動可以用遞歸函數(shù)非常簡單地實現(xiàn)左驾。
請編寫move(n, a, b, c)
函數(shù)镣隶，它接收參數(shù)n
，表示3個柱子A诡右、B安岂、C中第1個柱子A的盤子數(shù)量，然后打印出把所有盤子從A借助B移動到C的方法帆吻，例如：
題目：有四個數(shù)字：1域那、2、3猜煮、4次员，能組成多少個互不相同且無重復數(shù)字的三位數(shù)？各是多少王带？
程序分析：可填在百位淑蔚、十位、個位的數(shù)字都是1愕撰、2刹衫、3醋寝、4。組成所有的排列后再去 掉不滿足條件的排列带迟。
程序源代碼：
<pre>
for i in range(1,5):
for j in range(1,5):
for k in range(1,5):
if( i != k ) and (i != j) and (j != k):
print i,j,k
</pre>
題目：企業(yè)發(fā)放的獎金根據(jù)利潤提成音羞。利潤(I)低于或等于10萬元時，獎金可提10%仓犬；利潤高于10萬元嗅绰，低于20萬元時，低于10萬元的部分按10%提成婶肩，高于10萬元的部分办陷，可提成7.5%；20萬到40萬之間時律歼，高于20萬元的部分民镜，可提成5%；40萬到60萬之間時高于40萬元的部分险毁，可提成3%制圈；60萬到100萬之間時，高于60萬元的部分畔况，可提成1.5%鲸鹦，高于100萬元時，超過100萬元的部分按1%提成跷跪，從鍵盤輸入當月利潤I馋嗜，求應發(fā)放獎金總數(shù)？
程序分析：請利用數(shù)軸來分界吵瞻，定位葛菇。注意定義時需把獎金定義成長整型。
程序源代碼：
<pre>
i = int(raw_input('凈利潤:'))
arr = [1000000,600000,400000,200000,100000,0]
rat = [0.01,0.015,0.03,0.05,0.075,0.1]
r = 0
for idx in range(0,6):
if i>arr[idx]:
r+=(i-arr[idx])rat[idx]
print (i-arr[idx])rat[idx]
i=arr[idx]
print r
</pre>
題目：一個正整數(shù)橡羞，它加上100和加上268后都是一個完全平方數(shù)胖烛，請問該數(shù)是多少草雕？
程序分析：在10000以內判斷浓恶，將該數(shù)加上100后再開方紧憾，加上268后再開方，如果開方后的結果滿足如下條件签夭，即是結果齐邦。請看具體分析：
程序源代碼
<pre>
import math
for i in range(10000):
#轉化為整型值
x = int(math.sqrt(i + 100))
y = int(math.sqrt(i + 268))
if(x * x == i + 100) and (y * y == i + 268):
print i
</pre>
題目：斐波那契數(shù)列。
程序分析：斐波那契數(shù)列（Fibonacci sequence）第租，又稱黃金分割數(shù)列侄旬，指的是這樣一個數(shù)列：0、1煌妈、1儡羔、2宣羊、3、5汰蜘、8仇冯、13、21族操、34苛坚、……。
在數(shù)學上色难，費波那契數(shù)列是以遞歸的方法來定義：
<pre>
def fib(n):
a,b = 1,1
for i in range(n-1):
a,b = b,a+b
return a
輸出了第10個斐波那契數(shù)列
print fib(10)
</pre>
<pre>
使用遞歸
def fib(n):
if n==1 or n==2:
return 1
return fib(n-1)+fib(n-2)
輸出了第10個斐波那契數(shù)列
print fib(10)
</pre>
題目：輸出 9*9 乘法口訣表泼舱。
程序分析：分行與列考慮，共9行9列枷莉，i控制行娇昙，j控制列。
程序源代碼：
<pre>
for i in range(1, 10):
print
for j in range(1, i+1):
print "%d%d=%d" % (i, j, ij),
</pre>
題目：古典問題：有一對兔子笤妙，從出生后第3個月起每個月都生一對兔子冒掌，小兔子長到第三個月后每個月又生一對兔子，假如兔子都不死蹲盘，問每個月的兔子總數(shù)為多少股毫？
程序分析：兔子的規(guī)律為數(shù)列1,1,2,3,5,8,13,21....
程序源代碼：
<pre>
f1 = 1
f2 = 1
for i in range(1,22):
print '%12ld %12ld' % (f1,f2),
if (i % 3) == 0:
print ''
f1 = f1 + f2
f2 = f1 + f2
</pre>
題目：判斷101-200之間有多少個素數(shù)，并輸出所有素數(shù)召衔。
程序分析：判斷素數(shù)的方法：用一個數(shù)分別去除2到sqrt(這個數(shù))铃诬，如果能被整除，則表明此數(shù)不是素數(shù)苍凛，反之是素數(shù)趣席。
<pre>
!/usr/bin/python
-- coding: UTF-8 --
h = 0
leap = 1
from math import sqrt
from sys import stdout
for m in range(101,201):
k = int(sqrt(m + 1))
for i in range(2,k + 1):
if m % i == 0:
leap = 0
break
if leap == 1:
print '%-4d' % m
h += 1
if h % 10 == 0:
print ''
leap = 1
print 'The total is %d' % h
</pre>
