0Pricing
Coding Interview Prep · レッスン

アンカー部と再帰部

再帰CTEの2つの部分構造と、終了条件が機能する仕組みを学びます。

「アンカー部と再帰部」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

再帰CTEが登場する理由

面接官が組織図、部品表、またはカテゴリーツリーを示し、すべての子孫を求めるよう質問した場合、再帰CTEを使おうとするかどうかを見ています。通常のJOINでは固定された階層数しかたどれませんが、再帰なら任意の深さをたどれます。

質問に含まれる手がかりとなる表現は、「任意の深さまで」や「一番下まで」です。これが合図になります。このレッスンでは、すべての再帰CTEに共通する2つの部分、アンカーメンバーと再帰メンバーから成る構造を学びます。

2つの部分から成る基本構造

再帰CTEには必ずキーワードWITH RECURSIVEが含まれます（Postgres、SQLite、MySQL 8+。SQL ServerではRECURSIVEを省略します）。本体は、UNION ALLで結合された2つのクエリから成ります。

  • アンカーメンバー — 開始行です。1回だけ実行されます。
  • 再帰メンバー — CTE自身の名前を参照し、繰り返し実行されます。

この基本構造を覚えておいてください。面接官は、何もない状態からこれを書かせる質問を好みます。

WITH RECURSIVE cte AS (
    -- anchor member
    SELECT ...
    UNION ALL
    -- recursive member
    SELECT ... FROM cte JOIN ...
)
SELECT * FROM cte;

アンカーメンバーの役割

アンカーメンバーは、CTEを参照しない通常のクエリです。シード行、つまりレベル0の開始点を生成します。組織図では通常、CEO（managerがNULLの行）が該当します。数列であれば、最初の数値です。

アンカーメンバーは正確に1回だけ実行されます。その出力が、再帰ステップに渡される最初の行の集合になります。

-- Anchor: the top of the hierarchy
SELECT id, name, manager_id, 1 AS depth
FROM employees
WHERE manager_id IS NULL

再帰メンバーの役割

再帰メンバーは、CTEを名前で参照します。各反復で、直前の反復によって生成された行を基底テーブルに結合し、次の階層を見つけます。

再帰メンバーが参照できるのは、そこまでに構築されたCTE全体ではありません。直前のステップで追加された行だけです。これは、面接官が確認したがる重要なメンタルモデルです。

-- Recursive: children of the rows found so far
SELECT e.id, e.name, e.manager_id, c.depth + 1
FROM employees e
JOIN cte c ON e.manager_id = c.id

全体を組み立てる

アンカーメンバーと再帰メンバーをUNION ALLで結合すると、エンジンが自動的に反復処理を行います。各回で次の階層が追加され、再帰メンバーが0行を返した時点で再帰が停止します。

以下は、depthも追跡する、完全かつ実行可能な組織図の探索例です。

WITH RECURSIVE org AS (
    SELECT id, name, manager_id, 1 AS depth
    FROM employees
    WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, o.depth + 1
    FROM employees e
    JOIN org o ON e.manager_id = o.id
)
SELECT id, name, depth FROM org ORDER BY depth, id;

終了条件の仕組み

再帰メンバーが新しい行を返さなくなったとき、再帰は停止します。明示的なループカウンターは必要ありません。ツリーの葉に到達すると、JOINは自然に行を返さなくなります。

組織図の例では、直属の部下がいない従業員に到達すると、次の反復のJOINで子が見つからず、空の結果が返されてエンジンが停止します。この自動的に終了する動作を理解しているかは、面接でよく追加質問されます。

UNION ALLとUNIONの違い

面接官は、なぜUNIONではなくUNION ALLを使うのか、よく質問します。理由は2つあります。

  • パフォーマンス — UNIONは反復のたびに重複排除を行うため、コストがかかります。
  • 正しさ — ツリーでは通常、重複行は発生しないため、重複排除は無駄な処理になります。

構造がグラフで、繰り返し現れるノードを意図的にまとめたい場合に限りUNIONを使います。ただし、サイクル対策には明示的なガードのほうが適しています（後で扱います）。

深さとパスを追跡する

2つの列を追加すると、再帰クエリの結果がさらに役立つものになります。面接でもよく求められます。

  • depth — アンカーでは1から始め、再帰メンバーで1を加えます。
  • path — IDや名前の連なりを蓄積し、ルートからノードまでの経路を確認できるようにします。

pathを文字列として構築すると、後でサイクル検出の手段としても利用できます。

WITH RECURSIVE org AS (
    SELECT id, name, manager_id, 1 AS depth,
           CAST(name AS VARCHAR(1000)) AS path
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, o.depth + 1,
           o.path || ' > ' || e.name
    FROM employees e JOIN org o ON e.manager_id = o.id
)
SELECT name, depth, path FROM org;

列の型を一致させる

見落としやすい注意点があります。アンカーメンバーと再帰メンバーは、同じ数の列を返し、互換性のある型を使用する必要があります。path文字列を作成する場合は、アンカーの初期値を十分に広い型（例：VARCHAR(1000)）にキャストしてください。そうしないと、後の反復でエンジンによって切り詰められたり、型不一致エラーが発生したりする可能性があります。

これは、再帰CTEについて読んだだけでなく、実際に実行した経験があるかを面接官が確認するために仕込む、まさにその種の細かなポイントです。

部品表の例

同じ基本構造で、部品表も処理できます。ある部品を指定して、任意の深さにあるすべてのサブ部品を一覧にします。アンカーでは最上位のアセンブリを選択し、再帰メンバーではparent_partからchild_partへの関連をたどります。

組織図の場合と構造がまったく同じで、変わるのは列名だけであることに注目してください。1つの基本構造を多くの問題に適用できると認識することが、面接で本当に求められるスキルです。

WITH RECURSIVE bom AS (
    SELECT child_part, parent_part, 1 AS lvl
    FROM parts WHERE parent_part = 'ENGINE'
    UNION ALL
    SELECT p.child_part, p.parent_part, b.lvl + 1
    FROM parts p JOIN bom b ON p.parent_part = b.child_part
)
SELECT child_part, lvl FROM bom;

方言ごとの注意点

面接官にも好印象を与えやすい、各方言の簡単なチートシートです。

  • PostgreSQL、SQLite、MySQL 8+：WITH RECURSIVE name AS (...)。
  • SQL Server：単にWITH name AS (...)と書きます。RECURSIVEキーワードは暗黙で、既定のMAXRECURSIONは100です。
  • Oracle：再帰CTEと、以前からあるCONNECT BY構文の両方をサポートしています。

「SQL ServerではRECURSIVEという単語を使わない」と言えると、幅広い知識を示せます。

クイックチェック

2つの部分から成る構造を理解できているか確認しましょう。

まとめ

これで再帰CTEの基本構造を身につけました。

  • WITH RECURSIVE + アンカー + UNION ALL + 再帰メンバー。
  • アンカーはレベル0の行を用意し、1回だけ実行されます。
  • 再帰メンバーは直前の反復結果を基底テーブルに結合し、行を返さなくなるまで実行されます。
  • UNION ALLを使い、depthとpathを追跡し、列の型に互換性を持たせます。

次は、この基本構造を実際の組織図に適用し、下方向と上方向にたどります。

よくある質問

「アンカー部と再帰部」レッスンは無料ですか？

はい。「アンカー部と再帰部」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「アンカー部と再帰部」で何を学びますか？

再帰CTEの2つの部分構造と、終了条件が機能する仕組みを学びます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。

「アンカー部と再帰部」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. アンカー部と再帰部
  2. 組織図をたどる
  3. 数値系列と日付系列を生成する
  4. 無限再帰を避ける
← Coding Interview Prepに戻る