再帰

再帰とは

再帰 (Recursion) は、関数が自分自身を呼び出して問題を解く手法である。問題を同じ構造の小さな部分問題に分割し、基底条件 (Base Case) で再帰を停止する。

基本構造

再帰関数は「基底条件」(再帰を止める条件) と「再帰呼び出し」(自分自身を呼ぶ部分) の 2 つで構成される。呼び出しが起きるたびに引数と戻り先を持つフレームがコールスタックに積まれ、基底条件に到達したところから戻り値が逆順に畳み込まれていく。この「積んで、巻き戻す」動きが再帰の実体であり、基底条件を書き忘れると巻き戻る地点が来ないままフレームが積まれ続け、スタック領域を使い切って停止する。

function factorial(n: number): number {
  if (n <= 1) return 1;          // 基底条件
  return n * factorial(n - 1);   // 再帰呼び出し
}
// factorial(4) → 4 * factorial(3) → 4 * 3 * factorial(2) → 4 * 3 * 2 * 1 = 24
// 最も深いところで 4 フレームが同時にスタック上に存在する

再帰 vs ループ

同じ合計を再帰とループの両方で書くと、書き味の違いだけでなくコストの差が見える。

// 再帰: 先頭の 1 要素と「残りの配列の合計」に分解する
function sumRecursive(arr: number[]): number {
  if (arr.length === 0) return 0;
  return arr[0] + sumRecursive(arr.slice(1));
}

// ループ: 同じ結果を一定メモリで得る
function sumLoop(arr: number[]): number {
  let total = 0;
  for (const n of arr) total += n;
  return total;
}

再帰版には 2 つの落とし穴がある。要素数だけフレームが積まれること、そして slice(1) が毎回配列をコピーするため全体の計算量が O(n) ではなく O(n²) になることである。配列の合計のような線形処理は、再帰で書く利点よりこの代償が大きい。

観点	再帰	ループ
可読性	木構造に自然	線形処理に自然
メモリ	スタックを消費	一定
パフォーマンス	オーバーヘッドあり	高速

木構造の走査

木構造は再帰と相性が良い。各ノードに対して処理を行い、子ノードに対して同じ関数を再帰的に呼び出すことで、木全体を自然に走査できる。

type TreeNode = { value: number; children: TreeNode[] };

function sumTree(node: TreeNode): number {
  let total = node.value;
  for (const child of node.children) {
    total += sumTree(child); // 再帰で子ノードを走査
  }
  return total;
}

ファイルシステムの走査

ディレクトリはディレクトリを含む入れ子構造なので、「1 段分の処理」だけを書けば任意の深さに対応できる。下の例で書いているのは「要素を列挙し、ディレクトリなら自分を呼び、ファイルならパスを返す」という 1 段分だけである。

import { readdirSync, statSync } from 'fs';

function listFiles(dir: string): string[] {
  const entries = readdirSync(dir);
  return entries.flatMap(entry => {
    const path = `${dir}/${entry}`;
    return statSync(path).isDirectory() ? listFiles(path) : [path];
  });
}

スタックオーバーフロー

再帰の深さの上限は、言語仕様ではなく実行環境のスタック領域とフレームの大きさで決まる。固定値として覚えるのではなく、自分の環境で測るのが確実である。

// ❌ 基底条件がない → 無限再帰
function bad(n: number): number { return bad(n - 1); }
// RangeError: Maximum call stack size exceeded

// 深さを実測する: 引数もローカル変数もない最小の再帰で 1 万段前後
let depth = 0;
function probe(): void { depth++; probe(); }
try { probe(); } catch { console.log(depth); }

Node.js 26 でこの実測を行うと 1 万段強で RangeError: Maximum call stack size exceeded になる。引数やローカル変数が増えれば 1 フレームが太るため到達できる段数は減り、node --stack-size で領域を広げれば増える。CPython は逆に、スタックを使い切る前に自前の上限で止める設計で、既定値は sys.getrecursionlimit() で確認でき 1000 である (超過時は RecursionError)。

末尾呼び出し最適化の現況

末尾呼び出し最適化 (TCO) は、再帰呼び出しが関数の最後の処理であればフレームを積み替えずに再利用し、深さの制約をなくす仕組みである。下のように累算値を引数で持ち回る形が典型的な末尾再帰の書き方になる。

function factorialTail(n: number, acc = 1): number {
  if (n <= 1) return acc;
  return factorialTail(n - 1, n * acc);  // 戻り値をそのまま返す = 末尾呼び出し
}

ただし「末尾再帰に書き換えれば深い再帰が通る」とは限らない。ECMAScript 2015 は proper tail calls を仕様として規定したが、実装したのは WebKit の JavaScriptCore (2016 年に対応を公表) で、2026 年 8 月時点の V8 (Chrome / Node.js) は未実装であり、上の末尾再帰でも段数分のフレームを積んで RangeError に至る。Python も TCO を持たず、末尾再帰にしても RecursionError になる。深さが入力に比例して伸びるなら、ループか明示的なスタックへの書き換えが唯一確実な対策である。

再帰が適するケース

再帰が有利なのは、扱うデータ構造そのものが自分と同じ形を内側に含んでいる場合である。構造の再帰性とコードの再帰性が一致するため、1 段分の処理を書くだけで全体が処理できる。

ケース	例
木構造の走査	DOM、ファイルシステム、JSON
分割統治	マージソート、クイックソート
バックトラッキング	迷路、数独
フラクタル	再帰的な図形描画

再帰が不適なケース

逆に、構造が単に線形なだけの繰り返しを再帰で書くと、スタック消費と呼び出しオーバーヘッドの分だけ損になる。

ケース	代替
単純な繰り返し	for/while ループ
深さが入力に比例する処理	ループ、明示的なスタック
重複する部分問題	動的計画法 (メモ化)

理論と実装の両面から学ぶなら関連書籍が参考になる。