再帰（Recursion）と末尾再帰（Tail Recursion）

関数型プログラミングにおける制御構造としての「再帰（Recursion）」と「末尾再帰（Tail Recursion）」は、反復（ループ）処理の代替手段として重要な役割を果たします。以下、それぞれについて詳しく説明します。

1. 再帰（Recursion）

概要

再帰とは、関数が自分自身を呼び出すことで問題を段階的に解決していく手法です。関数型プログラミングでは命令的なループ構造（forやwhileなど）を使わず、再帰によって繰り返し処理を実現します。

特徴

  • **終了条件（ベースケース）と再帰呼び出し（再帰ステップ）**の2つで構成されます。

  • 関数呼び出しごとにコールスタック（呼び出しスタック）が積み上がるため、深い再帰ではスタックオーバーフローのリスクがあります。

例（数値の階乗）

haskell
factorial n =
  if n == 0 then 1
  else n * factorial (n - 1)

この関数は n = 3 の場合、次のように再帰的に評価されます：

matlab
factorial(3)
→ 3 * factorial(2)
→ 3 * (2 * factorial(1))
→ 3 * (2 * (1 * factorial(0)))
→ 3 * (2 * (1 * 1)) = 6

2. 末尾再帰（Tail Recursion）

概要

末尾再帰とは、関数の最後の処理が再帰呼び出しのみである再帰の形式です。この形にすると、コンパイラやインタプリタがスタックフレームを再利用できるため、スタックオーバーフローを防ぐことができます。

この最適化を「末尾呼び出し最適化（Tail Call Optimization, TCO）」と呼びます。

特徴

  • メモリ効率が良く、大きな入力にも対応可能。

  • 明示的なループに匹敵する性能を持つ。

  • **アキュムレータ（累積引数）**を用いて状態を渡していくスタイルになる。

例（末尾再帰による階乗）

haskell
factorialTail n = go n 1
  where
    go n acc =
      if n == 0 then acc
      else go (n - 1) (n * acc)

評価の流れ（factorialTail 3）：

go
go 3 1 → go 2 3 → go 1 6 → go 0 6 → 6

各呼び出しは新しいスタックを積まないため、メモリ効率が良くなります。

3. 再帰と末尾再帰の比較

比較項目 通常の再帰 末尾再帰
スタック消費 呼び出しごとに増加 最適化があれば一定量で済む
実装の簡潔さ 直感的で分かりやすい 状態管理のため冗長になりやすい
パフォーマンス 入力が大きいと非効率 大規模入力でも安定して動作
最適化の必要性 基本的にそのまま実行 最適化（TCO）される言語で効果大

4. 末尾再帰をサポートする主な関数型言語

言語 末尾再帰最適化（TCO）のサポート状況
Haskell 原則としてサポート
Scheme 必須とされており標準サポート
OCaml 条件付きでサポート
Scala 明示的なアノテーションでサポート
F# 再帰関数に tailrec 属性が必要

まとめ

  • 再帰は関数型プログラミングにおける基本的な制御構造。

  • 末尾再帰は、再帰の効率を高めるための最適化手法であり、特に大規模な繰り返し処理で有効。

  • 言語によってサポート状況が異なるため、実装時にはTCOの有無に注意が必要です。

必要であれば、特定の言語における末尾再帰の実装例もご紹介できます。

生成日：2025/06/01