遞歸

一個函數在執行過程中一次或多次調用其本身便是遞歸，就像是俄羅斯套娃一樣，一個娃娃里包含另一個娃娃。

遞歸其實是程式設計語言學習過程中很快就會接觸到的東西，但有關遞歸的理解可能還會有一些遺漏，下麵對此方面進行更加深入的理解

遞歸的分類

這裡根據遞歸調用的數量分為線性遞歸、二路遞歸與多重遞歸

線性遞歸

如果一個遞歸調用最多開始一個其他遞歸調用，我們稱之為線性遞歸。

例如：

def binary_search(data, target, low, high):
    """
    二分查找，對有序列表進行查找，如果找到則返回True，否則返回False 
    """

    if low > high:
        return False
    else:
        mid = (low + high) // 2
        if target == data[mid]:
            return True
        elif target < data[mid]:
            return binary_search(data, target, low, mid - 1)
        else:
            return binary_search(data, target, mid + 1, high)

雖然在代碼中有兩個binary_search，但他們是不同條件執行的，每次只能執行一次，所以是線性遞歸。

二路遞歸

如果一個遞歸調用可以開始兩個其他遞歸調用，我們稱之為二路遞歸

例如：

def binary_sum(S, start, stop):
    """
    二路遞歸計算一個序列的和，例如S[0:5],就像切片的範圍一樣

    """

    if start >= stop:
        return 0
    elif start == stop - 1:
        return S[start]
    else:
        mid = (start + stop) // 2
        return binary_sum(S, start, mid) + binary_sum(S, mid, stop)

這個遞歸每次執行都會調用兩次該函數，所以說是二路遞歸，每次遞歸後，範圍縮小一半，所以該遞歸的深度是1+logn

多重遞歸

如果一個遞歸調用可以開始三個或者更多其他遞歸調用，我們稱之為多重遞歸

例如：

import os

def disk_usage(path):
    """
    計算一個文件系統的磁碟使用情況，

    """

    total = os.path.getsize(path)
    if os.path.isdir(path):
        for filename in os.listdir(path):
            childpath = os.path.join(path, filename)
            total += disk_usage(childpath)
    print('{0:<7}'.format(total), path)
    return total

os.path.getsize為獲得標識的文件或者目錄使用的即時磁碟空間大小。我理解的是如果該標識的是一個文件，那麼就是獲得該文件的大小，如果是一個文件夾的話，那就是獲得該文件夾的大小，但不包括文件夾裡邊的內容，就像是一個盒子中放了很多物品，但這裡只計算了盒子的重量，但沒有計算物品的重量，也就是計算了一個空盒子。所以這個遞歸函數中的遞歸調用次數取決於這一層文件或文件夾的數量，所以是多重遞歸。

遞歸的不足

遞歸的不足顯然就是時間與空間的消耗，具體可以參考https://www.cnblogs.com/sfencs-hcy/p/10171457.html ，這篇文章中使用了緩存的方法減少了斐波那契數列的計算消耗，在這裡我們使用另一種方式來改善那種壞的遞歸：

def fibonacci(n):
    """
    斐波那契數列計算，返回的是一個元組

    """

    if n <= 1:
        return (n, 0)
    else:
        (a, b) = fibonacci(n - 1)
        return(a + b, a)

將原來的二路遞歸改為了線性遞歸，減少了重覆的計算。

python的最大遞歸深度

每一次遞歸都會有資源的消耗，每一次連續的調用都會需要額外的記憶體，當產生無限遞歸時，那就意味著資源的迅速耗盡，這明顯是不合理的。python為了避免這種現象，在設計時有意的限制了遞歸的深度，我們可以測試一下

def limitless(n):
    print('第' + str(n) + '次調用')
    n += 1
    return limitless(n)

limitless(1)

第988次調用
第989次調用
第990次調用
第991次調用
第992次調用
第993次調用
第994次調用
第995次調用
第996次調用
Traceback (most recent call last):
File “D:/github/Data-Structure/code/遞歸.py”, line 73, in
limitless(1)
File “D:/github/Data-Structure/code/遞歸.py”, line 70, in limitless
return limitless(n)
File “D:/github/Data-Structure/code/遞歸.py”, line 70, in limitless
return limitless(n)
File “D:/github/Data-Structure/code/遞歸.py”, line 70, in limitless
return limitless(n)
[Previous line repeated 992 more times]
File “D:/github/Data-Structure/code/遞歸.py”, line 68, in limitless
print(‘第’ + str(n) + ‘次調用’)
RecursionError: maximum recursion depth exceeded while calling a Python object

最終遞歸到996次停止了遞歸，也就是python的遞歸深度限制在了1000附近。

1000層的限制已經是足夠的了，但是還是有可能限制到某些計算，所以python提供了一個修改限制的方式

import sys
def limitless(n):
    print('第' + str(n) + '次調用')
    n += 1
    return limitless(n)

print(sys.getrecursionlimit())#1000
sys.setrecursionlimit(2000)
limitless(1)

第1994次調用
第1995次調用
第1996次調用
Traceback (most recent call last):
File “D:/github/Data-Structure/code/遞歸.py”, line 70, in limitless
return limitless(n)
File “D:/github/Data-Structure/code/遞歸.py”, line 70, in limitless
return limitless(n)
File “D:/github/Data-Structure/code/遞歸.py”, line 70, in limitless
return limitless(n)
[Previous line repeated 995 more times]
File “D:/github/Data-Structure/code/遞歸.py”, line 68, in limitless
print(‘第’ + str(n) + ‘次調用’)
RecursionError: maximum recursion depth exceeded while calling a Python object

可見把這個深度該為2000後便多了1000次調用，但這個深度顯然不是設置多少就是多少，畢竟還有電腦CPU與記憶體的限制，比如吧深度改為10000，那麼運行後

第3920次調用
第3921次調用
第3922次調用
第3923次調用

Process finished with exit code -1073741571 (0xC00000FD)

到達3923次便終止了，查詢-1073741571發現是遞歸棧溢出的問題。

尾遞歸

如果一個函數中所有遞歸形式的調用都出現在函數的末尾，我們稱這個遞歸函數是尾遞歸的。當遞歸調用是整個函數體中最後執行的語句且它的返回值不屬於表達式的一部分時，這個遞歸調用就是尾遞歸。尾遞歸函數的特點是在回歸過程中不用做任何操作，這個特性很重要，因為大多數現代的編譯器會利用這種特點自動生成優化的代碼。

Python解釋器在對於一次函數調用中，會使用一個棧幀來保存當前調用的函數的信息，如輸入參數、返回值空間、計算表達式時用到的臨時存儲空間、函數調用時保存的狀態信息以及輸出參數。因此在遞歸的調用中，這種未執行完的函數會一層一層的占用大量的棧幀。如果將遞歸的調用放到函數執行的最後一步，那麼執行完這步，該次函數的棧幀就會釋放，調用函數的新棧幀就會替換掉之前的棧幀，所以無論調用的深度有多少次，都只會占用一個棧幀，那也就不會發生棧溢出的問題。這就是尾遞歸。

所以根據需要，尾遞歸必須是線性遞歸，並且遞歸調用的返回值必須立即返回。

拿一個階乘遞歸函數舉例

def factorial(n):
    """
    階乘遞歸函數

    """
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

上邊這個是一個普通的遞歸，下麵把他改成尾遞歸的形式

def facttail(n, res):
    """
    階乘尾遞歸，res初始為1

    """

    if n < 0:
        return 0
    elif n == 0:
        return 1
    elif n == 1:
        return res
    else:
        return facttail(n - 1, n *res)

這個函數比之前那個還多了個res，第一種每次調用完要乘n，這裡的res就起了相同的作用，由於尾遞歸每一層的棧幀要釋放，所以通過res來作為相乘的過程。我個人認為尾遞歸的難度就在於參數的設計，因為它的前提條件就是調用後什麼也不再執行了，所以要作為傳遞的東西就得提前通過參數設計傳遞，總之要想設計一個尾遞歸的演算法還是需要好好思考一下的。

參考《數據結構與演算法Python語言實現》