最終更新日：2026年7月31日
fe fe-technology algorithm programming
まず結論
再帰関数は、関数の中で自分自身を呼び出す関数です。
試験では、次の3点を確認します。
自分自身を呼び出す
→ 再帰関数
再帰を止める条件
→ 終了条件
引数が終了条件へ近づく
→ 正常に終了できる
再帰問題は、難しい公式を覚えるよりも、終了条件まで式を展開することが大切です。
直感的な説明
再帰は、階段を一段ずつ下りるイメージです。
5段目
↓
4段目
↓
3段目
↓
2段目
↓
1段目で停止
一番下まで進んだら、今度は結果を戻しながら計算します。
例えば、次の関数を考えます。
f(n):
n ≦ 1 なら 1を返す
それ以外なら n + f(n - 1) を返す
f(5)は次のように展開できます。
f(5)
= 5 + f(4)
= 5 + 4 + f(3)
= 5 + 4 + 3 + f(2)
= 5 + 4 + 3 + 2 + f(1)
= 5 + 4 + 3 + 2 + 1
= 15
定義・仕組み
再帰関数に必要な二つの部分
再帰関数には、基本的に次の二つが必要です。
終了条件
n ≦ 1 なら1を返す
これ以上、自分自身を呼び出さない条件です。
再帰処理
n + f(n - 1)
問題を少し小さくして、自分自身をもう一度呼び出します。
終了条件
→ 再帰を止める
再帰処理
→ 問題を小さくして続ける
呼出しと戻り値の流れ
再帰関数では、まず呼出しが深く進みます。
f(5)
→ f(4)
→ f(3)
→ f(2)
→ f(1)
f(1)で終了条件に到達すると、結果が逆向きに戻ります。
f(1) = 1
f(2) = 2 + 1 = 3
f(3) = 3 + 3 = 6
f(4) = 4 + 6 = 10
f(5) = 5 + 10 = 15
スタックとの関係
関数を呼び出すたびに、処理途中の情報がスタックへ積まれます。
f(5)を途中保存
↓
f(4)を途中保存
↓
f(3)を途中保存
↓
f(2)を途中保存
↓
f(1)で終了
終了後は、後から呼び出したものから先に戻ります。
f(1)
→ f(2)
→ f(3)
→ f(4)
→ f(5)
これはスタックの後入れ先出し（LIFO）という性質です。
この関数が求めているもの
次の再帰式は、1からnまでの合計を求めています。
f(n) = n + f(n - 1)
したがって、
f(n)
= n + (n - 1) + … + 2 + 1
です。
例えば、
f(5)
= 5 + 4 + 3 + 2 + 1
= 15
となります。
どんな場面で使う？
階乗
階乗は、再帰関数の代表例です。
n! = n × (n - 1)!
例えば、
5!
= 5 × 4 × 3 × 2 × 1
= 120
ただし、今回のような合計問題とは演算子が違います。
合計
→ n + f(n - 1)
階乗
→ n × f(n - 1)
木構造の探索
フォルダ階層や組織図のような、同じ構造が入れ子になったデータの探索に向いています。
親フォルダ
├ 子フォルダ
│ └ 孫フォルダ
└ 子フォルダ
各子要素に対して同じ処理を行うため、再帰で表現しやすくなります。
フィボナッチ数
フィボナッチ数も再帰で定義できます。
F(n) = F(n - 1) + F(n - 2)
ただし、同じ計算を何度も繰り返す単純な実装は非効率になりやすいため、実務では繰返し処理やメモ化を使うことがあります。
よくある誤解・混同
f(1)でも再帰呼出しを続ける
終了条件が、
n ≦ 1 なら1を返す
であれば、f(1)はその場で終了します。
f(1) = 1
であり、
f(1) = 1 + f(0)
ではありません。
終了条件を確認せずに計算する
再帰関数では、最初に終了条件を探します。
終了条件がどこか
引数がどう変化するか
終了条件へ近づいているか
この3点を確認しないと、展開をどこで止めるか分からなくなります。
合計と階乗を混同する
再帰式では、演算子を必ず確認します。
5 + 4 + 3 + 2 + 1
→ 合計15
5 × 4 × 3 × 2 × 1
→ 階乗120
+と×を読み違えないことが重要です。
再帰関数は必ず無限に続く？
終了条件があり、引数がその条件へ近づけば終了します。
正常な例：
f(n) = n + f(n - 1)
nが1ずつ小さくなるため、やがて終了条件へ到達します。
一方、次のような関数は終了しません。
f(n) = n + f(n)
引数が変わらないため、終了条件へ近づきません。
また、
f(n) = n + f(n + 1)
も、n ≦ 1という終了条件から遠ざかるため、無限再帰になります。
再帰と繰返し処理はまったく別の計算をする？
同じ処理を、再帰でもループでも表現できる場合があります。
再帰
→ 関数が自分自身を呼ぶ
繰返し
→ forやwhileで処理を繰り返す
再帰は構造を直感的に書きやすい一方、呼出しが深くなるとスタックを多く使います。
まとめ（試験直前用）
自分自身を呼ぶ
→ 再帰関数
再帰を止める
→ 終了条件
引数を小さくする
→ 終了条件へ近づける
f(5)
→ 5 + 4 + 3 + 2 + 1
→ 15
試験では、次の順で確認します。
- 終了条件を探す
- 引数の変化を確認する
- 終了条件まで式を展開する
- 最後に戻り値を計算する
判断表にすると次のとおりです。
| 確認するもの | 見るポイント |
|---|---|
| 終了条件 | どこで再帰が止まるか |
| 引数 | 終了条件へ近づいているか |
| 演算子 | 加算か乗算か |
| 呼出し順 | 深く進んでから逆順に戻る |
一言で覚えるなら、
再帰問題は、終了条件まで展開してから戻り値を計算する。