當(dāng)我們碰到諸如需要求階乘或斐波那契數(shù)列的問題時(shí)，使用普通的循環(huán)往往比較麻煩，但如果我們使用遞歸時(shí)，會(huì)簡單許多，起到事半功倍的效果。這篇文章主要和大家分享一些和遞歸有關(guān)的經(jīng)典案例，結(jié)合一些資料談一下個(gè)人的理解，也借此加深自己對(duì)遞歸的理解和掌握一些遞歸基礎(chǔ)的用法。

一、遞歸的簡介

1、遞歸的百度百科定義

程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。

遞歸做為一種算法在程序設(shè)計(jì)語言中廣泛應(yīng)用。 一個(gè)過程或函數(shù)在其定義或說明中有直接或
間接調(diào)用自身的一種方法，它通常把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。

遞歸的能力在于用有限的語句來定義對(duì)象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進(jìn)
段和遞歸返回段。當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)；當(dāng)邊界條件滿足時(shí)，遞歸返回。

2、遞歸的通俗理解

遞歸就是在函數(shù)內(nèi)部調(diào)用自己的函數(shù)被稱之為遞歸。

3、幾個(gè)關(guān)于遞歸通俗的比喻

1.我們使用的詞典，本身就是遞歸，為了解釋一個(gè)詞，需要使用更多的詞。當(dāng)你查一個(gè)詞，發(fā)現(xiàn)這個(gè)詞的解釋中某個(gè)詞仍然不懂，于是你開始查這第二個(gè)詞，可惜，第二個(gè)詞里仍然有不懂的詞，于是查第三個(gè)詞，這樣查下去，直到有一個(gè)詞的解釋是你完全能看懂的，那么遞歸走到了盡頭，然后你開始后退，逐個(gè)明白之前查過的每一個(gè)詞，最終，你明白了最開始那個(gè)詞的意思。

2.一個(gè)小朋友坐在第10排，他的作業(yè)本被小組長扔到了第1排，小朋友要拿回他的作業(yè)本，可以怎么辦？他可以拍拍第9排小朋友，說：“幫我拿第1排的本子”，而第9排的小朋友可以拍拍第8排小朋友，說：“幫我拿第1排的本子”...如此下去，消息終于傳到了第1排小朋友那里，于是他把本子遞給第2排，第2排又遞給第3排...終于，本子到手啦！這就是遞歸，拍拍小朋友的背可以類比函數(shù)調(diào)用，而小朋友們都記得要傳消息、送本子，是因?yàn)樗麄冇杏洃浟Γ@可以類比棧。

3.一個(gè)洋蔥是一個(gè)帶著一層洋蔥皮的洋蔥。

4、最簡單的遞歸的實(shí)例

# 將 10不斷除以2，直至商為0，輸出這個(gè)過程中每次得到的商的值。
def recursion(n):
    v = n//2 # 地板除，保留整數(shù)
    print(v) # 每次求商，輸出商的值
    if v==0:
        ''' 當(dāng)商為0時(shí)，停止，返回Done'''
        return 'Done'
    v = recursion(v) # 遞歸調(diào)用，函數(shù)內(nèi)自己調(diào)用自己
recursion(10) # 函數(shù)調(diào)用

輸出結(jié)果：

5
2
1
0

5、遞歸的特點(diǎn)

通過以上的介紹，我們大致可以總結(jié)出遞歸的以下幾個(gè)特點(diǎn)：

1、必須有一個(gè)明確的結(jié)束條件
2、每次進(jìn)入更深一層遞歸時(shí)，問題規(guī)模(計(jì)算量)相比上次遞歸都應(yīng)有所減少
3、遞歸效率不高，遞歸層次過多會(huì)導(dǎo)致棧溢出（在計(jì)算機(jī)中，函數(shù)調(diào)用是通過棧（stack）這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的，每當(dāng)進(jìn)入一個(gè)函數(shù)調(diào)用，棧就會(huì)加一層棧幀，每當(dāng)函數(shù)返回，棧就會(huì)減一層棧幀。由于棧的大小不是無限的，所以，遞歸調(diào)用的次數(shù)過多，會(huì)導(dǎo)致棧溢出）

關(guān)于遞歸還有兩個(gè)名詞，可以概括遞歸實(shí)現(xiàn)的過程

遞推：像上邊遞歸實(shí)現(xiàn)所拆解，遞歸每一次都是基于上一次進(jìn)行下一次的執(zhí)行，這叫遞推

回溯：則是在遇到終止條件，則從最后往回返一級(jí)一級(jí)的把值返回來，這叫回溯

二、遞歸經(jīng)典案例

1、遞歸求階乘

實(shí)例如下：

'''
學(xué)習(xí)中遇到問題沒人解答？小編創(chuàng)建了一個(gè)Python學(xué)習(xí)交流群：711312441
尋找有志同道合的小伙伴，互幫互助,群里還有不錯(cuò)的視頻學(xué)習(xí)教程和PDF電子書！
'''
# 1！+2！+3！+4！+5！+...+n!
def factorial(n):
    ''' n表示要求的數(shù)的階乘 '''
    if n==1:
        return n # 階乘為1的時(shí)候，結(jié)果為1,返回結(jié)果并退出
    n = n*factorial(n-1) # n! = n*(n-1)!
    return n  # 返回結(jié)果并退出
res = factorial(5) #調(diào)用函數(shù)，并將返回的結(jié)果賦給res
print(res) # 打印結(jié)果

2、遞歸推斐波那契數(shù)列

實(shí)例如下：

# 1，1，2，3，5，8，13，21，34，55，試判斷數(shù)列第十五個(gè)數(shù)是哪個(gè)？
def fabonacci(n):
    ''' n為斐波那契數(shù)列 '''
    if n <= 2:
        ''' 數(shù)列前兩個(gè)數(shù)都是1 '''
        v = 1
        return v # 返回結(jié)果，并結(jié)束函數(shù)
    v = fabonacci(n-1)+fabonacci(n-2) # 由數(shù)據(jù)的規(guī)律可知，第三個(gè)數(shù)的結(jié)果都是前兩個(gè)數(shù)之和，所以進(jìn)行遞歸疊加
    return v  # 返回結(jié)果，并結(jié)束函數(shù)
print(fabonacci(15)) # 610    調(diào)用函數(shù)并打印結(jié)果

3、二分法找有序列表指定值

實(shí)例如下：

data = [1,3,6,13,56,123,345,1024,3223,6688]
def dichotomy(min,max,d,n):
    '''
    min表示有序列表頭部索引
    max表示有序列表尾部索引
    d表示有序列表
    n表示需要尋找的元素
    '''
    mid = (min+max)//2
    if mid==0:
        return 'None'
    elif d[mid]n:
        print('向左側(cè)找！')
        return dichotomy(min,mid,d,n)
    else:
        print('找到了%s'%d[mid])
        return 
res = dichotomy(0,len(data),data,222)
print(res)

鏈接：https://www.cnblogs.com/python1111/p/16669878.html