はじめに
こんにちは！アメリカの大学で語学を学びながら、独学でソフトウェアエンジニアを目指している者です。
本日は再帰呼び出しについて記事にしていこうと思います。
たのしいRubyで勉強している際に自分自身を呼び出すという仕組みである再帰呼び出しを知りました。
「再帰呼び出し」とは、自分自身を呼び出すメソッドのことです。
この仕組みを使うことで、ディレクトリの探索や木構造の処理といった、複雑な問題をシンプルに解くことができます。
この記事では、再帰呼び出しの基本から具体例まで解説していきます。
再帰呼び出しとは
再帰呼び出しとは、メソッドが自分自身を呼び出す仕組みのことです。この仕組みを用いると、問題を小さな部分に分解しながら解決できます。再帰には次の2つの要素が必要です。
- 再帰条件
再帰を進めるための条件（問題を分割して解決する）。 - 終了条件
処理を終了するための条件（解を求める終点）。
この仕組みは、例えばディレクトリの探索や木構造の処理といった場面で特に有効です。
## 再帰呼び出しの具体例
以下のコードは、楽しいRubyから参照しました。
このコードは、あるディレクトリ構造を再帰的に探索してファイル名を表示する例です。
def traverse(path)
if File.directory?(path)
dir = Dir.open(path)
while name = dir.read
next if name == "." || name == ".." # カレントディレクトリと親ディレクトリをスキップ
traverse(path + "/" + name) # 再帰呼び出し
end
dir.close
else
process_file(path) # ファイルを処理
end
end
def process_file(path)
puts path # ファイルパスを出力
end
traverse(ARGV[0]) # コマンドライン引数で渡されたパスを探索
- ディレクトリとファイルの判定
if File.directory?(path)
File.directory?(path) は、現在のパスがディレクトリかどうかを判定します。
- ディレクトリの場合
中のエントリを探索するため、Dir.open を使用。 - ファイルの場合
再帰呼び出しを行わずに process_file を実行します。
- 再帰呼び出しの進行
while name = dir.read
next if name == "." || name == ".." # 特殊エントリをスキップ
traverse(path + "/" + name) # 再帰呼び出し
end
ここでは、ディレクトリ内のすべてのエントリを1つずつ読み取ります。
ただし、next if nameを使用することで"."（カレントディレクトリ）や ".."（親ディレクトリ）をスキップし、無限ループを防ぎます。
ファイルやサブディレクトリに応じて再帰を進めます。
- 終了条件
このコードでは、終了条件が以下の形で実現されています：
ディレクトリをすべて読み終えると、dir.read が nil を返し、while ループが終了します。
ファイルに到達した場合、再帰は発生せず処理が終了します
process_file(path)
- 再帰の例
例えば、次のディレクトリ構造を上記のコードをもちいて探索するとしましょう
root/
├── file1.txt
├── dir1/
│ ├── file2.txt
│ └── dir2/
│ └── file3.txt
└── file4.txt
- 最初の呼び出し
traverse("root")が呼ばれます。
ファイルである"file1.txt"を処理して出力し、"dir1"に入ります（再帰呼び出し）。 - 再帰の進行
上記の再帰呼び出しによって、traverse("root/dir1")が呼ばれます。
ファイルである"file2.txt"を処理して出力し、"dir2"に入ります（再帰呼び出し）。 - 終了条件の到達
上記同様にtraverse("root/dir1/dir2")が呼ばれます。
ファイルである"file3.txt"を処理して出力し、ディレクトリのエントリをすべて読み終えたので再帰から戻ります。 - 処理の戻り
再帰が終了すると、再び"root"に戻り、残りのエントリ（"file4.txt")を処理します。
再帰呼び出しを使用する上での注意点
再帰呼び出しを使う際には、次のポイントに注意しましょう。
-
終了条件を明確にする
終了条件がないと無限ループになり、プログラムが停止しなくなります。このコードでは、特殊エントリ"."や".."をスキップし、無限ループを防いでいます。 -
スタックオーバーフローに注意
再帰の深さが深くなるとメモリを大量に消費し、スタックオーバーフローが発生する可能性があります。非再帰的な方法も検討してください。 -
再帰が適切なケースで使われているか確認
再帰はディレクトリ探索や木構造の処理には適していますが、処理が深すぎたり効率が悪くなる場合はループを使用する方法を検討しましょう。
まとめ
再帰呼び出しは、自分自身を呼び出すメソッドを活用することで、複雑な処理を簡潔に記述するテクニックです。
このコードでは、ディレクトリ構造を再帰的に探索する仕組みを学びました。
また勉強中で学んだことがあれば積極的にシェアしていきたいと思います。