如何使用Python來理解遞歸（程式碼講解）

這篇文章帶給大家的內容是關於如何使用Python來理解遞歸（程式碼講解），有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

遞歸

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

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

遞迴的分類

這裡根據遞迴呼叫的數量分為線性遞迴、二路遞迴與多重遞迴

線性遞迴

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

例如：

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(&#39;{0:<7}&#39;.format(total), path)
    return total

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

遞歸的不足

遞歸的不足顯然就是時間與空間的消耗，這篇文章中使用了快取的方法減少了斐波那契數列的計算消耗，在這裡我們使用另一種方​​式來改善那種壞的遞歸：

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 objec

可见把这个深度该为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來理解遞歸（程式碼講解）的詳細內容。更多資訊請關注PHP中文網其他相關文章！