Python3再帰動作検証～決定木まで

Pythonバージョン確認

C:\recurse>py -V
Python 3.6.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)

再帰動作検証その２

フォルダー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

以上