「再帰的」の意味がわかりません

Question

サブディレクトリを再帰的に削除します。
ディレクトリを再帰的に作成します。

この2つの「再帰的」の意味がわかりません。
「フォルダの中身全て」みたいな意味なのでしょうか？

フォルダ作成に際して、
「ディレクトリを再帰的に作成する」オプションを入れると
フォルダを最下位層まで一気に作れるということはプログラミングしているうちに
何となく理解したのですが、プログラミング用語の「再帰的」って何なのでしょうか？

wikipediaには
「再帰（さいき）は、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。」とあったのですが・・・。
ますます意味が分からなくなってしまいました・・・。

Answer 1

たとえば、
dir /S
を実行すると、ファイルのディレクトリ情報を読み出して順番に表示させます。
そして、ファイルじゃなくディレクトリであった場合、そのディレクトリに移動して、
ファイルのディレクトリ情報を読み出して順番に表示させ、
ファイルじゃなくディレクトリであった場合はそのディレクトリに移動して、
ファイルのディレクトリ情報を読み出して（以下略

とまあ、ディレクトリに出会うたび、同じ処理を最初からやり直す、という動作となり、これがまあ、再帰的動作、ということになります

まー、この同じ動作をプログラムでさせようと思ったときに、どういうふうにするかを考えると再帰、という動作がどういうことかよくわかるんですが。

Comments

[fermat]

再帰が「階層全部」なんて間違った理解をしていました。
「ディレクトリに出会うたび、同じ処理を最初からやり直す」動作をしているんですね。
ありがとうございます。

[y_waiwai]

そういうふうに処理を繰り返すことで、結果、それ以下の階層全部の処理を行うようになりますね

Answer 2

「再帰」とは、ある機能の処理の中でその機能の中で使うことを指します。

質問文にあるディレクトリ削除を例に取りましょうか。
ディレクトリの削除は以下の機能となっています。

1. 指定されたディレクトリの中のファイルを全て削除
2. 指定されたディレクトリを削除

では、以下のようなディレクトリがあったとして、

A_DIR/B_DIR/C_DIR/D.txt

A_DIRを削除しようとするとB_DIRを削除しなければなりません。
B_DIRを削除しようとするとC_DIRを削除しなければなりません。

この場合の再帰的というのは、削除機能の中で削除機能を使うということです。

A_DIRを削除する場合、以下のような流れで削除されます。

1. A_DIRの中にB_DIRがあるので先にA_DIRの削除機能がB_DIRを削除する
2. B_DIRの中にC_DIRがあるので先にB_DIRの削除機能がC_DIRを削除する
3. C_DIRの中のD.txtを削除する
4. C_DIRが削除される
5. B_DIRが削除される
6. A_DIRが削除される

Comments

[fermat]

再帰的な削除で何が起きているのか一つ一つのステップを解説してくださることで
「ある機能の処理の中でその機能の中で使う」がどういったことなのか理解できました。
ありがとうございます。

Answer 3

あるサブディレクトリを削除する時に、そのサブディレクトリの下に更にサブディレクトリがあった場合は、そのサブディレクトリも削除する、そのサブディレクトリの下に更にサブディレクトリがあったら・・・、と、サブディレクトリを削除するという処理を繰り返すことを「再帰的」に行うことを言います。
通常、自分で自分を呼び出すことで実現します。
サブディレクトリは無限にあるわけではないので、どこかで再帰呼び出しは止まりますので、無限ループにはなりません。
ただ、スタックを消費するのでメモリ不足には注意です。

再帰呼出し

Comments

[fermat]

リンク先がとても面白かったです。
「再帰」で起きていることが図形化して理解できました。
処理の中で処理が呼び出され、さらに呼び出されっていうことの繰り返しなんですね。
ありがとうございます。

Answer 4

「ディレクトリを再帰的に」の意味を意訳すると

「ディレクトリの中の中の中の中の～」と言った感じです。

１、ディレクトリの中(直下)のファイル・ディレクトリの一覧を取得
２、各ファイルorディレクトリに何らかの処理

と言った処理を行っている為、サブディレクトリも含める場合は１～２の処理を検出された子ディレクトリ毎に繰り返す（再帰する）形になります。

プログラム的に言えば、「とある関数Aの処理の中で自分自身(A)を呼び出す。」と言った形です。

大体ですがそんな感じです。

Comments

[fermat]

wikipediaの説明よりも「ディレクトリの中の中の中の中の～」の方が
直感的でわかりやすかったです。（wikipediaごめん）
ありがとうございます。

Answer 5

ファイル階層は再帰的なデータ構造の一つです。
再帰的データ扱うには、再帰的な方法を扱うのが適しています。

再帰は、いろいろなところに現れます。マトリョーシカ人形や、巻き貝の螺旋など。

Thinking Recursively with Java https://www.amazon.co.jp/dp/0471701467
や
ゲーデル、エッシャー、バッハ　https://www.amazon.co.jp/dp/4826901259
を読むとよいです。

アフリカのデザインに潜むフラクタル
https://www.ted.com/talks/ron_eglash_on_african_fractals/transcript?language=ja
も面白いかもしれません。(日本語字幕)

Comments

[fermat]

「再帰」って日本語にもともと無い概念らしいですね。
哲学なども含め、幅広く言葉の意味を知っておくことも大切と思いました。
ありがとうございます。