Python中遞歸以及遞歸遍歷目錄詳解

Posted on by

遞歸

遞歸的概念：函數包含瞭對自身的調用，那麼就是遞歸

使用的場景：如果你發現你將要做的事情就是你現在做的，那麼用遞歸

遞歸類似循環；在編寫或閱讀遞歸時，首先我們關註的是遞歸的終止條件

遞歸求和

在接觸遞歸之前，我們先來做這麼一個問題：如果說，要對一個數字列表求和（或者其他序列）求和，除瞭我們可以使用內置的sum函數，還有什麼辦法？

while循環

L = [1,2,3,4,5]
mysum = 0 #保存和的變量
while L: #將列表最為循環條件
	mysum += L[0] #每次將列表第一個位置的值加到和中
	L = L[1：] #去掉列表第一個元素

for循環

L = [1,2,3,4,5]
mysum = 0
for var in L:
	mysum += var

遞歸求和

def mysum(L):
    if not L:
        print ('L is empty')
        return 0
    else:
      	return L[0]+mysum(L[1:])
# 在返回值中，我們返回瞭一個函數的調用，並且傳遞的參數為去掉當前列表第一個元素的新列表

遞歸處理非線性循環

遞歸還可以處理一些非線性循環，而普通的循環是無法處理的；比如這樣一個列表對其求和：

L = [1,[2,[3,4],5],6,[7,8]]

由於這個列表不是一個線性迭代，包含著復雜的元素嵌套，普通的循環語句處理起來將會非常難以控制

L = [1,[2,[3,4],5],6,[7,8]]
sum = 0
def mysum(L):
    global sum
    for var in L:
    	if not isinstance(var,list):   
            #如果其中元素不為列表類型，則為一個確定的值
            sum += var
        else:
         	mysum(var)
    return

花錢遞歸

思考：假如你有10000塊，每天花一半，毛錢直接舍棄，那麼這錢可以花幾天？

遞歸解決：

def cost(money,day=0):
    if money > 0:
        money = money // 2 #每次花一半
        day += 1 #花完天數+1
        cost(money,day) #開啟花錢遞歸
    else:
        print('一共可以花%d天' % day)
        return #必須要有的一個終止條件

遞歸註意事項

Python中，遞歸的最大上限次數差不多是998次，一個沒有終止條件的遞歸會引發錯誤(類似一個死循環)

這是因為遞歸的每一次函數執行，都會在內存中產生新的函數副本，遞歸的內存消耗要大於普通循環

>>> def func():
...     return func()
...
>>> func()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in func
  File "<stdin>", line 2, in func
  File "<stdin>", line 2, in func
  [Previous line repeated 995 more times]
RecursionError: maximum recursion depth exceeded
#這裡我們在995次遞歸之後，達到上線，從而報錯

我們也可以手動幹預遞歸的上限，但是這是有風險的，要結合計算機本身內存來考慮

>>> import sys
>>> sys.setrecursionlimit(num)
# num為控制修改的最大遞歸上限次數

實現Tree命令

核心思路在於，目錄結構的深度及廣度是錯綜復雜的，通過單純的循環來做判定是一件非常苦難的事情

而遞歸恰好適合這樣的非線性循環問題，當然也有一些弊端，當目錄結構越來越復雜，那麼程序的執行效率會越來越差

import os

def getdir(path, level=0):
    if path == '':
      	path = os.getcwd()  # 獲取當前的工作目錄
    level += 4
    num = level // 4
    abs_path = os.path.abspath(path)
    for name in os.listdir(path):  # 返回的是一個列表
        format_str = ''
        if os.path.isfile(os.path.join(abs_path, name)):
            for var in range(num):  # range函數用來控制循環次數
              	format_str += '_' * 4 + '▕'
            format_str = format_str[0:-1]
            format_str += name
            mystr = format_str.replace('_', ' ', level-4)  # 替換掉level-4個_
    else:
        for var in range(num): # range函數用來控制循環次數
            format_str += '_' * 4 + '▕' # 輸出樣式構造
        format_str += name
        mystr = format_str.replace('_',' ',level-4) # 替換掉level-4個_
    print(mystr) # 輸出格式字符串
    name = os.path.join(abs_path,name)
    if os.path.isdir(name): # 絕對路徑,判斷是否是文件夾
	    getdir(name,level)
path = input('請輸入你要遍歷的目錄：')
getdir(path)

總結

到此這篇關於Python中遞歸以及遞歸遍歷目錄的文章就介紹到這瞭,更多相關Python遞歸遍歷目錄內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：