遞歸

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

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

遞歸的分類

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

線性遞歸

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

例如：

            
def binary_search(data, target, low, high):
  """
  二分查找，對有序列表進(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)
          

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

二路遞歸

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

例如：

            
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)
          

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

多重遞歸

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

例如：

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

遞歸的不足

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

            
def fibonacci(n):
  """
  斐波那契數(shù)列計算，返回的是一個元組
 
  """
 
  if n <= 1:
    return (n, 0)
  else:
    (a, b) = fibonacci(n - 1)
    return(a + b, a)
          

將原來的二路遞歸改為了線性遞歸，減少了重復(fù)的計算。

python的最大遞歸深度

每一次遞歸都會有資源的消耗，每一次連續(xù)的調(diào)用都會需要額外的內(nèi)存，當(dāng)產(chǎn)生無限遞歸時，那就意味著資源的迅速耗盡，這明顯是不合理的。python為了避免這種現(xiàn)象，在設(shè)計時有意的限制了遞歸的深度，我們可以測試一下

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

第988次調(diào)用
第989次調(diào)用
第990次調(diào)用
第991次調(diào)用
第992次調(diào)用
第993次調(diào)用
第994次調(diào)用
第995次調(diào)用
第996次調(diào)用
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) + ‘次調(diào)用')
RecursionError: maximum recursion depth exceeded while calling a Python object

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

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

            
import sys
def limitless(n):
  print('第' + str(n) + '次調(diào)用')
  n += 1
  return limitless(n)
 
print(sys.getrecursionlimit())#1000
sys.setrecursionlimit(2000)
limitless(1)
          

            
第1994次調(diào)用
第1995次調(diào)用
第1996次調(diào)用
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) + ‘次調(diào)用')
RecursionError: maximum recursion depth exceeded while calling a Python objec
          

可見把這個深度該為2000后便多了1000次調(diào)用，但這個深度顯然不是設(shè)置多少就是多少，畢竟還有計算機(jī)CPU與內(nèi)存的限制，比如吧深度改為10000，那么運行后

第3920次調(diào)用
第3921次調(diào)用
第3922次調(diào)用
第3923次調(diào)用

Process finished with exit code -1073741571 (0xC00000FD)

到達(dá)3923次便終止了，查詢-1073741571發(fā)現(xiàn)是遞歸棧溢出的問題。

尾遞歸

如果一個函數(shù)中所有遞歸形式的調(diào)用都出現(xiàn)在函數(shù)的末尾，我們稱這個遞歸函數(shù)是尾遞歸的。當(dāng)遞歸調(diào)用是整個函數(shù)體中最后執(zhí)行的語句且它的返回值不屬于表達(dá)式的一部分時，這個遞歸調(diào)用就是尾遞歸。尾遞歸函數(shù)的特點是在回歸過程中不用做任何操作，這個特性很重要，因為大多數(shù)現(xiàn)代的編譯器會利用這種特點自動生成優(yōu)化的代碼。

Python解釋器在對于一次函數(shù)調(diào)用中，會使用一個棧幀來保存當(dāng)前調(diào)用的函數(shù)的信息，如輸入?yún)?shù)、返回值空間、計算表達(dá)式時用到的臨時存儲空間、函數(shù)調(diào)用時保存的狀態(tài)信息以及輸出參數(shù)。因此在遞歸的調(diào)用中，這種未執(zhí)行完的函數(shù)會一層一層的占用大量的棧幀。如果將遞歸的調(diào)用放到函數(shù)執(zhí)行的最后一步，那么執(zhí)行完這步，該次函數(shù)的棧幀就會釋放，調(diào)用函數(shù)的新棧幀就會替換掉之前的棧幀，所以無論調(diào)用的深度有多少次，都只會占用一個棧幀，那也就不會發(fā)生棧溢出的問題。這就是尾遞歸。

所以根據(jù)需要，尾遞歸必須是線性遞歸，并且遞歸調(diào)用的返回值必須立即返回。

拿一個階乘遞歸函數(shù)舉例

            
def factorial(n):
  """
  階乘遞歸函數(shù)
 
  """
  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)
          

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