成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

Python | 遞歸

qieangel2013 / 3095人閱讀

摘要：那假如我們用遞歸來描述這種情況呢定義基本情況其它情形所以在上述求和中的定義又用到了自己本身的定義，這就構(gòu)成了遞歸。

說起遞歸，我覺得其實大部分人應(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ī)科學(xué)中，我們給出一個比較傳統(tǒng)的定義是：
它們有兩個特性。

一個基本特例，也稱作平凡（一般）情況，它是遞歸終止的情形

一個已定義好的規(guī)則來使其它非基本的情形轉(zhuǎn)化為基本情形

可能這個上面的定義比較枯燥，那么我們用一個經(jīng)典的例子來說明一下。

Fibonacci sequence

Fib(0) = 0, 是一個基本情況
Fib(o) = 1, 是第二個基本情況
所以 Fibonacci sequence 總共有兩個基本情形
對于其它情形，我們定義 Fib(n) = Fib(n-1) + Fib(n-2)

到這里，估計讀者已經(jīng)對遞歸有一個大概的印象了，那么在Python中我們怎么用遞歸來實現(xiàn)某些特定的功能呢？

我首先用一些簡單的例子來進(jìn)行說明。

例1.

假如你要求序列數(shù)列 1, 2, 3, 4, ..., n 的和。比如對于n=4， 其和是10。那假如我們用遞歸來描述這種情況呢？
定義:

基本情況：S(1) = 1

其它情形: S(n) = S(n-1) + n
所以在上述求和中S(n)的定義又用到了自己本身的定義，這就構(gòu)成了遞歸。

我們用Python來實現(xiàn)以下上面的思路。

def Sum(n):
    if n==1:
    #對應(yīng)基本情形
        return 1
    return Sum(n-1) + n#對應(yīng)遞歸情形

>>> Sum(4)
10
>>> Sum(10)
55
>>> Sum(100)
5050

代碼如上，可以看到，問題如果用遞歸來解決的話，可以與現(xiàn)實很好的結(jié)合，因為現(xiàn)實中有很多問題也是遞歸定義的。
此外，使用遞歸編程也比較簡單。

例2.
經(jīng)典的求階乘

定義 F(n) 為階乘函數(shù)。

基本情形: F(0) = 1, F(1) = 1

其它情形: F(n) = F(n-1) * n

實現(xiàn):

def F(n):
    if n==0 or n==1:
    #對應(yīng)基本情形
        return 1
    return F(n-1)*n#對應(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)

實現(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
>>>

除此以外，接下來的幾道題也可以用遞歸求解，雖然可能在有些問題上，遞歸并不是最合適的工具，可以使用迭代得到比遞歸更為高效的算法。

例4.

計算s=a+aa+aaa+aaaa+aa...a，其中 a是一個數(shù)字。
其中，a 以及 n 由用戶輸入，但是我們在這里就直接給定了。

定義：
函數(shù) SSS(a, n) 的值為上述所求值

基本情形：

SSS(a, 1) = a

其它情形:
SSS(a, n) = SSS(a, n-1) + a...a(共n項)

def SSS(a, n):

    #這里我說明一下，直接用input函數(shù)得到的就是字符串，除非你已經(jīng)做了轉(zhuǎn)換
    #所以,我們設(shè)定a、n都是字符串
    n = int(n)#轉(zhuǎn)換
    if n == 1:
        return int(a)
    return SSS(a, n-1) + int(a * n)#請思考這里a*n

>>> SSS("2", "5")
24690
>>> SSS("2", "1")
2
>>> SSS("2", "2")
24
>>>
例5.

在一個排列中，如果一對數(shù)的前后位置與大小順序相反，即前面的數(shù)大于后面的數(shù)，那么它們就稱為一個逆序。一個排列中逆序的總數(shù)就稱為這個排列的逆序數(shù)。比如排列[1,4,3,2]中，4在3前面，但4>3，則4和3逆序，同理，4和2逆序，3和2逆序，共有3對逆序，因此這組排列的逆序數(shù)為3?，F(xiàn)在請你設(shè)計一個程序，判斷用戶輸入的數(shù)組的逆序數(shù)。

定義：
OP(seq, n)為序列seq中前n項的逆序數(shù)

基本情形:
OP(seq[1...n], 1) = 0，對于只有一個元素的集合，逆序數(shù)必然只有0

其它情形:
OP(seq[1...n], n) = OP(seq[1...n, n-1] + F(n)，其中，F(xiàn)(n)是n關(guān)于seq[1...n-1]的逆序數(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.

輸入某年某月某日，判斷這一天是這一年的第幾天？

假如我們要用遞歸實現(xiàn)這樣的程序，該怎么考慮呢？

首先，我們得定義出我們的遞歸函數(shù)，它有三個變量，年，月，日。

定義:WhichDay(year, month, day)

基本情況: WhichDay(year, month, day) 當(dāng)month = 1時，可以看出，此時該函數(shù)的值為 day

其它情形:
WhichDay(year, month, day) = WhichDay(year, month-1, F(month-1))+day

請注意,我在遞歸式子中使用的F(month-1), 這個代表(month-1)這一月的總天數(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請讀者思考
        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
>>>

雖然上面的問題并不是很適合使用遞歸來實現(xiàn)，但是我主要是想跟大家分享一個遞歸解決問題中的思路，以及遞歸是一個很強(qiáng)大的工具，但是同時會產(chǎn)生很嚴(yán)重的效率問題。關(guān)于這一點，可以查看遞歸優(yōu)化，可以很大程度上改善遞歸的效率。

希望讀者看完這篇教程，可以有所收獲，謝謝。

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/44235.html

相關(guān)文章

  • 處理python遞歸函數(shù)及遞歸算法頻次受限制難題

    　　本文關(guān)鍵闡述了處理python遞歸函數(shù)及遞歸算法頻次受限制難題，具有非常好的實用價值，希望能幫助到大家。如有誤或者未考慮到真正的地區(qū)，望鼎力相助　　遞歸函數(shù)及遞歸算法頻次受限制　　一個函數(shù)在外部啟用自身，那么這樣的函數(shù)是遞歸函數(shù)。遞歸算法要反復(fù)應(yīng)用自身，每遞歸算法一回，越近最后的值。如果一個難題需要由很多類似小問題處理，可以選擇應(yīng)用遞歸函數(shù)。伴隨著遞歸算法的深層次，難題經(jīng)營規(guī)模對比之前都應(yīng)該所...

    89542767 評論0 收藏0

  • Python開啟尾遞歸優(yōu)化!

    摘要：尾遞歸優(yōu)化一般遞歸與尾遞歸一般遞歸執(zhí)行可以看到一般遞歸每一級遞歸都產(chǎn)生了新的局部變量必須創(chuàng)建新的調(diào)用棧隨著遞歸深度的增加創(chuàng)建的棧越來越多造成爆棧尾遞歸尾遞歸基于函數(shù)的尾調(diào)用每一級調(diào)用直接返回遞歸函數(shù)更新調(diào)用棧沒有新局部變量的產(chǎn)生類似迭代的 Python尾遞歸優(yōu)化 一般遞歸與尾遞歸 一般遞歸: def normal_recursion(n): if n == 1: ...

    junnplus 評論0 收藏0

  • 小李飛刀：python你慢點飛，我的腦子還在后面追

    摘要：默認(rèn)參數(shù)設(shè)置默認(rèn)參數(shù)時，有幾點要注意一是必選參數(shù)在前，默認(rèn)參數(shù)在后，否則的解釋器會報錯二是如何設(shè)置默認(rèn)參數(shù)。注意此處，獲得的其實是的拷貝，函數(shù)內(nèi)對的改變不會影響到。使用遞歸函數(shù)需要注意防止棧溢出。 總是在最前面的叨逼叨 最近總是在想成長這兩個很常常被提起的事情，這對于一個已經(jīng)25歲的半中年而言，已經(jīng)是一個不太能高頻提起的詞。但是，最近一些事情吧，總讓我覺得我的生長期似乎比正常人來的晚了...

    kevin 評論0 收藏0

  • Python筆記

    摘要：針對尾遞歸優(yōu)化的語言可以通過尾遞歸防止棧溢出。尾遞歸事實上和循環(huán)是等價的，沒有循環(huán)語句的編程語言只能通過尾遞歸實現(xiàn)循環(huán)。標(biāo)準(zhǔn)的解釋器沒有針對尾遞歸做優(yōu)化，任何遞歸函數(shù)都存在棧溢出的問題。 python 頭部： #!/usr/bin/env python # -*- coding: utf-8 -*- 函數(shù)的參數(shù) Python的函數(shù)具有非常靈活的參數(shù)形態(tài)，既可以實現(xiàn)簡單的調(diào)用，又可以傳入...

    yuxue 評論0 收藏0

  • 【數(shù)據(jù)科學(xué)系統(tǒng)學(xué)習(xí)】Python # 編程基礎(chǔ)[一]

    摘要：在定義函數(shù)時給定的名稱稱作形參，在調(diào)用函數(shù)時你所提供給函數(shù)的值稱作實參。調(diào)用函數(shù)要調(diào)用一個函數(shù)，需要知道函數(shù)的名稱和參數(shù)。默認(rèn)參數(shù)值可以有效幫助解決這一情況。是默認(rèn)參數(shù)定義默認(rèn)參數(shù)要牢記一點默認(rèn)參數(shù)必須指向不變對象。 關(guān)于數(shù)據(jù)科學(xué)在做什么，我們已經(jīng)在前兩篇文章中進(jìn)行了總結(jié)，即專題概述和描述性統(tǒng)計分析。要進(jìn)行數(shù)據(jù)科學(xué)的探索，需要一個好工具，就是Python。從本篇開始，將總結(jié)學(xué)習(xí)Pyth...

    luckyyulin 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<