メイン・トピック
本稿の主題は再帰関数です。題材の都合上、ファイルやディレクトリのリスト取得(Windowsでいうところのdirコマンド、Unix系だとlsコマンド)を奥底まで辿るプロセスを取り扱います。
目指すところ
Pythonのプログラムで、ディレクトリ内のディレクトリおよびファイルを最下層までリストする仕組みを目指します。
以下はtreeコマンドの実行例です。こんな上等な見栄えではありませんが、端的に言えばこのような機能を目指しています。見た目の├とか└とかは面倒なのでやりません。
MacBookPro:Tips $ tree
.
├── 01.exception_info
│ └── exception_info.py
├── 02.str
│ └── 02.str.py
├── 03.type
│ └── sample.py
├── 04.AES
│ └── aes.py
├── 05.RSA
│ └── rsa.py
├── 06.tree
│ └── 06.tree.py
└── 09.misc
└── misc.py
学習できること
- ディレクトリの移動
- ファイル名やディレクトリ名の取得
- ファイルやディレクトリの判定
- 再帰関数
ソースコード
#!/usr/bin/env python3.8
import os
import glob
def list_file(dir_name=".", indent=0):
print(" " * indent + "[dir] " + dir_name)
for file in glob.glob(dir_name + "/*"):
if os.path.isfile(file):
filename = file.split("/")[-1]
print(" " * indent + "[file] " + filename)
if os.path.isdir(file):
list_file(file, indent + 1)
os.chdir("..")
list_file()
解説
他の投稿同様にソースコードのそれぞれの部分に説明を付けていきたいと思いますが、その前に先に重要な用語である再帰関数について触れたいと思います。
再帰関数
再帰関数とは、自分自身の定義の中に自分自身の呼び出しが登場する関数のことをいいます。
たいそうな名前を戴いていますが、再帰関数を表す特別な記述方法があるわけではありませんし、再帰関数であることを示す特別なキーワードも用意されていません。関数の中で自分自身を呼び出している部分を再帰呼び出しといいますが、その再帰呼び出しが登場している「何の変哲も無い関数」のことを再帰関数と呼ぶだけです。
ちなみに元となる言葉はrecursive functionで、recursion自体に再帰とか回帰、それから帰納といった意味があります。
ここで、帰納という言葉が登場しましたが、数学で帰納法という言葉にお目にかかった記憶がある方もいらっしゃるかと思いますが、概念的にはあの概念を思い浮かべると理解の助けになるかも知れません。あるいは、漸化式を思い浮かべるとしっくりくるかも知れません。
再帰関数のサンプル
#!/usr/bin/env python3.8
def total(num):
if num < 1:
return 0
return num + total(num - 1)
print(total(10))
解説
サンプルを実行すると結果は55と出ます。これは、1から10まで足し合わせた結果です。
再帰関数であるtotalは引数numをとっていますがtotal(10)ということで初期値として10が与えられていて、内部では10 + total(9)こそが結果であるという構造になっています。
問題を先送りしているというか、なんというか。total関数の存在を最大限活かした作りですね。
足し算じゃなくなってしまいますが、以下のイメージですね。(サンプルをかけ算にすれば良かったかな…)
10! = 10 * 9!
話を戻しますと、この構図だとtotal(9)はtotal(8)を使って、、、と順に値が下がっていき、total(0)となったところで答えは0なので、その場合のみif文で0を返して再帰呼び出しをしないという構図になっています。(もちろん、1のタイミングで1を返すのでもOKですよ)
単なるイメージですが、以下のような構図です。
total(10) = 10 + total(9)
total(9) = 9 + total(8)
total(8) = 8 + total(7)
total(7) = 7 + total(6)
total(6) = 6 + total(5)
total(5) = 5 + total(4)
total(4) = 4 + total(3)
total(3) = 3 + total(2)
total(2) = 2 + total(1)
total(1) = 1 + total(0)
total(0) = 0
total(1) = 1 + 0
total(2) = 2 + 1
total(3) = 3 + 3
total(4) = 4 + 6
total(5) = 5 + 10
total(6) = 6 + 15
total(7) = 7 + 21
total(8) = 8 + 28
total(9) = 9 + 36
total(10) = 10 + 45
ここで大事なことは、if文の条件を間違えると永遠に掘り進んでいくことになり理論上は停止しない無限ループと同じ構図になります。
理論上としたのには訳があります。いわゆるwhile Trueのようなループは本当に永遠と回り続けます。ですが、再帰関数の場合は計算の途中で次を呼び出している都合上、一番奥底の処理が終わると結果が戻ってきて続きの処理を実行しなければならず、この構図を無限にというわけにはいきません。要するにやり過ぎると、限界を迎えてエラーとなります。
どんなエラーが発生するかというと、Pythonの場合には以下のエラーが発生します。
RecursionError: maximum recursion depth exceeded
ここで、制限が設けられているということは、制限値を変えることも可能です。それについてはsys.getrecursionlimit() を参照してください。
ソースコードの解説
話を元のソースコードの解説にうつります。すでにどんなコードだったか忘れてしまったかと思いますので再掲します。
#!/usr/bin/env python3.8
import os
import glob
def list_file(dir_name=".", indent=0):
print(" " * indent + "[dir] " + dir_name)
for file in glob.glob(dir_name + "/*"):
if os.path.isfile(file):
filename = file.split("/")[-1]
print(" " * indent + "[file] " + filename)
if os.path.isdir(file):
list_file(file, indent + 1)
os.chdir("..")
list_file()
list_files関数は、ディレクトリ名とインデント数の2つの引数をとります。
print(" " * indent + "[dir] " + dir_name)
はじめにprint関数でディレクトリ名を表示しています。ちょっとしたTipsですが” ” * indentで文字列のかけ算が可能です。今回の場合空白2文字を1インデント分として前に挟みたいのでこのようにしています。
for file in glob.glob(dir_name + "/*"):
glob.glob関数によって、指定の名称のファイルおよびディレクトリの名前のリストが取得可能です。したがって変数名はfileとしていますが、果たしてそれが本当はファイルなのかディレクトリなのかはこの時点では分かっていません。
そこで次のif文における判定となります。
if os.path.isfile(file):
file変数に格納されている名前のオブジェクトがファイルであればTrueを返します。
filename = file.split("/")[-1]
ここで、file変数に格納されている文字列を/で分割(リスト化)して末尾の要素をfilename変数へ格納しています。ここで[-1]というのは後から数えて1つ目という指定です。
print(" " * indent + "[file] " + filename)
ファイルと分かったので、名前を出力しています。
if os.path.isdir(file):
同様に、file変数に格納されているオブジェクトがディレクトリであればTrueを返します。
list_file(file, indent + 1)
そしていよいよ真打ち登場です。ディレクトリと分かったのでlist_files関数に指定して、インデントを1つ深くして再帰呼び出しをしています。
最後にlist_files関数の呼び出し部分です。
os.chdir("..")
list_files()
ディレクトリを移動してから、このlist_files()を呼び出しています。引数には何も指定していないので、カレントディレクトリを表す . とインデント数 0 で再帰関数が呼ばれることになります。
実行例
(LearningPython) MacBookPro:06.tree $ ./06.tree.py
[dir] .
[dir] ./09.misc
[file] misc.py
[dir] ./05.RSA
[file] rsa.py
[dir] ./01.exception_info
[file] exception_info.py
[dir] ./02.str
[file] 02.str.py
[dir] ./06.tree
[file] 06.tree.py
[dir] ./03.type
[file] sample.py
[dir] ./04.AES
[file] aes.py
(LearningPython) MacBookPro:06.tree $
ソートしていないので、順番がバラバラですね。もし出てくる順番をソートしたいならば、sorted(glob.glob(dir_name + “/*”)などとやれば良いです。
まとめ
再帰関数について、実際に遭遇するであろう例を使って説明しましたが、いかがでしたでしょうか。手放しで歓迎していますと、無限ループに類する問題や、リソースの枯渇などを招く可能性がありますが、使いどころを間違わなければ、明らかに数学でいうところの数列あるいは帰納法の類いの発想との相性はぴったりなので、是非有効活用したいものです。