再帰呼出しと引数の渡し方
再帰呼出しの定義、階乗の再帰式 F(n)＝n×F(n−1)、値呼出しと参照呼出しの違いを選択肢から見分けられるようになる。再帰関数やスタックを使う問題を、紙の上で1段ずつ追って答えを出せるようになる。
再帰関数のトレース（処理を1段ずつ追うこと）は、公開過去問で本試験系 8 回・免除試験 11 回観測されています。手順どおりに書き出せば必ず解けるので、確実に取れる計算問題です。引数の渡し方は、API でデータを『コピーで渡すか、実体の場所を渡すか』という実務の感覚とそのままつながります。
このレッスンで稽古する（用語チェック・過去問）結論：再帰とは『自分で自分を呼ぶ』こと
再帰呼出しとは、関数の中で自分自身を呼び出す処理のことです。問題を『1つ小さい同じ形の問題』に分けて、それを自分に任せます。
再帰には必ず基底条件（それ以上呼ばずに値を返す止まり方。終了条件とも言う）が必要です。基底条件が無いと呼出しが永遠に続き、プログラムは止まりません。
たとえるならマトリョーシカです。開けると1つ小さい同じ人形が出てきて、いちばん小さい人形（基底条件）で開けるのが止まります。
『再◯可能』とまぎらわしい用語の比較
定義を問う問題では、名前の似た性質が誤りの選択肢に並びます。違いは表で覚えます。
| 用語 | 意味 | 見分けるキーワード |
|---|---|---|
| 再帰的（リカーシブ） | 実行中に自分自身を呼び出せる | 『自分自身を』 |
| 再入可能（リエントラント） | 複数のタスクが同時に共有して実行しても正しく動く | 『同時に』『複数タスク』 |
| 再使用可能（リユーザブル） | ロードし直さずに繰り返し実行しても正しく動く | 『ロードし直さず』 |
| 再配置可能（リロケータブル） | 主記憶のどのアドレスに置いても実行できる | 『どこのアドレスでも』 |
再帰とは関係ない概念が誤りの選択肢に混ざることもあります。『起きた事象に応じて処理する』はイベント駆動、『失敗したら直前の状態に戻す』はロールバックです。
階乗の再帰的定義：F(n)＝n×F(n−1)
階乗 n! は 1 から n までの整数をすべて掛けた値です（例：4! ＝ 4×3×2×1 ＝ 24）。n! ＝ n×(n−1)! と書けるので、再帰の式は次のとおりです。
- n ＞ 0 のとき：F(n) ＝ n × F(n−1)
- n ＝ 0 のとき：F(n) ＝ 1（基底条件。0! ＝ 1 と決められている）
確かめると F(3) ＝ 3×F(2) ＝ 3×2×F(1) ＝ 3×2×1×F(0) ＝ 3×2×1×1 ＝ 6 になります。空欄補充では **『掛け算』かつ『引数が1つ小さくなる』**選択肢を選びます。
再帰のトレース：『行き』と『帰り』を分けて書く
トレース問題は、紙に呼出しを1段ずつ書き出すのがいちばん確実な解き方です。コツは、処理を行き（呼出しを深く下りる間）と帰り（基底条件から戻ってくる間）に分けて考えることです。
- 行き：再帰呼出しより前に書かれた処理が、外側から順に実行される
- 基底条件に着いたら、そこで具体的な値が決まる
- 帰り：再帰呼出しより後に書かれた処理が、内側（いちばん深い段）から順に実行される
帰りの順番は行きの逆になります。これは呼出しの記録がスタック（後から入れたものを先に取り出す積み重ね。LIFO）に積まれるためです。
flowchart TD
A["f(5)=5+f(4)"] --> B["f(4)=4+f(3)"]
B --> C["f(3)=3+f(2)"]
C --> D["f(2)=2+f(1)"]
D --> E["f(1)=1（基底条件）"]
E -.->|"戻る: 1"| D
D -.->|"戻る: 3"| C
C -.->|"戻る: 6"| B
B -.->|"戻る: 10"| A
引数の渡し方：コピーを渡すか、場所を渡すか
関数を呼ぶ側が渡す値を実引数、関数の定義側で受け取る変数を仮引数と呼びます。実引数を仮引数にどう渡すかには、いくつかの方式があります。
| 方式 | 渡すもの | 呼出し元の変数は変わるか |
|---|---|---|
| 値呼出し（call by value） | 値のコピー | 変わらない（保証される） |
| 参照呼出し（call by reference） | 変数の場所（アドレス） | 変わりうる |
| 結果呼出し | 終了時に結果を書き戻す | 変わりうる |
| 名前呼出し | 引数の式そのもの（使うたびに評価する） | 変わりうる |
たとえるなら、値呼出しは書類のコピーを渡すことです。相手がコピーに書き込んでも原本は変わりません。参照呼出しは原本の置き場所を教えることなので、相手が書き換えれば原本も変わります。
f(n)：n≦1 なら 1、それ以外は n＋f(n−1) のとき、f(5) を求める
ア 6
イ 9
ウ 15
エ 25
解き方と答えを見る
- 行き：f(5) ＝ 5 ＋ f(4) の形に展開する
- f(4) ＝ 4 ＋ f(3)、f(3) ＝ 3 ＋ f(2)、f(2) ＝ 2 ＋ f(1) と下りていく
- f(1) は n≦1 を満たす（基底条件）ので 1 を返す
- 帰り：f(2) ＝ 2 ＋ 1 ＝ 3
- f(3) ＝ 3 ＋ 3 ＝ 6
- f(4) ＝ 4 ＋ 6 ＝ 10
- f(5) ＝ 5 ＋ 10 ＝ 15
答え：15（ウ）。式は足し算なので 5＋4＋3＋2＋1 です。掛け算の階乗 120 や、5²＝25 と取り違えないようにします。
スタック A・B・C（初期状態はどれも [1,2,3]）を使う再帰関数 f() の実行後の B
ア [1, 2, 3, 1, 2, 3]
イ [1, 2, 3, 3, 2, 1]
ウ [3, 2, 1, 1, 2, 3]
エ [3, 2, 1, 3, 2, 1]
解き方と答えを見る
- ルールを確認する：右端がスタックの一番上で、pop は右端を取り出し、push は右端に積む
- 1段目の行き：A から 3 を pop して C に push する → A＝[1,2]、C＝[1,2,3,3]。続けて f() を呼ぶ
- 2段目の行き：A から 2 を pop して C に push する → A＝[1]、C＝[1,2,3,3,2]。続けて f() を呼ぶ
- 3段目の行き：A から 1 を pop して C に push する → A＝[]、C＝[1,2,3,3,2,1]。続けて f() を呼ぶ
- 4段目：A が空なので何もせずに戻る（基底条件）
- 3段目の帰り：C から 1 を pop して B に push する → B＝[1,2,3,1]
- 2段目の帰り：C から 2 を pop して B に push する → B＝[1,2,3,1,2]
- 1段目の帰り：C から 3 を pop して B に push する → B＝[1,2,3,1,2,3]
答え：[1, 2, 3, 1, 2, 3]（ア）。C で一度逆順になり、取り出すときにもう一度逆順になるので、B には元の順番 1,2,3 のまま積まれます。
要点（試験直前に読む）
- 再帰呼出しとは『関数の中で自分自身を呼び出す』こと。再入可能・再使用可能・再配置可能と区別する。
- 階乗は F(n)＝n×F(n−1)、F(0)＝1。式は『掛け算』で『引数が1つ小さくなる』。
- トレースは行きで基底条件まで展開し、帰りで内側から値を確定させる。途中の値を省略せずに書く。
- 再帰呼出しより後に書かれた処理は、行きと逆の順で実行される（スタックと同じ LIFO）。
- 呼出し元の変数が変わらないと保証されるのは値呼出しだけ。参照・結果・名前呼出しでは変わりうる。
- 実引数は呼ぶ側、仮引数は受け取る側。仮引数はその関数の中だけで有効。
ひっかけ
- 『同時に複数タスクで共有』は再入可能、『ロードし直さず再実行』は再使用可能、『どのアドレスでも』は再配置可能。再帰を選ぶのは『自分自身を呼び出す』と書かれた選択肢だけ。
- 階乗の空欄補充では、足し算の n＋F(n−1) や、同じ引数で自分を呼ぶ (n−1)×F(n) が誤りとして並ぶ。後者は引数が小さくならないので、再帰が終わらない。
- n＋f(n−1) 型の問題を階乗（掛け算）と思い込むと 120 を選んでしまう。式の演算子を必ず確認する。
- スタックを2回移し替える問題では『逆順になるはず』と思い込みやすい。2回逆転すると元の順に戻るので、1段ずつ書き出して確かめる。
- 『値呼出しでは仮引数を変えると実引数も変わる』は誤り。実引数まで変わるのは参照呼出し。
用語（15）
関数が実行中に自分自身を呼び出すこと。
⚠ 再入可能（複数のタスクが同時に実行できる性質）と混同しやすい。『自分自身を』と書いてあれば再帰。
再帰でそれ以上は呼び出さず、具体的な値を返して止まるための条件。
あるものを、それ自身の一回り小さい場合を使って定義する書き方。
1 から n までの整数をすべて掛けた値 n! で、0! は 1 と決められている。
⚠ 1 から n までの総和（n＋(n−1)＋…）と取り違えやすい。階乗は掛け算。
後から入れたデータを先に取り出す（LIFO）データの入れ物。
⚠ キュー（先に入れたものを先に出す FIFO）と区別する。
push はスタックの一番上にデータを積む操作、pop は一番上のデータを取り出す操作。
複数のタスクが同時に共有して実行しても、正しい結果が得られる性質。
⚠ 再帰的と取り違えやすい。見分けるキーワードは『同時に複数タスク』。
一度実行した後にロードし直さなくても、繰り返し正しく実行できる性質。
⚠ 見分けるキーワードは『ロードし直さずに』。
主記憶のどのアドレスに置いても実行できる性質。
⚠ 見分けるキーワードは『どこのアドレスでも』。
関数を呼び出す側が渡す値や変数。
⚠ 仮引数と逆にしやすい。呼ぶ側が実引数、受け取る側が仮引数。
関数の定義側で受け取る変数で、その関数の中だけで有効。
⚠ 『仮引数が呼出し側でも有効』という選択肢は誤り。
実引数の値のコピーを渡す方式で、関数内で変更しても呼出し元の変数は変わらない。
⚠ 参照呼出しと逆にしやすい。『変更されないことが保証される』のは値呼出しだけ。
変数の場所（アドレス）を渡す方式で、関数内で変更すると呼出し元の変数も変わる。
⚠ 値呼出しと逆にしやすい。
関数の終了時に、仮引数の結果を実引数へ書き戻す方式。
⚠ 呼出し元の変数が変わりうるので、『変更されない保証』の正解にはならない。
引数の式そのものを渡し、関数の中で使うたびに評価する方式。
⚠ これも呼出し元の変数が変わりうる。
このレッスンの過去問
- 再帰呼出しの定義平成29年度 秋期 基本情報技術者試験 午前 問6
- 階乗の再帰的定義(n×F(n−1))基本情報技術者試験 科目A免除 修了試験 20210725 実施分 問10
- 再帰関数のトレース計算平成31年度 春期 基本情報技術者試験 午前 問6
- 引数の渡し方(値呼出し・参照呼出し)平成24年度 春期 基本情報技術者試験 午前 問49