特定ディレクトリ以下の列挙 (再帰呼び出しとループ)

例えば、あるディレクトリ以下のファイル名を取得したい場合の再帰のみ使ったもの、ループのみ使ったもの、両方使ったもののどれが一番分かりやすいか。
まずは自分ならどう書くかを形にした上で続きを読むといいのかな。
あ、サンプルは Java です。

両方

一番初めに思いついたのがこれ。

public List<String> getAllChildren(File dir) {
    List<String> result = new ArrayList<String>();
    // ループと
    for (File f : dir.listFiles()) {
        if (f.isDirectory()) {
            // 再帰
            result.addAll(getAllChildren(f));
        } else if (f.isFile()) {
            result.add(f.getName());
        }
    }
    return result;
}

再帰するごとに ArrayList を生成するため、ディレクトリが多いと効率がよくない。
ディレクトリが少なくても第一階層以降のファイルが多いと、2 回 add する必要があるため効率がよくない。

再帰だけ

addAllChildren と addAllChildrenImpl で相互再帰になっちゃってるから、ちょっと分かりにくいかも。

private void addAllChildrenImpl(File file, List<String> tmp) {
    if (file.isFile()) {
        tmp.add(file.getName());
    } else if (file.isDirectory()) {
        // 相互再帰
        addAllChildren(new LinkedList<File>(Arrays.asList(file.listFiles())), tmp);
    }
}

private void addAllChildren(Queue<File> files, List<String> tmp) {
    if (files.isEmpty()) return;
    
    // 相互再帰
    addAllChildrenImpl(files.poll(), tmp);
    // 再帰
    addAllChildren(files, tmp);
}

public List<String> getAllChildren(File dir) {
    List<String> result = new ArrayList<String>();
    addAllChildren(new LinkedList<File>(Arrays.asList(dir.listFiles())), result);
    return result;
}

addAllChildrenImpl にディレクトリを渡すと配列をリストに変換した上で LinkedList を生成するので、ディレクトリが多い場合は効率が悪い。
ただし、ディレクトリが少ない場合は最初に生成した ArrayList に突っ込んでいくので効率がいい。

ループだけ

分かりやすいといえば分かりやすい。

public List<String> getAllChildren(File dir) {
    List<String> result = new ArrayList<String>();
    LinkedList<File> remains = new LinkedList<File>(Arrays.asList(dir.listFiles()));
    // ループ
    while (!remains.isEmpty()) {
        File f = remains.pollFirst();
        if (f.isDirectory()) {
            remains.addAll(0, Arrays.asList(f.listFiles()));
        } else {
            result.add(f.getName());
        }
    }
    return result;
}

途中で何も生成していないので、多分一番効率はいいかな？
最初は Deque 使ってディレクトリだったら拡張 for で remains.offerFirst してたけど、面倒なので LinkedList にして addAll するように変更。

結果が他の 2 つと異なってもいいのなら、LinkedList をやめて ArrayList とかにして、 addAll(Collection c) を使えばもっと効率はよくなるかも。

個人的意見

個人的には、混在バージョンが一番読みやすく書きやすいと思うんだけど、そこは人にもよるし言語にもよるだろうな。
「自分ならもっとうまく書ける！」ってのもあるだろうし。
えぇ、どうせ「かなりプログラミングができない」人ですよ。

ちなみに

この記事中に出てくる「効率」と、通常の再帰とループの比較で出てくる「効率」は別物ですので注意してくださいね。
再帰呼出しがループに比べて効率が悪いとか言う場合の効率は、関数呼出しの実装による効率の悪さをさしています。
詳しくは面倒なので、「再帰スタック」あたりをぐぐればいいと思います(何
「末尾再帰」とか「末尾最適化」で幸せになれる言語・実装もあります。