Pythonバージョン確認
C:\recurse>py -V Python 3.6.5
再帰動作検証その1
自然数1~5の足し算
# file_name: recurse.py def recurse_add(n): if n==1: return 1 return n + recurse_add(n - 1) if __name__ == '__main__': recurse_add(5)
Stackの様子を見てみよう、下から上の順にPush、逆のほうからPop(LIFO)
recurse_add(1) 2+recurse_add(1) 3+recurse_add(2) 4+recurse_add(3) 5+recurse_add(4)
再帰動作検証その2
フォルダーc:/recurse/直下のサブフォルダー、ファイル名を階層で表示
Pythonコード
# file_name: recurse.py import os FOLDER = "c:/recurse/" def main(): counter_recurse = 0 # 再帰counter初期化 print_files(FOLDER, counter_recurse) # folderとsub_folerのfilesをプリントする def print_files(folder, counter_recurse): # 再帰関数の入り口 for f in os.listdir(folder): full_name = folder + f # PATHつきfile名 または folder名 if os.path.isdir(full_name): # folderの場合 # folder名プリント print(" " * 5 * counter_recurse + f + ", counter_recurse =" , counter_recurse) counter_recurse = counter_recurse + 1 # folder名プリント print_files(full_name + "/", counter_recurse) # 再帰、スタックにプッシュ、LIFOでポップ counter_recurse = 0 # 再帰counterリセット、再帰毎終了時に実行 elif os.path.isfile(full_name): # fileの場合 print(" " * 5 * counter_recurse + f) # file名プリント if __name__ == '__main__': main()
確認
C:\recurse>py recurse.py file_in_recurse.txt folder1, counter_recurse = 0 folder2, counter_recurse = 1 folder3, counter_recurse = 2 folder4, counter_recurse = 3 file_in_folder4.txt folder5, counter_recurse = 0 folder6, counter_recurse = 1 folder7, counter_recurse = 2 file_in_folder7.txt recurse.py
決定木の再帰
# 葉っぱの数を取得する def getNumLeafs(myTree): numLeafs = 0 firstStr = myTree.keys()[0] secondDict = myTree[firstStr] for key in secondDict.keys(): if type(secondDict[key]) is dict: numLeafs += getNumLeafs(secondDict[key]) else: numLeafs += 1 return numLeafs # 木の深さを取得する def getTreeDepth(myTree): maxDepth = 0 firstStr = myTree.keys()[0] secondDict = myTree[firstStr] for key in secondDict.keys(): if type(secondDict[key]) is dict: thisDepth = 1 + getTreeDepth(secondDict[key]) else: thisDepth = 1 if thisDepth > maxDepth: maxDepth = thisDepth return maxDepth
以上