Haskellと再帰
「再帰は単なるループの代替ではなく、言語の評価モデルや型システムと深く結びついている」
この記事では、Haskellにおける再帰の本質というテーマでの入門を目指します。
再帰とは何か
— ループの代用品ではなく、言語の“計算の仕組み”そのもの —
多くの入門書ではこう説明されます。
「関数型言語ではループの代わりに再帰を使う」
これは間違いではありませんが、本質ではありません。
再帰は単なる文法上の代替ではなく、
その言語が“どうやって計算を進めるか”という根本構造に関わる概念
です。
理解の鍵は次の2点です。
- 評価モデル（Evaluation Model）
- 型システム（Type System）
まず直感 なぜ再帰が自然に出てくるのか
命令型言語のループはこういう発想です。
状態を更新し続ける
i = i + 1
しかし純粋関数型言語では、
- 値は変更できない（不変）
- 状態の「更新」という概念がない
そのため計算はこう考えます。
「次の状態」を“新しい値”として作る
これを関数の呼び出し連鎖で表現したものが再帰です。
f(state) = f(next_state)
ここまでは「ループの代わり」に見えます。しかしこれはまだ表面です。
評価モデルと再帰の関係
言語は「式を書き換える機械」
関数型言語（特にHaskell）は、
プログラム = 式の変形規則
というモデルで動きます。
これはラムダ計算という数学モデルに基づいています。
再帰とはこの「式変形」を続けられる仕組みです。
例
factorial 3
→ 3 * factorial 2
→ 3 * (2 * factorial 1)
→ 3 * (2 * (1 * factorial 0))
→ ...
これは「ループ」ではなく、
式が自己展開していく現象
です。
つまり再帰は、
評価（式の書き換え）が連鎖する構造
そのものなのです。
再帰と遅延評価（Haskell特有の重要点）
Haskellではすべての式は
必要になるまで評価されない（遅延評価）
このとき再帰は「反復」ではなく
“無限構造の定義”
にもなります。
ones = 1 : ones
これは「無限ループ」ではなく、
「必要になった分だけ展開される無限リスト」
です。
つまり再帰は、
| 言語 | 再帰の意味 |
|---|---|
| 命令型 | 繰り返し処理の代替 |
| 関数型（遅延） | 無限データや構造の定義方法 |
役割が根本的に違います。
型システムと再帰の関係
再帰は「データの形」と一致している
関数型言語ではデータ型も再帰的です。
data List a = Empty | Cons a (List a)
リストの定義自体が再帰です。
それに対応する関数も自然に再帰になります。
length Empty = 0
length (Cons _ xs) = 1 + length xs
これは偶然ではなく、
型の構造 ＝ 計算の構造
という関係があるからです。
これを 構造的再帰 と呼びます。
さらに深い話 停止性と型
型システムは「どんな計算が書けるか」を制御します。
- 再帰を自由に許す → 停止しないプログラムも書ける
- 再帰を制限する型理論（例：証明支援系） → 停止が保証される
つまり再帰は、
言語が“無限計算を許すかどうか”を決めるスイッチ
でもあります。
これはループの代替どころではなく、
言語の計算能力そのもの
に関わっています。
まとめ
| 観点 | 再帰の本当の意味 |
|---|---|
| 表面的理解 | ループの代わり |
| 評価モデル | 式の自己展開の仕組み |
| 遅延評価 | 無限構造の記述手段 |
| 型システム | データ構造と計算構造の一致 |
| 計算理論 | 言語が持つ計算能力の核心 |
結論
再帰とは、「繰り返し」ではなく「計算の自己定義構造」です。
だから関数型言語では再帰が特別扱いされるのではなく、言語の土台そのものとして存在しているのです。