日韩人妻无码一区二区三区99,亚洲国模精品一区二区,中文字幕有码日韩精品

函數(shù)之遞歸

遞歸

前戲

在講今天的內(nèi)容之前，我們先來講一個(gè)故事，講的什么呢？從前有座山，山里有座廟，廟里有個(gè)老和尚講故事，講的什么呢？從前有座山，山里有座廟，廟里有個(gè)老和尚講故事，講的什么呢？從前有座山，山里有座廟，廟里有個(gè)老和尚講故事，講的什么呢？從前有座山，山里有座廟，廟里有個(gè)老和尚講故事，講的什么呢......這個(gè)故事你們不喊停我能講一天！我們說，生活中的例子也能被寫成程序，剛剛這個(gè)故事，讓你們寫，你們怎么寫呀？

while True:
    story = "
    從前有個(gè)山，山里有座廟，廟里老和尚講故事，
    講的什么呢？   
    "
    print(story)

你肯定是要這么寫的，但是，現(xiàn)在我們已經(jīng)學(xué)了函數(shù)了，什么東西都要放到函數(shù)里去調(diào)用、執(zhí)行。于是你肯定會說，我就這么寫：

def story():
    s = """
    從前有個(gè)山，山里有座廟，廟里老和尚講故事，
    講的什么呢？
    """
    print(s)
    
while True:
    story()

但是大家來看看，我是怎么寫的！

def story():
    s = """
    從前有個(gè)山，山里有座廟，廟里老和尚講故事，
    講的什么呢？
    """
    print(s)
    story()
    
story()

先不管函數(shù)最后的報(bào)錯(cuò)，除了報(bào)錯(cuò)之外，我們能看的出來，這一段代碼和上面的代碼執(zhí)行效果是一樣的。

遞歸的概念：

在一個(gè)函數(shù)內(nèi)部調(diào)用這個(gè)函數(shù)自身我們就可以將其稱為遞歸函數(shù)

遞歸其實(shí)是倆個(gè)不同的過程：

遞：是整個(gè)函數(shù)執(zhí)行的過程是從上到下的順序

歸：是將執(zhí)行的結(jié)果返回來是從下到上的順序

def  story():
    info = '''
    從前有個(gè)山，山里有座廟，廟里老和尚講故事，
    講的什么呢？   
    '''
    print(info)
    story()

story()

上面一個(gè)簡單的示例詮釋了遞歸函數(shù)概念：在story這個(gè)函數(shù)中調(diào)用了story函數(shù)自身那么我們就可以稱story這個(gè)函數(shù)為遞歸函數(shù)。

我們現(xiàn)在知道了什么是遞歸函數(shù)，但是在執(zhí)行這個(gè)函數(shù)的時(shí)候會發(fā)現(xiàn)執(zhí)行以后會報(bào)錯(cuò)：RecursionError: maximum recursion depth exceeded while calling a Python object

這是為什么呢？是不是我們的遞歸函數(shù)寫錯(cuò)了呢？不然為什么會報(bào)錯(cuò)呢？這就涉及到了一個(gè)新的知識點(diǎn)---遞歸函數(shù)的最大深度

遞歸的最大深度深度

什么是遞歸函數(shù)的最大深度呢？

　　我們執(zhí)行遞歸函數(shù)如果不受到外力的阻止會一直執(zhí)行下去。但是我們之前已經(jīng)說過關(guān)于函數(shù)調(diào)用的問題，每一次函數(shù)調(diào)用都會產(chǎn)生一個(gè)屬于它自己的名稱空間，如果一直調(diào)用下去，就會造成名稱空間占用太多內(nèi)存的問題，于是python為了杜絕此類現(xiàn)象，強(qiáng)制的將遞歸層數(shù)控制在了997

　　怎么證明遞歸的最大深度是997呢？

def foo(n):
    print(n)
    n += 1
    foo(n)
foo(1)

測試遞歸最大深度

通過執(zhí)行上述代碼知道在程序沒有報(bào)錯(cuò)之前執(zhí)行的最大值就是997，當(dāng)然997是python為了我們程序的內(nèi)存優(yōu)化所設(shè)定的一個(gè)默認(rèn)值，我們當(dāng)然還可以通過一些手段去修改它：

import sys
print(sys.setrecursionlimit(100000))

修改遞歸最大深度值

我們可以通過這種方式來修改遞歸的最大深度，剛剛我們將python允許的遞歸深度設(shè)置為了10w，至于實(shí)際可以達(dá)到的深度就取決于計(jì)算機(jī)的性能了。不過我們還是不推薦修改這個(gè)默認(rèn)的遞歸深度，因?yàn)槿绻?97層遞歸都沒有解決的問題要么是不適合使用遞歸來解決要么是你代碼寫的太爛了～～～

看到這里，你可能會覺得遞歸也并不是多么好的東西，不如while True好用呢！然而，江湖上流傳這這樣一句話叫做：人理解循環(huán)，神理解遞歸。所以你可別小看了遞歸函數(shù)，很多人被攔在大神的門檻外這么多年，就是因?yàn)闆]能領(lǐng)悟遞歸的真諦。而且之后我們學(xué)習(xí)的很多算法都會和遞歸有關(guān)系。來吧，只有學(xué)會了才有資本嫌棄！

遞歸的深入了解

通過對初始遞歸這個(gè)小結(jié)的了解我們對遞歸也有了一定的了解當(dāng)然了只是初步的了解，那么就讓我們再來深入的了解一下吧畢竟這樣才可以掌握的更扎實(shí)嘛

現(xiàn)在你們問我，alex老師多大了？我說我不告訴你，但alex比 egon 大兩歲。
你想知道alex多大，你是不是還得去問egon？egon說，我也不告訴你，但我比武sir大兩歲。
你又問武sir，武sir也不告訴你，他說他比金鑫大兩歲。
那你問金鑫，金鑫告訴你，他40了。。。
這個(gè)時(shí)候你是不是就知道了？alex多大？
1  金鑫　  40
2  武sir    42
3  egon　 44
4  alex　　46
你為什么能知道的？
首先，你是不是問alex的年齡，結(jié)果又找到egon、武sir、金鑫，你挨個(gè)兒問過去，一直到拿到一個(gè)確切的答案，然后順著這條線再找回來，才得到最終alex的年齡。這個(gè)過程已經(jīng)非常接近遞歸的思想。我們就來具體的我分析一下，這幾個(gè)人之間的規(guī)律。
age(4) = age(3) + 2 
age(3) = age(2) + 2
age(2) = age(1) + 2
age(1) = 40
那這樣的情況下，我們的函數(shù)應(yīng)該怎么寫呢？

def age(n):
    if n == 1:
        return 40
    else:
        return age(n-1)+2

print('alex的年齡是:%s'%age(4))

猜年齡深入了解遞歸

怎么樣通過上面的例子相信你一定對遞歸有了一個(gè)更深刻的理解了吧那么就請牢牢的記住吧它的用處非常的大哦，不相信你會后悔的！??！

遞歸和三級菜單

數(shù)據(jù)結(jié)構(gòu)：

menu = {
    '北京':{
        '海淀':{
            '五道口':{
                'soho':{},
                '網(wǎng)易':{},
                'google':{}
            },
            '中關(guān)村':{
                '愛奇藝':{},
                '汽車之家':{},
                'youku':{},
            },
            '上地':{
                '百度':{},
            },
        },
        '昌平':{
            '沙河':{
                '老男孩':{},
                '北航':{},
            },
            '天通苑':{},
            '回龍觀':{},
        },
        '朝陽':{},
        '東城':{},
    },
    '上海':{
        '閔行':{
            "人民廣場":{
                '炸雞店':{}
            }
        },
        '閘北':{
            '火車戰(zhàn)':{
                '攜程':{}
            }
        },
        '浦東':{},
    },
    '山東':{},
}


需求：
可依次選擇進(jìn)入各子菜單
可從任意一層往回退到上一層
可從任意一層退出程序

#遞歸方式實(shí)現(xiàn)
def show_Menu(ch):
    for s in ch:
        print(s)
    print('返回/退出')
    p = input('您選擇是')
    if p == '退出':
        exit()
    elif p == '返回' and ch != menu:
        return
    else:
        if p in ch:
            show_Menu(ch[p])
        show_Menu(ch)
show_Menu(menu)

遞歸實(shí)現(xiàn)三級菜單

遞歸和二分算法

遞歸我們已經(jīng)知道是怎么回事，那么算法又是怎么回事呢？很簡單啊，你通過字面就可以解釋?。壕褪怯?jì)算的方法嘛。那么下面我們就通過示例來看一下什么是二分算法吧

如果有一個(gè)列表，讓你從這個(gè)列表中找到66的位置，你要怎么做？

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

l.index(66) 這不就解決問題了嗎

這確實(shí)可以解決問題，是因?yàn)槲覀冇玫膇ndex方法內(nèi)部提供了__next__()方法就相當(dāng)于for循環(huán)遍歷了整個(gè)列表，我們的示例數(shù)據(jù)量比較小這樣做可以但是如果有一個(gè)非常大的數(shù)據(jù)達(dá)了幾萬或者幾十萬的話這樣做會占用很大的內(nèi)存導(dǎo)致程序運(yùn)行緩慢甚至崩潰這該怎么辦呢這就用到了我們要學(xué)習(xí)的二分法

二分法概念

其實(shí)就是一種通過不斷的排除不可能的東西,來最終找到需要的東西的一種方法.所以可以理解成排除法.之所以叫二分,是因?yàn)槊看闻懦及阉械那闆r分成"可能"和"不可能"兩種,
然后拋棄所有"不可能"的情況.最正統(tǒng)的二分法中,是每次排除都可以排除掉一半的情況,這樣子的尋找效率是很高的.

 ps:二分查找算法 必須處理有序的列表

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

def find(l,aim):
    mid_index = len(l) // 2
    if l[mid_index] < aim:
        new_l = l[mid_index+1 :]
        find(new_l,aim)
    elif l[mid_index] > aim:
        new_l = l[:mid_index]
        find(new_l, aim)
    else:
        print('找到了',mid_index,l[mid_index])

find(l,66)

二分法實(shí)現(xiàn)數(shù)據(jù)查找

ps:使用二分法查找數(shù)據(jù)數(shù)據(jù)必須是有序的列表方可

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

def find(l,aim,start = 0,end = None):
    end = len(l) if end is None else end
    mid_index = (end - start)//2 + start
    if start <= end:
        if l[mid_index] < aim:
            return find(l,aim,start =mid_index+1,end=end)
        elif l[mid_index] > aim:
            return find(l, aim, start=start, end=mid_index-1)
        else:
            return mid_index
    else:
        return '找不到這個(gè)值'

進(jìn)階(終極版本)

posted on 2017-08-09 15:56 WorthWaitingFor 閱讀(306) 評論(0) 收藏舉報(bào)

刷新頁面返回頂部

Worth Waiting For