# 普通函數(shù)方法
def hanshu(n):
 sum = 0
 # 循環(huán)遍歷每一個(gè)數(shù)字，將他們加到一個(gè)事先定義好的變量上，直到加完
 for x in range(1, n+1):
  sum += x
 return sum

# 遞歸
def digui(n):
 if n == 1:
  return 1 # 如果n等于1證明已經(jīng)遞歸到最后，返回1，這就是上述的臨界條件
 else:
  return n + digui(n-1) # 當(dāng)沒有達(dá)到臨界條件時(shí)，用n加上對(duì)n-1的遞歸，每次都把n加進(jìn)去，但是后面依然是使用當(dāng)下這個(gè)遞歸函數(shù)，會(huì)再次調(diào)用計(jì)算n-1，直到遞歸結(jié)束，也就是將從n到1的數(shù)全部遞歸完

import os # 由于我們遍歷目錄，所以要找到那個(gè)目錄并操作，os模塊包含普遍的操作系統(tǒng)功能
path = "" # 這是我們要遍歷的目錄的路徑，需要自己寫進(jìn)去
# 既然是遞歸函數(shù)，那么肯定要有個(gè)函數(shù)，而且這個(gè)函數(shù)還將在函數(shù)內(nèi)部再次被調(diào)用
def getAllDir(path, sp = ''): # 參數(shù)中傳入路徑和sp，這個(gè)我最后說一句你就明白了
 # 得到當(dāng)前目錄下的所有文件
 filesList = os.listdir(path) # os.listdir()是os模塊下的一個(gè)方法，相當(dāng)于Linux中的ls，查看所有文件
 sp += " " # 這個(gè)也先放一下
 # 處理每一個(gè)文件
 for fileName in filesList: # 遍歷剛才找到的目錄下的所有文件
  # 判斷是否是目錄（要用絕對(duì)路徑）
  fileAbsPath = os.path.join(path,fileName) # join是os模塊下將兩個(gè)路徑拼接在一起的意思，第二個(gè)參數(shù)不能有斜杠。因?yàn)槲覀円袛嘁幌逻@個(gè)文件是一個(gè)普通文件還是一個(gè)目錄，所有要先把他的絕對(duì)路徑整理出來
  if os.path.isdir(fileAbsPath): # isdir是判斷是否為目錄，是則返回True
   print(sp + "目錄：", fileName) # 打印當(dāng)前這個(gè)文件，他是個(gè)目錄
   getAllDir(fileAbsPath,sp = " ") # 這里就開始遞歸了，因?yàn)槲覀円业秸麄€(gè)目錄里的東西，所以當(dāng)這個(gè)文件還是個(gè)目錄的時(shí)候我們需要繼續(xù)向下找
  else:
   print(sp + "普通文件：", fileName) # 如果僅僅是個(gè)普通文件，那么他里面也就沒有其他文件了，就可以直接打印他了
getAllDir(path) # 這里是調(diào)用函數(shù)，讓遍歷開始
# 最后我來說一下開始寫的那個(gè)sp，是space的意思，有人也許現(xiàn)在就明白了。那個(gè)其實(shí)就是讓我們方便觀察，因?yàn)槊看未蛴《际琼斝袑懙?，我們分不清他的目錄結(jié)構(gòu)，所以通過空格來調(diào)整。在函數(shù)內(nèi)部寫一個(gè)空格增加的表達(dá)式，可以使調(diào)用次數(shù)和空格數(shù)相關(guān)起來，遞歸的越深，證明目錄的級(jí)越低，那么空格越多

# 整體思路是沒有變得，這里沒有寫到的也許是重復(fù)的，看下上面注釋就好了
# 寫了一半想起來應(yīng)該回來寫一下棧：棧就是一個(gè)容器，但它只有一個(gè)口，入棧出棧都從這一個(gè)口，而且這個(gè)棧很細(xì)，進(jìn)去了就不能顛倒位置了，所以，每入棧一個(gè)元素他在最外面時(shí)候可以出來，否則得等前面的走完了它才可以出來
import os
def getAllDirDFS(path):
 stack = [] # 這里是用棧來模擬，我們先創(chuàng)建一個(gè)列表當(dāng)做棧
 stack.append(path) # 首先，先向棧里壓入路徑
 # 處理?xiàng)?，?dāng)棧為空時(shí)結(jié)束循環(huán)（棧為空就說明棧里沒有普通文件和目錄了，因?yàn)槲覀兪敲坎僮饕粋€(gè)要把那個(gè)取出來）
 while len(stack) != 0:
  # 從棧中取出數(shù)據(jù)
  dirPath = stack.pop() # pop函數(shù)是刪除最后一個(gè)元素，同時(shí)還有一個(gè)返回值，就是去除的那個(gè)元素，我們?cè)俳邮找幌碌鹊扔?
  # 目錄下所有文件
  filesList = os.listdir(dirPath) # 這個(gè)和上面一樣
  # 處理每一個(gè)文件，如果是普通文件則打印出來，如果是目錄則將該目錄地址壓棧
  for fileName in filesList:
   # print(dirPath)
   fileAbsPath = os.path.join(dirPath,fileName)
   # print(fileAbsPath)
   if os.path.isdir(fileAbsPath):
    # 是目錄就壓棧
    print("目錄：" + fileName)
    stack.append(fileAbsPath) # 當(dāng)是目錄時(shí)入棧，它這時(shí)就在最外面，下一次循環(huán)時(shí)候要取出棧的元素是不是還是這個(gè)啊，既然是它的話就還有找他內(nèi)部的東西，等把他找完了才繼續(xù)找和他并列的那些文件。就是說抓住一根繩子使勁往下找，找到頭沒有了才返回來，這就是深度優(yōu)先遍歷
   else:
    # 打印普通文件
    print("普通：" + fileName)
getAllDirDFS(path)

# 這回記住了，先說一下隊(duì)列，隊(duì)是一個(gè)兩端開口的模型，一頭進(jìn)一頭出，當(dāng)然還有雙向隊(duì)列，循環(huán)等等，我們就簡(jiǎn)單用一下最基本的隊(duì)列
import collections # 隊(duì)列在python的包里有，所以我們直接調(diào)用一下，不用以為這個(gè)很難，他也只不過是類型是queue，實(shí)際的思想是一樣的，入隊(duì)append，因?yàn)檫@個(gè)是在右側(cè)，也就是后方入隊(duì)，另一邊出的話就是popleft，左側(cè)出，是不是很通俗，只是改了一下出來的口
def getAllDirBFS(path):
 queue = collections.deque() # 創(chuàng)建一個(gè)隊(duì)列，只要記得后面用法就是上面我說的那個(gè)不同就可以了
 queue.append(path)
 while len(queue) != 0:
  dirPath = queue.popleft() # 僅僅這里不同，因?yàn)殛?duì)列模擬是另一端出隊(duì)
  filesList = os.listdir(dirPath)
  for fileName in filesList:
   fileAbsPath = os.path.join(dirPath,fileName)
   if os.path.isdir(fileAbsPath):
    print('目錄：' + fileName)
    queue.append(fileAbsPath)
   else:
    print('文件：' + fileName)
getAllDirBFS(path)  
# 大家想一下，棧是哪里進(jìn)哪里出，也就是，剛進(jìn)去的元素，接下來的一次循環(huán)又出來了，那便是一條路走到頭，是深度遍歷；那么現(xiàn)在一頭進(jìn)另一頭出是什么意思呢，就是即便判斷了這個(gè)是一個(gè)目錄，但我現(xiàn)在不執(zhí)行你，我要把你前面這些都查一遍，找完是目錄的都添加在后面，之后再遍歷你們這些，就是把一層的內(nèi)容找完再找下一層，被稱為廣度優(yōu)先遍歷。