遞歸

一個(gè)函數(shù)在執(zhí)行過程中一次或多次調(diào)用其本身便是遞歸，就像是俄羅斯套娃一樣，一個(gè)娃娃里包含另一個(gè)娃娃。

遞歸其實(shí)是程序設(shè)計(jì)語言學(xué)習(xí)過程中很快就會(huì)接觸到的東西，但有關(guān)遞歸的理解可能還會(huì)有一些遺漏，下面對(duì)此方面進(jìn)行更加深入的理解

遞歸的分類

這里根據(jù)遞歸調(diào)用的數(shù)量分為線性遞歸、二路遞歸與多重遞歸

線性遞歸

如果一個(gè)遞歸調(diào)用最多開始一個(gè)其他遞歸調(diào)用，我們稱之為線性遞歸。

例如：

def binary_search(data, target, low, high):  """  二分查找，對(duì)有序列表進(jìn)行查找，如果找到則返回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)

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

二路遞歸

如果一個(gè)遞歸調(diào)用可以開始兩個(gè)其他遞歸調(diào)用，我們稱之為二路遞歸

例如：

def binary_sum(S, start, stop):  """  二路遞歸計(jì)算一個(gè)序列的和，例如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)

這個(gè)遞歸每次執(zhí)行都會(huì)調(diào)用兩次該函數(shù)，所以說是二路遞歸，每次遞歸后，范圍縮小一半，所以該遞歸的深度是1+logn

多重遞歸

如果一個(gè)遞歸調(diào)用可以開始三個(gè)或者更多其他遞歸調(diào)用，我們稱之為多重遞歸

例如：

import os def disk_usage(path):  """  計(jì)算一個(gè)文件系統(tǒng)的磁盤使用情況，   """   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為獲得標(biāo)識(shí)的文件或者目錄使用的即時(shí)磁盤空間大小。我理解的是如果該標(biāo)識(shí)的是一個(gè)文件，那么就是獲得該文件的大小，如果是一個(gè)文件夾的話，那就是獲得該文件夾的大小，但不包括文件夾里邊的內(nèi)容，就像是一個(gè)盒子中放了很多物品，但這里只計(jì)算了盒子的重量，但沒有計(jì)算物品的重量，也就是計(jì)算了一個(gè)空盒子。所以這個(gè)遞歸函數(shù)中的遞歸調(diào)用次數(shù)取決于這一層文件或文件夾的數(shù)量，所以是多重遞歸。

遞歸的不足

遞歸的不足顯然就是時(shí)間與空間的消耗 ，這篇文章中使用了緩存的方法減少了斐波那契數(shù)列的計(jì)算消耗，在這里我們使用另一種方式來改善那種壞的遞歸：