Python_遞回函式

楔子

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

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

你肯定是要這么寫的，但是，現在我們已經學了函式了，什么東西都要放到函式里去呼叫、執行，于是你肯定會說，我就這么寫：

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

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

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

先不管函式最后的報錯，除了報錯之外，我們能看的出來，這一段代碼和上面的代碼執行效果是一樣的，

初識遞回

遞回的定義——在一個函式里再呼叫這個函式本身

現在我們已經大概知道剛剛講的story函式做了什么，就是在一個函式里再呼叫這個函式本身，這種魔性的使用函式的方式就叫做遞回，

剛剛我們就已經寫了一個最簡單的遞回函式，

遞回的最大深度——997

正如你們剛剛看到的，遞回函式如果不受到外力的阻止會一直執行下去，但是我們之前已經說過關于函式呼叫的問題，每一次函式呼叫都會產生一個屬于它自己的名稱空間，如果一直呼叫下去，就會造成名稱空間占用太多記憶體的問題，于是python為了杜絕此類現象，強制的將遞回層數控制在了997(只要997！你買不了吃虧，買不了上當...).

拿什么來證明這個“997理論”呢？這里我們可以做一個實驗：

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

由此我們可以看出，未報錯之前能看到的最大數字就是997.當然了，997是python為了我們程式的記憶體優化所設定的一個默認值，我們當然還可以通過一些手段去修改它：

import sys
print(sys.setrecursionlimit(100000))

我們可以通過這種方式來修改遞回的最大深度，剛剛我們將python允許的遞回深度設定為了10w，至于實際可以達到的深度就取決于計算機的性能了，不過我們還是不推薦修改這個默認的遞回深度，因為如果用997層遞回都沒有解決的問題要么是不適合使用遞回來解決要么是你代碼寫的太爛了～～～

看到這里，你可能會覺得遞回也并不是多么好的東西，不如while True好用呢！然而，江湖上流傳這這樣一句話叫做：人理解回圈，神理解遞回，所以你可別小看了遞回函式，很多人被攔在大神的門檻外這么多年，就是因為沒能領悟遞回的真諦，而且之后我們學習的很多演算法都會和遞回有關系，來吧，只有學會了才有資本嫌棄！

再談遞回

這里我們又要舉個例子來說明遞回能做的事情，

例一：

現在你們問我，alex老師多大了？我說我不告訴你，但alex比 egon 大兩歲，

你想知道alex多大，你是不是還得去問egon？egon說，我也不告訴你，但我比武sir大兩歲，

你又問武sir，武sir也不告訴你，他說他比金鑫大兩歲，

那你問金鑫，金鑫告訴你，他40了，，，

這個時候你是不是就知道了？alex多大？

你為什么能知道的？

首先，你是不是問alex的年齡，結果又找到egon、武sir、金鑫，你挨個兒問過去，一直到拿到一個確切的答案，然后順著這條線再找回來，才得到最終alex的年齡，這個程序已經非常接近遞回的思想，我們就來具體的我分析一下，這幾個人之間的規律，

age(4) = age(3) + 2 
age(3) = age(2) + 2
age(2) = age(1) + 2
age(1) = 40

那這樣的情況下，我們的函式應該怎么寫呢？

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

print(age(4))

遞回函式與三級選單

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

def threeLM(dic):
    while True:
        for k in dic:print(k)
        key = input('input>>').strip()
        if key == 'b' or key == 'q':return key
        elif key in dic.keys() and dic[key]:
            ret = threeLM(dic[key])
            if ret == 'q': return 'q'

threeLM(menu)

還記得之前寫過的三級選單作業么？現在咱們用遞回來寫一下～

l = [menu]
while l:
    for key in l[-1]:print(key)
    k = input('input>>').strip()   # 北京
    if k in l[-1].keys() and l[-1][k]:l.append(l[-1][k])
    elif k == 'b':l.pop()
    elif k == 'q':break

遞回函式與二分查找演算法

http://www.cnblogs.com/Eva-J/articles/7197403.html

標籤：Python

上一篇：Python_內置函式和匿名函式

下一篇：Python_常用模塊