Day10,遞歸函數，遍歷目錄

一、遞歸

1. 定義: 一個函數調用了自身的編程技巧

2. 思維方式:

1） 找出這一次調用和上一次調用的關係;

2） 找出臨界條件(退出遞歸的條件);

3） 假設當前的函數已經能夠使用, 調用自身求出上一次結果, 再求出本次結果

def factorial_(n): # 計算n的階乘 if n == 1: return 1 return n * factorial_(n-1) # 函數調用他自己：遞歸調用

由於內存的問題，遞歸函數很容易有棧溢出的異常，所有遞歸的次數有限。解決遞歸的次數限制的方式： 尾遞歸

3. 尾遞歸

只返回函數本身，不包含表達式，可以本次計算的結果存放函數的參數中。

def factorial_(n, res=1): # 尾遞歸函數 if n == 1: return res return factorial_(n-1, n*res)

注意：Python標準的解釋器沒有針對尾遞歸做優化，棧有最大深度限制，所以任何遞歸函數都存在站溢出的問題，哪怕是普通的尾遞歸函數。

4. 優化後的尾遞歸（沒有溢出的問題）

def factorial_(n, res=1): if n == 1: yield res yield factorial_(n-1, n*res)def factorial_G(n): # 優化最大棧幀的問題，藉助於生成器 a = factorial_(n) while True: if isinstance(a, types.GeneratorType): a = next(a) else: break return a

5. 練習

1）猴子吃桃（Day4中有案例）

2）兩個數的最大公約數

二、遍歷目錄

1. 獲取目錄下的所有目錄名和文件名

def get_all(sourcePath, level): list_file_name = os.listdir(sourcePath) # 獲取該目錄下所有的文件目錄名 for file_name in list_file_name: full_name = os.path.join(sourcePath, file_name) # 拼接成完整的目錄名 if os.path.isdir(full_name): # 判斷是否是目錄 print((%s % file_name).rjust((5-level)*10,-)) get_all(full_name, level+1) if os.path.isfile(full_name): # 判斷是否是文件 print((%s % file_name).center((5-level)*10, -))path = r../print(../.ljust(80, -))get_all(path, 0)

2. 擴展練習

1）模擬棧數據結構：先進後出，後進先出

def pop_(stack): if len(stack) == 0: return -1 return stack.pop()def push(stack, item): # 壓棧 stack.append(item)sl = []push(sl, 5)push(sl, 10)push(sl, 9)print(pop_(sl))print(pop_(sl))print(pop_(sl))print(pop_(sl))

2）模擬隊列數據結構

import collectionsqueue = collections.deque([1,2,3,4], maxlen=400) # 創建一個對隊列queue.append(3) # 往隊列右邊添加元素print(queue)queue.appendleft(5) # 往隊列左邊添加元素print(queue)queue.popleft() # 從隊列左邊彈出一個元素print(queue)queue.pop() # 從隊列右邊彈出一個元素print(queue)

3. 深度遍歷（堆棧方式存儲路徑）

import osstack = []path = ..stack.append(path) # 壓棧while True: if len(stack) == 0: # 棧彈空了退出 break dir_ = stack.pop() # 彈棧 print(dir_.ljust(40, )) fs = os.listdir(dir_) for fname in fs: fpath = os.path.join(dir_, fname) if os.path.isdir(fpath): stack.append(fpath) # 入棧 else: dir_len = len(dir_) print(|.rjust(dir_len+2, )+fname.rjust(1+len(fname),-))

4. 廣度遍歷（隊列的方式存儲路徑）

import os, collectionsqueue = collections.deque() # 創建一個空的雙向列表queue.append(../) # 添加需要遍歷的根目錄while True: if len(queue) == 0: # 判斷雙隊列是否為空 break deal_path = queue.popleft() # 取出需要遍歷的目錄 print(deal_path) for fname in os.listdir(deal_path): fpath = os.path.join(deal_path, fname) if os.path.isdir(fpath): queue.append(fpath) # 把下一級目錄從右邊添加進去 else: print(|.rjust(15, ) + fname.rjust(30,-))

三、作業

1. 基於深度遍歷，遍歷某一目錄下，所有文件及子目錄中文件的個數和大小，通過回調函數將目錄名、文件個數和文件總大小(bytes位元組)和耗時寫入到files_count.dat文件中

2. 定義裝飾函數，實現針對文件操作時，判斷文件路徑是否存在，如果不存在，則創建目錄

3. 開發文件管理系統， 提供新建文件 new 、文件刪除 del、目錄創建 mk、切換目錄cd 等功能