関数や手続きを定義する際に、プログラムの本体で自分自身の呼出しを含む場合、
再帰定義（recursive definition）という。
また、プログラムの本体で自分自身を呼出すことを再帰呼出し（recursive call）という。
複雑な繰り返しをする場合、簡単に定義することができる。
── 元資料 3 枚目
すでに再帰的な定義には出会っています。第 10 章のフィボナッチ数列です。
第 10 章では、これを繰り返しに書き直して計算しました。 この章では定義のまま書きます。
再帰には、必ず 2 つのものが要ります。
どちらかを忘れると永久に呼び続けます。
第 8 章 §5.3 で「毎回かならず小さくなる量を探す」と言ったのは、
まさにこの確認のことです。
※ この教材の処理系は 400 段で打ち切ります。本物の Excel では
「スタック領域が不足しています」というエラーになります。
Sub Macro1()
Cells(1, 1) = "これから呼びます"
Call owaranai(5)
Cells(2, 1) = "ここには来ません"
End Sub
Sub owaranai(ByVal n As Integer)
' 終了条件がない！
Call owaranai(n - 1)
End Sub
元資料 4・5 枚目の対比です。1 行の位置を変えるだけで、出力の順序が逆になります。
Dim gyou As Integer ' どちらの Sub からも見える（第 10 章 §4）
Dim gyou2 As Integer
Sub Macro2()
Cells(1, 1) = "呼ぶ前に表示"
Cells(1, 3) = "呼んだ後に表示"
gyou = 2
Call mae(5)
gyou2 = 2
Call ato(5)
End Sub
' 自分を呼ぶ「前」に書く
Sub mae(ByVal n As Integer)
If n = 0 Then Exit Sub
Cells(gyou, 1) = n ' ← ここ
gyou = gyou + 1
Call mae(n - 1)
End Sub
' 自分を呼ぶ「後」に書く
Sub ato(ByVal n As Integer)
If n = 0 Then Exit Sub
Call ato(n - 1)
Cells(gyou2, 3) = n ' ← ここ
gyou2 = gyou2 + 1
End Sub
左は 5, 4, 3, 2, 1、右は 1, 2, 3, 4, 5 になります。 なぜでしょうか。呼び出しは「積み上がる」のです。
ato は先に自分を呼ぶので、
n=5 → 4 → 3 → 2 → 1 → 0 まで一気に潜っていきます。
そして 0 で Exit Sub して戻ってくるとき、
いちばん深いところ（n=1）から順に表示されます。
だから 1, 2, 3, 4, 5 の順になるのです。
この「積み上がって、あとから戻る」構造をスタックといいます。 再帰は、スタックを自動で使う繰り返しだと言えます ── だから深くなりすぎると「スタック領域が不足」になるのです。
第 5 章では GoTo で、第 7 章では For で書きました。
再帰ならこう定義できます ──
「1〜N の和は、N ＋（1〜N−1 の和）」。
Sub Macro3()
Dim n As Integer
For n = 1 To 8
Cells(n, 1) = n
Cells(n, 2) = wa(n)
Next n
Cells(10, 1) = "wa(100)"
Cells(10, 2) = wa(100)
End Sub
Function wa(ByVal n As Integer) As Long
If n = 1 Then ' 終了条件
wa = 1
Else
wa = n + wa(n - 1) ' 自分を呼ぶ（引数は必ず小さくなる）
End If
End Function
定義がそのままプログラムになっています。
For 版と比べてみてください ──
繰り返し版は「どう計算するか」の手順を書きますが、
再帰版は「何であるか」を書いています。
問題の定義が再帰的なら、再帰で書くほうが素直なのです。
元資料は「複雑な繰り返しを簡単に定義できる」と書いていますが、 簡単に書けることと、速いことは別です。 フィボナッチを定義のまま書くと、とんでもなく遅くなります。 これは触れておくべき重要な点なので、節を立てます。
Dim yobi As Long ' 呼び出された回数を数える
Sub Macro4()
Dim n As Integer
Cells(1, 1) = "n": Cells(1, 2) = "fib(n)": Cells(1, 3) = "呼び出し回数"
For n = 1 To 24
yobi = 0
Cells(n + 1, 1) = n
Cells(n + 1, 2) = fib(n)
Cells(n + 1, 3) = yobi
Next n
End Sub
Function fib(ByVal n As Integer) As Long
yobi = yobi + 1
If n <= 2 Then
fib = 1
Else
fib = fib(n - 1) + fib(n - 2)
End If
End Function
| n | fib(n) | 再帰版の呼び出し回数 | 繰り返し版（第 10 章） |
|---|---|---|---|
| 5 | 5 | 9 | 1 |
| 10 | 55 | 109 | 1 |
| 20 | 6,765 | 13,529 | 1 |
| 24 | 46,368 | 92,735 | 1 |
| 40 | 102,334,155 | 約 2 億回 | 1 |
なぜこんなに増えるのか。 fib(24) を求めるのに fib(23) と fib(22) を呼びますが、 fib(23) の中でも fib(22) を呼びます ── 同じものを何度も計算しなおしているのです。 fib(20) は fib(24) の計算中に 5 回も呼ばれます。 呼び出し回数は 2 × fib(n) − 1 で、 fib 自体が指数的に増えるので、呼び出し回数も指数的に増えます。
だから、再帰で書くべきかどうかは考えて決めます。 ハノイの塔（§5）や迷路（§6）は再帰でしか素直に書けませんが、 フィボナッチや階乗は繰り返しのほうが速いのです。 判断の目安は「同じ計算を何度もしていないか」です （答えを覚えておく「メモ化」という工夫で再帰版も速くできますが、それは先の話です）。
① にある円盤（N 個）を、③ に移すことを考える。
・一度に、一つの円盤しか動かすことができない。
・小さい円盤の上に、大きな円盤を乗せることはできない。
手続きの意味（元資料 18 枚目）
hanoi(n, a, b, c) ──
N 個の円盤を変数 a の値にある棒から、変数 b の値の棒へ移す。
変数 c の値の棒は補助となる棒である。
解き方の発想。 n 枚をいきなり動かす方法は思いつきませんが、 「n−1 枚を動かす方法は分かっている」と仮定すれば、3 段で書けます。
①と③は「n−1 枚を動かす」という同じ問題の小さい版です。 だから自分を呼べばよい ── これが再帰の考え方の核心です。 「全部の手順を考える」のではなく「1 段だけ考えて、残りは自分に任せる」。
Dim cnt As Integer
Sub Macro5()
Dim n As Integer
n = Cells(1, 5).Value
cnt = 0
Cells(1, 1) = "手": Cells(1, 2) = "円盤": Cells(1, 3) = "動かす"
Call hanoi(n, 1, 3, 2) ' ① から ③ へ、② を補助に
Cells(1, 6) = "手数"
Cells(2, 6) = cnt
Cells(3, 6) = "2^n - 1 ="
Cells(4, 6) = 2 ^ n - 1
End Sub
Sub hanoi(ByVal n As Integer, ByVal a As Integer, ByVal b As Integer, ByVal c As Integer)
If n = 0 Then Exit Sub ' 終了条件
Call hanoi(n - 1, a, c, b) ' ① 上の n-1 枚を補助の c へ
cnt = cnt + 1
If cnt <= 15 Then ' 表は 15 手までにしておく
Cells(cnt + 1, 1) = cnt
Cells(cnt + 1, 2) = n
Cells(cnt + 1, 3) = a & " ⇒ " & b
End If
Call hanoi(n - 1, c, b, a) ' ③ c の n-1 枚を b へ
End Sub
3 枚のとき 7 手、4 枚で 15 手、n 枚で 2n − 1 手です。 手数は1 枚増えるごとに倍以上になります（第 8 章の倍々貯金と同じ増え方）。 伝説では 64 枚だそうですが、264−1 ≒ 1844 京手。 1 秒に 1 枚動かしても5800 億年かかります。
3 枚のときに hanoi がどう呼ばれるかを書き出したものです。
元資料 20 枚目の図と、手順の番号（①〜⑤）まで一致します。
木の葉に近いところから順に手が確定していくことに注目してください。 いちばん大きい円盤（④）は、ちょうど真ん中で 1 回だけ動きます。 そして前半と後半は同じ形の小さい問題になっています ── これが再帰の構造がそのまま見える形です。
迷路をスタート地点からゴール地点に最短で移動する経路を列挙するプログラムを考える。
■ は壁であり、進むことができない。最短で移動するために、右と下にのみ移動できる。
「右と下だけ」という条件が効いています。 右か下にしか進めないので、同じ場所に戻ってくることがありません。 だから「行き止まりで引き返す」処理を書かなくても、素直な再帰で全部の経路を数えられます。 （左や上にも動けるなら「来た道を覚えておく」必要が出て、ぐっと難しくなります。）
左上（S）から右下（G）へ、右と下だけで進みます。 マスをクリックすると壁（黒）になります。
Dim kazu As Integer
Dim W As Integer
Dim H As Integer
Sub Macro6()
W = 6: H = 6 ' 迷路の大きさ
kazu = 0
Call susumu(1, 1) ' 左上から出発
Cells(8, 1) = "経路の数"
Cells(8, 2) = kazu
Cells(9, 1) = "壁がなければ"
Cells(9, 2) = 252 ' 10C5 = 252 通り
End Sub
Sub susumu(ByVal r As Integer, ByVal c As Integer)
' 外へ出たら行き止まり
If r > H Or c > W Then Exit Sub
' 壁なら行き止まり
If Cells(r, c).Value = "■" Then Exit Sub
' ゴールに着いたら 1 通り数える
If r = H And c = W Then
kazu = kazu + 1
Exit Sub
End If
Call susumu(r, c + 1) ' 右へ進む場合
Call susumu(r + 1, c) ' 下へ進む場合
End Sub
この手続きは 3 つの終了条件を持っています。
「外へ出た」「壁だった」「ゴールに着いた」──
再帰では、終了条件が複数あることがふつうです。
そして本体は 右へ と 下へ の 2 行だけ。
「その場で 2 通りに分かれる」ことだけ書けば、
残りは自分自身が処理してくれるのです。
壁がない 6×6 なら 252 通りです （右 5 回と下 5 回の並べ方＝10 個から 5 個選ぶ組み合わせ ＝ 252）。 上の配置（壁 4 つ）では 30 通りに減ります。 壁の位置を変えて、数がどう変わるか試してみてください ── 真ん中の壁ほどよく効きます。
再帰は「慣れ」で書くものではなく、決まった型があります。
| 問題 | 向いているのは | 理由 |
|---|---|---|
| 1〜N の和、階乗 | 繰り返し | 1 本道なので再帰の利点がない |
| フィボナッチ | 繰り返し | 再帰だと同じ計算を大量に繰り返す |
| ハノイの塔 | 再帰 | 問題が 2 つの小さい同じ問題に分かれる |
| 迷路の経路の列挙 | 再帰 | 分岐が枝分かれし、深さが決まらない |
| フォルダの中を全部たどる | 再帰 | 入れ子の深さが分からない（第 1 章のファイルシステム） |
| 図形の中に同じ図形（第 15 章） | 再帰 | 定義そのものが再帰的 |
もとにしたのは「情報学入門（VBA）185-2025」全 23 枚 （および同内容の 180-2019・23 枚）です。
| 元資料 | この教材 | 種別 |
|---|---|---|
Sub hanoi(n As Intger, a As Integer, b As Integer, c As Integer) |
Integer の綴り誤り。VBA では
「ユーザー定義型は定義されていません」というコンパイルエラーになり実行できない | 誤り |
| 「複雑な繰り返しをする場合、簡単に定義することができる」とあるが、 再帰が遅くなる場合に触れていない | §4 として追加。fib(24) で 92,735 回呼ばれることを実際に数えて示し、 再帰が向く問題と向かない問題を表にした | 不足 |
| 終了条件の必要性が明示されていない | 「終了条件」と「必ず小さくなること」の 2 つを要件として立て、 忘れたときに何が起きるかを実行して見せた | 不足 |
| 「呼び出す前に表示／呼び出した後に表示」の 2 例があるが、 なぜ順序が逆になるかの説明がない | スタックの図を添えて、 深く潜ってから戻るときに表示されることを説明した | 不足 |
| 迷路で「右と下にのみ移動できる」という条件の意味が書かれていない | この条件のおかげで同じ場所に戻らないので、 引き返す処理が不要になることを明示。壁なしなら 252 通り（10 個から 5 個選ぶ組み合わせ）も追記 | 不足 |
| ハノイの塔の手数に触れていない | 2n − 1 手。64 枚なら 1 秒 1 手で 5800 億年 | 不足 |
| 資料 180（23 枚）と 185（23 枚）がほぼ同内容で 2 本ある | 185（2025 年版）を採り、1 つの章にまとめた | 重複 |
元資料で正しかったこと。
再帰定義・再帰呼出しの定義文、
hanoi(n, a, b, c) の意味づけ（a から b へ移す、c は補助）、
20 枚目の呼び出しの木と手順の番号（①1を1⇒3、②2を1⇒2、③1を3⇒2、④3を1⇒3、⑤1を2⇒1）は
この教材のプログラムを実行した結果と完全に一致しました。
ハノイの塔の 3 つの規則、迷路の課題設定（右と下のみ）も適切です。
とくに「呼び出す前／呼び出した後」を並べて見せる構成は、
再帰を理解するうえで的確な導入です。