最終更新日：2026年8月5日

fe technology algorithm recursion

まず結論

再帰関数とは、関数の中から同じ関数を呼び出し、問題を少しずつ小さくしながら解く方法です。

階乗を再帰関数で表すと、次の形になります。

n = 0 のとき
F(n) = 1

n > 0 のとき
F(n) = n × F(n−1)

科目Aでは、次の2点を確認します。

求めたい計算になっているか
＋
引数が終了条件へ近づいているか

階乗なら、掛け算をしながら n が1ずつ減る式を選びます。

直感的な説明

再帰関数は、大きな問題を「一つ小さい同じ問題」に置き換えて考える方法です。

例えば、5の階乗は次のように分けられます。

5!
= 5 × 4!

さらに、4の階乗も同じ形で分けられます。

4!
= 4 × 3!

この関係を続けると、次のようになります。

5!
= 5 × 4 × 3 × 2 × 1 × 0!

ここで、0! = 1 と決めておけば計算を止められます。

問題を一つ小さくする
↓
同じ関数を呼ぶ
↓
終了条件に到達したら止める

再帰関数では、同じ処理を繰り返すことよりも、必ず終了条件へ近づくことが重要です。

定義・仕組み

階乗とは

階乗は、1から自然数 n までの整数をすべて掛け合わせた値です。

n! = n × (n−1) × (n−2) × … × 2 × 1

例えば、5の階乗は次のとおりです。

5!
= 5 × 4 × 3 × 2 × 1
= 120

また、0の階乗は次のように定義されます。

0! = 1

再帰関数の二つの部分

再帰関数には、主に次の二つが必要です。

部分 役割
終了条件 再帰呼出しを止める
再帰処理 問題を小さくして同じ関数を呼ぶ

階乗では、次のように対応します。

F(0) = 1
→ 終了条件

F(n) = n × F(n−1)
→ 再帰処理

階乗の再帰式

階乗は、次の関係を持ちます。

n! = n × (n−1)!

F(n) が n! を表すと考えると、再帰式は次です。

F(n) = 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 × F(0)
= 5 × 4 × 3 × 2 × 1 × 1
= 120

引数が終了条件へ近づく必要がある

再帰関数が終了するには、呼び出すたびに引数が終了条件へ近づかなければなりません。

正しい例は次です。

F(5)
→ F(4)
→ F(3)
→ F(2)
→ F(1)
→ F(0)

一方、次のように同じ引数のまま呼び出すと終了できません。

F(5)
→ F(5)
→ F(5)
→ …

このような状態を無限再帰といいます。

Pythonで表すと

Pythonでは、次のように書けます。

def factorial(n: int) -> int:
    if n == 0:
        return 1
    return n * factorial(n - 1)

このコードでも、n == 0 が終了条件、factorial(n - 1) が再帰呼出しです。

科目Aでどう出る？

科目Aでは、再帰関数の空欄へ入る式を選ぶ問題や、再帰呼出しの結果を求める問題が出ます。

最初に引数を見る

まず、再帰呼出しの引数が変化しているか確認します。

F(n−1)
→ 終了条件へ近づく可能性がある

F(n)
→ 同じ呼出しを繰り返す

終了条件が n = 0 なら、n−1 のように値を小さくする式が有力です。

次に演算を見る

引数が正しく変化していても、目的の計算になっていなければ不正解です。

階乗なら、必要なのは掛け算です。

n + F(n−1)
→ 1からnまでの和に近い

n × F(n−1)
→ 階乗

したがって、次の順番で選択肢を確認します。

1. 引数が終了条件へ近づくか
2. 演算が目的に合っているか

小さい値で展開する

迷ったら、n = 3 などの小さい値を代入して確認します。

正しい式なら、次のようになります。

F(3)
= 3 × F(2)
= 3 × 2 × F(1)
= 3 × 2 × 1 × F(0)
= 6

式を数段だけ展開すると、終了するか、目的の値になるかを判断しやすくなります。

判断表

式の特徴 判断
F(n−1) を呼ぶ 終了条件へ近づく可能性がある
F(n) を呼ぶ 引数が変わらず無限再帰になりやすい
足し算を続ける 合計を求める処理になりやすい
掛け算を続ける 階乗に対応する
終了条件がない 再帰を止められない

科目Bでどう使う？

科目Bでは、再帰関数そのものを読んで、処理結果や呼出し順を考える場面があります。

呼出しを上から順に書く

例えば、次の処理を考えます。

F(4)
= 4 × F(3)
= 4 × 3 × F(2)
= 4 × 3 × 2 × F(1)
= 4 × 3 × 2 × 1 × F(0)

ここでは、先に F(0) まで呼び出してから、戻りながら掛け算します。

呼出し
F(4) → F(3) → F(2) → F(1) → F(0)

戻り
1 → 1 → 2 → 6 → 24

再帰処理では、呼び出す順番と戻る順番が逆になる点に注意します。

スタックとの関係

再帰関数を呼び出すたびに、途中の処理情報はスタックへ積まれます。

F(4)
F(3)
F(2)
F(1)
F(0)

終了条件へ到達すると、最後に呼び出した処理から順に戻ります。

後から入れたものを先に取り出す
→ LIFO

そのため、再帰の深さが大きすぎると、スタック領域を多く使うことがあります。

ループへ置き換える

階乗は、繰返し処理でも計算できます。

def factorial_loop(n: int) -> int:
    result = 1
    for value in range(1, n + 1):
        result *= value
    return result

再帰とループは、同じ結果を求められる場合があります。

方法 特徴
再帰 定義をそのまま表しやすい
ループ 呼出し回数やメモリ使用を抑えやすい

試験では、どちらが常に優れているかではなく、処理の流れを正しく追えることが重要です。

よくある誤解・混同

自分自身を呼べば正しい再帰関数になる

自分自身を呼ぶだけでは不十分です。

F(n) → F(n)

のように引数が変わらなければ、終了条件へ到達しません。

再帰呼出しでは、問題が確実に小さくなっているかを確認します。

引数が減れば必ず正解になる

引数が減れば再帰は終了しやすくなりますが、目的の計算になるとは限りません。

F(n) = n + F(n−1)

は終了しますが、階乗ではなく和を求める処理です。

終了するか
＋
目的の計算になるか

の両方を確認します。

F(0)=0だと思う

階乗では、0! = 1 です。

もし F(0)=0 にすると、掛け算の最後に0が掛かり、すべて0になります。

3 × 2 × 1 × 0 = 0

階乗の終了条件は 1 である点を押さえます。

呼出し順と計算順は同じ

再帰関数は、先に終了条件まで呼び出します。

その後、戻りながら計算します。

呼出し：大きい値 → 小さい値
戻り　：小さい値 → 大きい値

呼び出した直後に、すべての掛け算が完了するわけではありません。

再帰はループとは全く別の結果になる

再帰とループは書き方が異なりますが、同じ計算を表せることがあります。

階乗の場合、どちらも同じ値を求められます。

違いは、処理の表現方法やメモリの使い方です。

まとめ（試験直前用）

  • 再帰関数は、関数の中から同じ関数を呼び出す処理
  • 再帰には、終了条件と問題を小さくする処理が必要
  • 階乗の再帰式は、F(n) = n × F(n−1)
  • 階乗の終了条件は、F(0) = 1
  • F(n)を同じ引数のまま呼ぶ式は、無限再帰になりやすい
  • 選択肢は、引数が終了条件へ近づくか → 演算が目的に合うかの順で確認する
  • 迷ったら、小さい値を代入して数段だけ展開する

© 2024-2026 stemtazoo. All rights reserved.