再帰

再帰とは

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

基本構造

再帰関数は「基底条件」(再帰を止める条件) と「再帰呼び出し」(自分自身を呼ぶ部分) の 2 つで構成される。基底条件がないと無限ループに陥るため、必ず再帰が収束する条件を定義する。

  if (n <= 1) return 1;          // 基底条件
  return n * factorial(n - 1);    // 再帰呼び出し
}
// factorial(4) → 4 * factorial(3) → 4 * 3 * factorial(2) → 4 * 3 * 2 * 1

再帰 vs ループ

再帰と ループ のコード例を比較する。

// 再帰
function sum(arr: number[]): number {
  if (arr.length === 0) return 0;
  return arr[0] + sum(arr.slice(1));
}

// ループ (同じ結果)
function sum(arr: number[]): number {
  let total = 0;
  for (const n of arr) total += n;
  return total;
}

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

木構造の走査

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

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;
}

ファイルシステムの走査

ファイルシステムの走査のコード例を示す。

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

// ✅ 末尾再帰 (一部の環境で最適化)
function factorial(n: number, acc = 1): number {
  if (n <= 1) return acc;
  return factorial(n - 1, n * acc);
}

再帰が適するケース

再帰が適するケースを以下に示す。

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

再帰が不適なケース

再帰が不適なケースを以下に示す。

ケース	代替
単純な繰り返し	for/while ループ
深い再帰 (> 10,000)	ループに変換
重複する部分問題	動的計画法 (メモ化)

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