Python理解遞歸的方法總結(jié)

更新時(shí)間：2019年01月28日 15:32:54 投稿：laozhang

在本篇文章里小編給大家分享了關(guān)于如何使用Python來理解遞歸的知識點(diǎn)內(nèi)容，有興趣的朋友們學(xué)習(xí)下。

遞歸

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

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

遞歸的分類

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

線性遞歸

如果一個(gè)遞歸調(diào)用最多開始一個(gè)其他遞歸調(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)

雖然在代碼中有兩個(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í)行都會調(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í)磁盤空間大小。我理解的是如果該標(biāo)識的是一個(gè)文件，那么就是獲得該文件的大小，如果是一個(gè)文件夾的話，那就是獲得該文件夾的大小，但不包括文件夾里邊的內(nèi)容，就像是一個(gè)盒子中放了很多物品，但這里只計(jì)算了盒子的重量，但沒有計(jì)算物品的重量，也就是計(jì)算了一個(gè)空盒子。所以這個(gè)遞歸函數(shù)中的遞歸調(diào)用次數(shù)取決于這一層文件或文件夾的數(shù)量，所以是多重遞歸。

遞歸的不足

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

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

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

python的最大遞歸深度

每一次遞歸都會有資源的消耗，每一次連續(xù)的調(diào)用都會需要額外的內(nèi)存，當(dāng)產(chǎn)生無限遞歸時(shí)，那就意味著資源的迅速耗盡，這明顯是不合理的。python為了避免這種現(xiàn)象，在設(shè)計(jì)時(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)是足夠的了，但是還是有可能限制到某些計(jì)算，所以python提供了一個(gè)修改限制的方

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

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

第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)是遞歸棧溢出的問題。

尾遞歸

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

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

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

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

def factorial(n):
  """
  階乘遞歸函數(shù)
 
  """
  if n == 0:
    return 1
  else:
    return n * factorial(n - 1)

上邊這個(gè)是一個(gè)普通的遞歸，下面把他改成尾遞歸的形式

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)

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

您可能感興趣的文章: