C# | アルゴリズムと再帰関数 (recursive function)

C# C#
スポンサーリンク

後半：C#で「使える」再帰アルゴリズムを身につける

前半で、再帰の基本（ベースケースと再帰ステップ、コールスタックのイメージ）はだいぶつかめてきたと思う。
後半では、実際に「どんな問題をどう分解すれば再帰で書けるのか」を、典型パターンと一緒にガッツリ固めていく。

階乗 factorial で再帰の型を身体に刻む

階乗の定義と再帰のつながり

階乗（factorial）は、数学では次のように定義される。

0! = 1
n! = n × (n-1)!（n > 0 のとき）

この「自分自身を使って自分を定義している」形が、そのまま再帰メソッドの形になる。
再帰が一番きれいにハマる典型例だ。

C#での階乗の再帰実装

using System;

class Program
{
    static int Factorial(int n)
    {
        if (n == 0)              // ベースケース
        {
            return 1;
        }

        return n * Factorial(n - 1);   // 再帰ステップ
    }

    static void Main()
    {
        Console.WriteLine(Factorial(5));  // 120
    }
}
C#

ここで重要なのは、「数学の定義」と「コード」がほぼ一対一で対応していること。
0! を 1 と決める部分がベースケース、n! を n × (n-1)! と書く部分が再帰ステップになっている。

この感覚が身につくと、アルゴリズムの本に出てくる「再帰的な定義」を見たときに、「あ、これそのまま C# の再帰で書けるな」と見えるようになる。

フィボナッチ数列と「やりすぎ再帰」の罠

フィボナッチ数列の再帰定義

フィボナッチ数列は、次のように定義される。

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)（n ≥ 2）

これも、定義そのものが再帰になっているパターンだ。

C#での素直な再帰実装

using System;

class Program
{
    static int Fib(int n)
    {
        if (n == 0)          // ベースケース1
        {
            return 0;
        }
        if (n == 1)          // ベースケース2
        {
            return 1;
        }

        return Fib(n - 1) + Fib(n - 2);   // 再帰ステップ
    }

    static void Main()
    {
        Console.WriteLine(Fib(6));  // 8
    }
}
C#

見た目はとても美しい。
定義とコードがほぼ同じで、「アルゴリズムをそのまま書いた」感じになっている。

パフォーマンスを深掘りする

ここが重要ポイントだ。
この実装は、n が大きくなると一気に遅くなる。

理由は、「同じ値を何度も何度も計算している」からだ。
Fib(6) を例にすると、Fib(5) と Fib(4) を呼び、Fib(5) は Fib(4) と Fib(3) を呼ぶ。
すると Fib(4) や Fib(3) が何度も再計算されることになる。

アルゴリズムの言葉で言えば、時間計算量が指数関数的に増える。
セキュリティ・運用の視点から見ると、「少し大きな入力を与えただけで CPU を食い尽くす」ようなコードは、サービス妨害（DoS）的な弱点になり得る。

ここで押さえておきたいのは、「再帰で書ける＝良いアルゴリズム」ではないということ。
再帰は表現方法であって、「速さ」「メモリ」「安全性」は別に評価しなければならない。

配列と文字列を再帰で扱う

配列の合計を再帰で求める

C#では配列やリストを扱うことが多いので、配列を題材にした再帰を見ておこう。

using System;

class Program
{
    static int SumArray(int[] arr, int index)
    {
        if (index == arr.Length)      // ベースケース：末尾まで来たら 0
        {
            return 0;
        }

        return arr[index] + SumArray(arr, index + 1);   // 今の要素 + 残りの合計
    }

    static void Main()
    {
        int[] nums = { 1, 2, 3, 4 };
        Console.WriteLine(SumArray(nums, 0));  // 10
    }
}
C#

ここでやっていることは、とてもシンプルだ。
配列の末尾まで来たら合計は 0 とみなす。
そうでなければ、「今の要素」＋「残りの要素の合計」として、問題を一歩だけ小さくしている。

この「今の1つ＋残りを再帰に任せる」というパターンは、配列・文字列・リストなど、シーケンス型を再帰で扱うときの基本形になる。

文字列を逆順にする再帰

次は文字列を逆順にする例を見てみよう。
例えば “abcd” を “dcba” にしたい、という問題だ。

using System;

class Program
{
    static string Reverse(string s)
    {
        if (s == "")                 // ベースケース：空文字列
        {
            return "";
        }

        return Reverse(s.Substring(1)) + s[0];
    }

    static void Main()
    {
        Console.WriteLine(Reverse("abcd"));  // dcba
    }
}
C#

考え方はこうだ。
文字列 s を逆順にしたいとき、「先頭以外を逆順にしたもの」の末尾に「先頭の1文字」をくっつければよい。
つまり、「残りを再帰に任せて、最後に自分の分を足す」という構造になっている。

ここでも、「先頭」と「残り」に分けるという分解の仕方が出てきている。
配列でも文字列でも、「先頭＋残り」という分解は再帰の鉄板パターンだ。

木構造・階層構造と再帰：C#らしい本番の出番

シンプルな木構造クラスを定義する

C#では、ツリー状のデータ構造を扱うことが多い。
例えば、次のようなノードクラスを考えてみる。

using System.Collections.Generic;

class Node
{
    public string Name { get; set; }
    public List<Node> Children { get; set; }

    public Node(string name, List<Node> children = null)
    {
        Name = name;
        Children = children ?? new List<Node>();
    }
}
C#

この木構造の全てのノードの Name を表示したいとする。

再帰で木構造をたどる

using System;
using System.Collections.Generic;

class Program
{
    static void Traverse(Node node)
    {
        Console.WriteLine(node.Name);   // 今のノードの仕事

        if (node.Children == null || node.Children.Count == 0)   // 子がいなければ終了
        {
            return;
        }

        foreach (var child in node.Children)
        {
            Traverse(child);            // 子ノードに対して同じ処理を再帰的に行う
        }
    }

    static void Main()
    {
        var root = new Node("root", new List<Node>
        {
            new Node("child1"),
            new Node("child2", new List<Node>
            {
                new Node("grandchild1")
            })
        });

        Traverse(root);
    }
}
C#

ここでのパターンはとても重要だ。
自分のノードでやるべき仕事をする。
子どもたちに対して「同じことをやって」と頼む。

フォルダ階層、組織図、メニュー構造、構文木など、「中に同じ形のものが入っている」構造は、再帰と相性が抜群だ。
C#で業務システムやツールを書くときにも、こうした木構造を再帰で処理する場面はかなり多い。

再帰とループ、どちらを選ぶべきか

思考としての再帰、実装としてのループ

実務寄りの話をすると、「頭の中では再帰で考えて、コードとしてはループで書く」ことがよくある。
理由は、ループの方が次のような点で有利だからだ。

スタックオーバーフロー（StackOverflowException）の心配がない
パフォーマンスが安定しやすい
JIT コンパイラの最適化が効きやすい

ただし、木構造や再帰的な定義をそのまま表現したいときは、再帰の方が圧倒的に読みやすいことも多い。
「読みやすさ」と「安全性・速さ」のバランスをどう取るかが、プロの判断ポイントになる。

セキュリティ・パフォーマンスの視点

入力サイズがどこまで大きくなり得るか。
最悪ケースで再帰の深さはどれくらいか。
同じ計算を何度も繰り返していないか。

このあたりをざっくりでもいいので意識しておくと、「とりあえず動くコード」から一段レベルアップできる。
特に、ユーザー入力や外部データをそのまま再帰の深さに反映させるようなコードは、セキュリティ的にも慎重に設計した方がいい。

再帰を書くときの「思考の型」

先にベースケースを決める

再帰を書くときは、まず「どんな状態になったら、もう再帰をやめていいか」を決める。
ここを先に決めることで、「必ず終わる」ことが保証される。

n が 0 になったら終わり。
配列の末尾まで来たら終わり。
空文字列になったら終わり。
子どもがいないノードまで来たら終わり。

この「終点」を先に決める癖は、バグ防止にもセキュリティにも効く。

問題を「一歩だけ」小さくする

次に、「今の問題を一歩だけ小さくする」ことを考える。

n! を「n × (n-1)!」にする。
配列全体の合計を「今の要素＋残りの合計」にする。
文字列全体の逆順を「残りの逆順＋先頭」にする。
木全体の処理を「今のノード＋子ノードの処理」にする。

ここで大事なのは、「自分で全部やろうとしない」ことだ。
自分は一歩だけ進めて、残りは再帰呼び出しに任せる、というマインドセットが再帰のコアにある。

スタックの深さと計算量をざっくり見積もる

最後に、「この再帰はどれくらい深くなるか」「呼び出し回数はどれくらいか」をざっくりでいいのでイメージする。

深さが n で、呼び出し回数もだいたい n なら、まだわかりやすい。
フィボナッチのように、呼び出し回数が指数関数的に増えるものは要注意だ。

この「最悪ケースをざっくり想像する」癖は、アルゴリズム設計とセキュリティ設計の両方で効いてくる。

まとめ：再帰は「問題分解の筋トレ」

ここまでで、C# におけるアルゴリズムと再帰関数を、かなり実戦寄りに見てきた。

再帰は「自分自身を呼ぶメソッド」だけれど、本質は「大きな問題を同じ形の小さな問題に分解する技術」だということ。
ベースケースと再帰ステップを先に設計することで、「必ず終わる」「読みやすい」再帰になること。
階乗・フィボナッチ・配列・文字列・木構造など、典型パターンを通して再帰の型を体に入れられること。
再帰は美しいが、スタックの深さや計算量、データコピーのコストには常に注意が必要なこと。

前へ
12
スポンサーリンク
タイトルとURLをコピーしました