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

fe fe-technology algorithm data-structure

まず結論

再帰処理とは、関数の中から自分自身を呼び出す処理です。

基本情報技術者試験では、再帰そのものの定義よりも、「再帰呼び出しの前」と「再帰呼び出しの後」で処理されるタイミングが違うことを理解しているかが重要です。

再帰呼び出しより前の処理 → 奥へ進むときに実行
再帰呼び出し             → さらに奥へ進む
再帰呼び出しより後の処理 → 戻ってくるときに実行

この「行き」と「戻り」を分けて考えるのが最大のポイントです。

直感的な説明

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

function f() {
    行きの処理
    f()
    戻りの処理
}

途中で再び f() を呼ぶので、現在の処理はいったん止まり、さらに奥へ進みます。

1回目 f()
  ↓
2回目 f()
  ↓
3回目 f()
  ↓
終了条件
  ↑
3回目の残りを実行
  ↑
2回目の残りを実行
  ↑
1回目の残りを実行

つまり、再帰処理は先に奥まで進み、あとから逆向きに戻ると考えると分かりやすくなります。

定義・仕組み

再帰処理には終了条件が必要

再帰関数には、必ず処理を止める条件が必要です。

function f(n) {
    if n == 0 {
        return
    }

    f(n - 1)
}

n == 0 が終了条件です。

これがないと自分自身を呼び続け、最終的にはコールスタックを使い切ってエラーになる可能性があります。

再帰呼び出しの前後で実行タイミングが違う

function f(n) {
    if n == 0 {
        return
    }

    print(n)
    f(n - 1)
    print(n)
}

f(3) を実行すると、最初の print(n) は奥へ進むときに実行されます。

3
2
1

再帰呼び出しの後ろにある print(n) は、戻ってくるときに実行されます。

1
2
3

全体では次の順です。

3
2
1
1
2
3

再帰呼び出しでは、呼び出し元へ戻るための情報がコールスタックに積まれます。スタックそのものは、スタックとは？LIFO・計算途中の値・関数呼出しの仕組みも合わせて確認すると理解しやすくなります。

公式の出題範囲やシラバスは、IPA：基本情報技術者試験から確認できます。

科目Aでどう出る？

科目Aでは、再帰処理の定義や、終了条件・スタックとの関係を知識として問われることがあります。

次の対応を押さえます。

自分自身を呼び出す
→ 再帰

処理を止める条件
→ 終了条件

呼び出し元へ戻る情報
→ コールスタック

特に、終了条件がない再帰は呼び出しが止まらない点を確認します。

科目Bでどう使う？

科目Bでは、再帰関数を読むときに呼び出し回数ごとの状態をトレースすることが重要です。

手順1：終了条件を最初に探す

まず、どこで再帰が止まるかを確認します。

if n == 0
    return

のような条件を先に見つけます。

手順2：再帰呼び出しの前後を分ける

処理A
f(...)
処理B

なら、

処理A → 行きで実行
処理B → 戻りで実行

とメモします。

手順3：呼び出しごとの値を書き出す

例えば f(3)、f(2)、f(1) のように、引数や変数の値を1段ずつ書きます。

スタック操作と組み合わせる例

function f() {
    if A is empty {
        return
    }

    Aからpopした値をCへpushする
    f()
    Cからpopした値をBへpushする
}

この場合、再帰呼び出しより前ではAからCへ値を移します。

before recursion
A → C

Aが空になるまで奥へ進み、その後、戻るときにCからBへ値を移します。

after recursion
C → B

初期状態を、末尾がスタックの先頭として次のようにします。

A = [1, 2, 3]
B = [1, 2, 3]
C = [1, 2, 3]

奥へ進む間は、Aの末尾から 3 → 2 → 1 がCへ移動します。

A = []
C = [1, 2, 3, 3, 2, 1]

その後、戻るときにCの末尾から 1 → 2 → 3 がBへ移ります。

B = [1, 2, 3, 1, 2, 3]

ポイントは、再帰呼び出しの後ろの処理を、すぐには実行しないことです。

よくある誤解・混同

コードは上から下まで毎回そのまま実行される

再帰呼び出しに到達すると、その時点で現在の関数はいったん中断されます。

処理A
f()
処理B

なら、処理B は呼び出した f() が終了して戻ってきてから実行されます。

再帰呼び出しの後ろの処理も「行き」で実行する

これは典型的なひっかけです。

before recursion → 行き
after recursion  → 戻り

と分けてください。

再帰とスタックは関係ない

再帰呼び出しでは、呼び出し元へ戻るための情報がコールスタックに積まれます。

ただし試験問題では、内部実装を細かく考えるよりも、どこまで進んで、どの順番で戻るかを追うことが重要です。

まとめ（試験直前用）

  • 再帰 = 関数の中から自分自身を呼び出す
  • 必ず 終了条件 を確認する
  • 再帰呼び出しより前 = 行きで実行
  • 再帰呼び出しより後 = 戻りで実行
  • 科目Bでは、呼び出し回数ごとに引数・変数・スタックの状態を書き出す

© 2024-2026 stemtazoo. All rights reserved.