関数（メソッド）が、自分自身を呼び出すことを「再帰呼び出し」といいます。ディレクトリの一覧を取得するときなどに重宝します。

// 指定したディレクトリを再帰的に表示
[STAThread]
static void Main(string[] args) {
 if (args.Length == 0) {
  Console.WriteLine("ディレクトリを指定してください。");
 } else {
  OutputDirectory(args[0], 0);
 }
}
static void OutputDirectory(string directoryName, int depth) {
 if (Directory.Exists(directoryName) == false) {
  return;
 }
 DirectoryInfo dir = new DirectoryInfo(directoryName);
 PrintLeader(depth);
 Console.WriteLine("-{0}",dir.Name);
 DirectoryInfo[] dirInfo = dir.GetDirectories();
 foreach (DirectoryInfo item in dirInfo) {
  OutputDirectory(item.FullName, depth + 1);
 }
 FileInfo[] fileInfo = dir.GetFiles();
 foreach (FileInfo item in fileInfo) {
  PrintLeader(depth + 1);
  Console.WriteLine(item.Name);
 }
}
static void PrintLeader(int depth) {
 for (int level = 0; level < depth; level++) {
  Console.Write("｜");
 }
}

// 実行結果
D:\DataFolder\Projects\TestSolution\tree\bin\Debug>tree ..\..
-tree
｜-bin
｜｜-Debug
｜｜｜tree.exe
｜｜｜tree.pdb
｜-obj
｜｜-Debug
｜｜｜-temp
｜｜｜-TempPE
｜｜｜tree.exe
｜｜｜tree.pdb
｜｜｜tree.projdata
｜App.ico
｜AssemblyInfo.cs
｜Tree.cs
｜tree.csproj
｜tree.csproj.user

このプログラムの考え方の一例を示します。

指定されたディレクトリに存在する、ディレクトリの一覧を取得します。取得したディレクトリ一覧について、それぞれのディレクトリでまた存在するディレクトリの一覧を取得します。ディレクトリ内にディレクトリが存在しなければ、ファイルの一覧を取得し、表示します。そして、上のレベルへ制御を戻します。

ところが、この方法は少し注意が必要です。

ここの例では C# でコードを作っていますが、コンピュータは C# を理解できません。そこで、コンピュータにわかる言語にコンパイルします。C# の場合、コンパイルした結果は CL という言語になりますが、この言語を直接実行することは出来ません。実行時に、ngen.exe というツールでもう一度、今度はネイティブ（コンピュータが直接理解できる言語）にコンパイルされます。

ネイティブ言語、すなわち CPU が理解できる言語を実行するとき、“プログラム ポインタ”（または、プログラム カウンタ）というレジスタがあり、このポインタで、次に実行するべき命令の位置を示します。関数呼び出しを行うと、このプログラム ポインタの現在の値（および、他のレジスタの現在値）をスタックへ積み、呼び出される関数のアドレスで上書きします。そして、関数の実行が終わったら、プログラム ポインタの値をスタックから取り出し、元の処理を続けます。

関数の呼び出しが多くなって、スタックする領域がなくなると、「スタック オーバーフロー」という実行時エラーが発生することになります。

反対に考えると、「スタック オーバーフロー」が発生したら、どこかで関数呼び出しがループしていると考えられます（あるいは、単に深すぎる）。このエラーは次のようなプロパティ設定をすると、簡単に発生させることが出来ます。

// スタック オーバーフローが発生する例
private int someValue;
public int SomeValue {
    get { return SomeValue; } // 大文字と小文字を間違えた！！
}
// SomeValue プロパティへのアクセスは、SomeValue プロパティを呼び出すため、無限再帰する。

このように再帰呼び出しは、ある処理をするためには必要なのですが、プログラム ポインタのスタック領域という、比較的小さなエリアの大きさによって制限されます。また、CPU の実行レベルで考えても、レジスタ群のスタックやプログラム ポインタの書き換えは、コストがかかる方法です。

そこで、再帰呼び出しと同じ結果を、別の方法で実現します。

こういう時に用いるのが、System.Collections.Stack クラス／System.Collection.Queue クラスです。スタックは、後入れ先出し（LIFO）の記憶領域を提供してくれます。キューは、先入れ先出し（FIFO）の記憶領域を提供してくれます。

どうするかというと、もう一度コードを見ます。ここで、再帰呼び出しをしているのは、foreach ブロックの中です。このループで、再帰呼び出しをしているところで、ループ内で使っている変数のスナップ ショットをとり、そのスナップ ショットをスタックに待避、新しい値で変数を上書きして処理をやり直せば、再帰処理をしているのと同じ動きをすることになります。

・・・面倒です。

なので、使いません。（おい）

ケース バイ ケース。ものは使いようなのです。

このコードでは、ディレクトリ構造を表示しました。表示するためには、今表示している内容がなんなのか、覚えておかなければなりません。覚えておかなければならないものがあるため、自分で覚えておかなければならないものを待避させなければならない場合は、再帰の方が楽です。

しかし、「ディレクトリ中のすべてのファイルを、{アタッチしたい | 更新日付が知りたい | フルパス名が知りたい}」という場合、ファイルにアクセスする順番は関係ありません。順番が関係ないなら、覚えておくものはありません。こういう場合、再帰呼び出しよりも低コストなので、使います。

// Main を少し変更
static void Main(string[] args) {
    if (args.Length == 0) {
        Console.WriteLine("ディレクトリを指定してください。");
    }
    else {
        DateTime start = DateTime.Now;
        OutputDirectory(args[0], 0);
        DateTime t1 = DateTime.Now;
        Console.WriteLine("----------");
        OutputDirectory(args[0]);
        DateTime t2 = DateTime.Now;
        Console.WriteLine("{0} / {1}", t1.Subtract(start), t2.Subtract(t1));
    }
}
// 指定したディレクトリ以下のフルパス名を表示
static void OutputDirectory(string directoryName) {
    // Queue に、次に列挙したいディレクトリを放り込むことにする
    System.Collections.Queue q = new System.Collections.Queue();
    DirectoryInfo dir = new DirectoryInfo(directoryName);
    // 初回が回るように、トップを放り込む
    q.Enqueue(dir);
    while (q.Count > 0) {
        // キューから取り出して、書く
        DirectoryInfo info = q.Dequeue() as DirectoryInfo;
        Console.WriteLine(info.FullName);
        // ディレクトリ内のディレクトリを、キューに放り込む
        DirectoryInfo[] dirs = info.GetDirectories();
        foreach (DirectoryInfo item in dirs) {
            q.Enqueue(item);
        }
        FileInfo[] files = info.GetFiles();
        foreach (FileInfo item in files) {
            Console.WriteLine(item.FullName);
        }
    }
}

// 実行結果
-tree
｜-bin
｜｜-Debug
｜｜｜tree.exe
｜｜｜tree.pdb
｜-obj
｜｜-Debug
｜｜｜-temp
｜｜｜-TempPE
｜｜｜tree.exe
｜｜｜tree.pdb
｜｜｜tree.projdata
｜App.ico
｜AssemblyInfo.cs
｜tree.cs
｜tree.csproj
｜tree.csproj.user
----------
D:\Visual Studio Projects\TestSolution\tree
D:\Visual Studio Projects\TestSolution\tree\App.ico
D:\Visual Studio Projects\TestSolution\tree\AssemblyInfo.cs
D:\Visual Studio Projects\TestSolution\tree\tree.cs
D:\Visual Studio Projects\TestSolution\tree\tree.csproj
D:\Visual Studio Projects\TestSolution\tree\tree.csproj.user
D:\Visual Studio Projects\TestSolution\tree\bin
D:\Visual Studio Projects\TestSolution\tree\obj
D:\Visual Studio Projects\TestSolution\tree\bin\Debug
D:\Visual Studio Projects\TestSolution\tree\bin\Debug\tree.exe
D:\Visual Studio Projects\TestSolution\tree\bin\Debug\tree.pdb
D:\Visual Studio Projects\TestSolution\tree\obj\Debug
D:\Visual Studio Projects\TestSolution\tree\obj\Debug\tree.exe
D:\Visual Studio Projects\TestSolution\tree\obj\Debug\tree.pdb
D:\Visual Studio Projects\TestSolution\tree\obj\Debug\tree.projdata
D:\Visual Studio Projects\TestSolution\tree\obj\Debug\temp
D:\Visual Studio Projects\TestSolution\tree\obj\Debug\TempPE
00:00:00.0312500 / 00:00:00.0781250

表示されている順番を見ると、再帰の例のように、ツリー表示には向かないことがわかると思います。何度かトライして、できなかったというわけでは、断じてあります。

しかし。。。実際に実行してみると、再帰処理の方が速かったorz...

K&R 本あたりに、関数を呼び出すことによる、プログラム ポインタの書き換えと、ローカル変数の待避、および再生成のオーバー ヘッドの方が大きい、と書いてあったと思うんだけど。すると・・・キューやスタックを使うメリットがない？？？