python递归求5!_Python | 递归
說(shuō)起遞歸，我覺(jué)得其實(shí)大部分人應(yīng)該是不陌生的，遞歸廣泛存在于生活中。
比如：
The woman in this image holds an object that contains a smaller image of her holding an identical object, which in turn contains a smaller image of herself holding an identical object, and so forth.[from wikipedia]
那么遞歸的定義是什么呢？
在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中，我們給出一個(gè)比較傳統(tǒng)的定義是：
它們有兩個(gè)特性。
一個(gè)基本特例，也稱作平凡(一般)情況，它是遞歸終止的情形
一個(gè)已定義好的規(guī)則來(lái)使其它非基本的情形轉(zhuǎn)化為基本情形
可能這個(gè)上面的定義比較枯燥，那么我們用一個(gè)經(jīng)典的例子來(lái)說(shuō)明一下。
Fibonacci sequence
Fib(0) = 0, 是一個(gè)基本情況
Fib(o) = 1, 是第二個(gè)基本情況
所以 Fibonacci sequence 總共有兩個(gè)基本情形
對(duì)于其它情形，我們定義 Fib(n) = Fib(n-1) + Fib(n-2)
到這里，估計(jì)讀者已經(jīng)對(duì)遞歸有一個(gè)大概的印象了，那么在Python中我們?cè)趺从眠f歸來(lái)實(shí)現(xiàn)某些特定的功能呢？
我首先用一些簡(jiǎn)單的例子來(lái)進(jìn)行說(shuō)明。
例1.
假如你要求序列數(shù)列 1, 2, 3, 4, ..., n 的和。比如對(duì)于n=4， 其和是10。那假如我們用遞歸來(lái)描述這種情況呢？
定義:
基本情況：S(1) = 1
其它情形: S(n) = S(n-1) + n
所以在上述求和中S(n)的定義又用到了自己本身的定義，這就構(gòu)成了遞歸。
我們用Python來(lái)實(shí)現(xiàn)以下上面的思路。
def Sum(n):
if n==1:
#對(duì)應(yīng)基本情形
return 1
return Sum(n-1) + n#對(duì)應(yīng)遞歸情形
>>> Sum(4)
10
>>> Sum(10)
55
>>> Sum(100)
5050
代碼如上，可以看到，問(wèn)題如果用遞歸來(lái)解決的話，可以與現(xiàn)實(shí)很好的結(jié)合，因?yàn)楝F(xiàn)實(shí)中有很多問(wèn)題也是遞歸定義的。
此外，使用遞歸編程也比較簡(jiǎn)單。
例2.
經(jīng)典的求階乘
定義 F(n) 為階乘函數(shù)。
基本情形: F(0) = 1, F(1) = 1
其它情形: F(n) = F(n-1) * n
實(shí)現(xiàn):
def F(n):
if n==0 or n==1:
#對(duì)應(yīng)基本情形
return 1
return F(n-1)*n#對(duì)應(yīng)遞歸情形
>>> F(4)
24
>>> F(10)
3628800
例3.
求 斐波那契數(shù)列
定義Fib(n) 為斐波那契數(shù)列
基本情形:
Fib(0) = 1, Fib(1) = 1
其它情形:
Fib(n) = Fib(n-1)+Fib(n-2)
實(shí)現(xiàn):
def Fib(n):
if n==0 or n==1:
return 1
return Fib(n-1)+Fib(n-2)
>>> Fib(10)
89
>>> Fib(8)
34
>>>
除此以外，接下來(lái)的幾道題也可以用遞歸求解，雖然可能在有些問(wèn)題上，遞歸并不是最合適的工具，可以使用迭代得到比遞歸更為高效的算法。
例4.
計(jì)算s=a+aa+aaa+aaaa+aa...a，其中 a是一個(gè)數(shù)字。
其中，a 以及 n 由用戶輸入，但是我們?cè)谶@里就直接給定了。
定義：
函數(shù) SSS(a, n) 的值為上述所求值
基本情形：
SSS(a, 1) = a
其它情形:
SSS(a, n) = SSS(a, n-1) + a...a(共n項(xiàng))
def SSS(a, n):
#這里我說(shuō)明一下，直接用input函數(shù)得到的就是字符串，除非你已經(jīng)做了轉(zhuǎn)換
#所以,我們?cè)O(shè)定a、n都是字符串
n = int(n)#轉(zhuǎn)換
if n == 1:
return int(a)
return SSS(a, n-1) + int(a * n)#請(qǐng)思考這里a*n
>>> SSS('2', '5')
24690
>>> SSS('2', '1')
2
>>> SSS('2', '2')
24
>>>
例5.
在一個(gè)排列中，如果一對(duì)數(shù)的前后位置與大小順序相反，即前面的數(shù)大于后面的數(shù)，那么它們就稱為一個(gè)逆序。一個(gè)排列中逆序的總數(shù)就稱為這個(gè)排列的逆序數(shù)。比如排列[1,4,3,2]中，4在3前面，但4>3，則4和3逆序，同理，4和2逆序，3和2逆序，共有3對(duì)逆序，因此這組排列的逆序數(shù)為3。現(xiàn)在請(qǐng)你設(shè)計(jì)一個(gè)程序，判斷用戶輸入的數(shù)組的逆序數(shù)。
定義：
OP(seq, n)為序列seq中前n項(xiàng)的逆序數(shù)
基本情形:
OP(seq[1...n], 1) = 0，對(duì)于只有一個(gè)元素的集合，逆序數(shù)必然只有0
其它情形:
OP(seq[1...n], n) = OP(seq[1...n, n-1] + F(n)，其中，F(n)是n關(guān)于seq[1...n-1]的逆序數(shù).
實(shí)現(xiàn):
def OP(seq, n):
if n == 1:
return 0
#不為0
Fn = 0
for i in range(0, n-1):
if seq[n-1] < seq[i]:
Fn+=1
return OP(seq, n-1)+Fn
>>> s = [5, 4, 3, 2, 1]
>>> s
[5, 4, 3, 2, 1]
>>> OP(s, len(s))
10
>>>
例6.
輸入某年某月某日，判斷這一天是這一年的第幾天？
假如我們要用遞歸實(shí)現(xiàn)這樣的程序，該怎么考慮呢？
首先，我們得定義出我們的遞歸函數(shù)，它有三個(gè)變量，年，月，日。
定義:WhichDay(year, month, day)
基本情況: WhichDay(year, month, day) 當(dāng)month = 1時(shí)，可以看出，此時(shí)該函數(shù)的值為 day
其它情形:
WhichDay(year, month, day) = WhichDay(year, month-1, F(month-1))+day
請(qǐng)注意,我在遞歸式子中使用的F(month-1), 這個(gè)代表(month-1)這一月的總天數(shù)。
實(shí)現(xiàn):
F = { 1:31, 2: 28, 3:31, 4:30, 5:31, 6:30, 7:31, 8:31, 9:30, 10: 31, 11: 30, 12: 31}
def WhichDay(year, month, day):
if month == 1:
return day
flag = 0#二月是否閏年標(biāo)志
if month == 3:
#二月特殊處理
#這里month等于3請(qǐng)讀者思考
if (year % 4 == 0 and year % 100!=0) or year % 400 == 0:
flag = 1#判斷閏年
return WhichDay(year, month-1, F[month-1]+flag)+day
>>> WhichDay(2016, 2, 1)
32
>>> WhichDay(2016, 11, 8)
313
>>> WhichDay(2016, 12, 31)
366
>>>
雖然上面的問(wèn)題并不是很適合使用遞歸來(lái)實(shí)現(xiàn)，但是我主要是想跟大家分享一個(gè)遞歸解決問(wèn)題中的思路，以及遞歸是一個(gè)很強(qiáng)大的工具，但是同時(shí)會(huì)產(chǎn)生很嚴(yán)重的效率問(wèn)題。關(guān)于這一點(diǎn)，可以查看遞歸優(yōu)化，可以很大程度上改善遞歸的效率。
希望讀者看完這篇教程，可以有所收獲，謝謝。
總結(jié)
以上是生活随笔為你收集整理的python递归求5!_Python | 递归的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 八卦岭
- 下一篇： Retroifit原理