基本情報科目Bの再帰呼び出しがわからない人への対策方法を解説|擬似言語で処理を追うコツ
「再帰呼び出しは、関数が自分自身を呼ぶ処理」と説明されても、呼び出したあとにどの行へ戻るのかがわからなくなることはありませんか?
基本情報技術者試験の科目Bで再帰問題を解くときに大切なのは、コードを頭の中で全部動かそうとしないことです。①どこで止まるか、②どの順番で呼ぶか、③どの順番で戻り値を計算するかの3つを紙に分けて書くと、短い問題から解けるようになります。
この記事では、階乗の基本例から、初見でも解きやすいオリジナル例題、停止条件のミスの見分け方まで解説します。
再帰呼び出しとは?最初に3つだけ覚えよう¶
再帰呼び出しとは、ある関数の処理の途中で、その関数自身を呼び出すことです。例えばf(4)を処理するためにf(3)が必要で、f(3)を処理するためにf(2)が必要になる、といった形です。
再帰には次の3要素があります。
| 要素 | 役割 | 確認すること |
|---|---|---|
| 停止条件 | 再帰を終える | n = 0やn ≦ 1など、どんな値で止まるか |
| 再帰呼び出し | 同じ関数を再び使う | f(n - 1)など、引数はどう変化するか |
| 戻り値 | 各呼び出しの答えを返す | 呼び出しから戻った値で何を計算するか |
停止条件がない、または停止条件に近づかないコードでは、呼び出しが終わらなくなる可能性があります。最初に「どの引数で再帰が終わるか」を確認しましょう。
例題1:階乗の再帰を呼び出し順と戻り順に分ける¶
次は説明のために作成したオリジナルの擬似言語です。fact(4)の戻り値を求めてみます。
○整数型: fact(整数型: n)
if (n = 0)
return 1
endif
return n × fact(n - 1)
「階乗」は、例えば4! = 4 × 3 × 2 × 1 = 24という計算です。0! = 1と定義します。
ステップ1:停止条件を探す¶
n = 0なら1を返します。ここで再帰呼び出しは行いません。
ステップ2:呼び出される順番を下へ書く¶
fact(4)は、答えを出すためにfact(3)を呼びます。同様に、小さい値へ進みます。
fact(4)
└ fact(3)
└ fact(2)
└ fact(1)
└ fact(0) → 1を返す
ここで重要なのは、fact(4)の計算をまだ完了していないことです。下位のfact(3)の答えを待っています。
ステップ3:一番下から戻り値を計算する¶
| 戻る順 | 呼び出し | その段階の計算 | 戻り値 |
|---|---|---|---|
| 1 | fact(0) |
停止条件に一致 | 1 |
| 2 | fact(1) |
1 × fact(0) = 1 × 1 |
1 |
| 3 | fact(2) |
2 × fact(1) = 2 × 1 |
2 |
| 4 | fact(3) |
3 × fact(2) = 3 × 2 |
6 |
| 5 | fact(4) |
4 × fact(3) = 4 × 6 |
24 |
したがって、答えは24です。
再帰が苦手な人は「関数を呼ぶ方向」と「戻って計算する方向」を混ぜてしまいがちです。この2つを分ければ、戻り値がどの段階で確定するかを追いやすくなります。
呼び出しスタックとは?「途中の計算を保留する場所」¶
fact(4)は4 × fact(3)を計算する途中で、fact(3)の完了を待ちます。そのとき、n = 4という引数や、どこへ戻るかという情報を保持する仕組みが呼び出しスタックです。
ここでの「スタック」とは、後から積んだものを先に取り出す後入れ先出し(LIFO)の構造です。
| 呼び出し時に積まれる処理 | 保留している内容 |
|---|---|
fact(4) |
4 × (戻り値待ち) |
fact(3) |
3 × (戻り値待ち) |
fact(2) |
2 × (戻り値待ち) |
fact(1) |
1 × (戻り値待ち) |
fact(0) |
1を返して終了 |
fact(0)が終わると、fact(1)、fact(2)…の順番で保留していた計算を再開します。最後に呼んだ関数から先に戻るわけです。
なお、「スタックとキューの違い」を基礎から学びたい場合は、擬似言語のスタックとキューの違いも参考になります。
例題2:階乗ではない再帰問題も同じ方法で解ける¶
次の擬似言語でcalc(5)を実行すると、戻り値はいくつでしょうか。
○整数型: calc(整数型: n)
if (n ≦ 1)
return 0
endif
return n + calc(n - 2)
選択肢は、ア:8 イ:9 ウ:10 エ:15です。
① 停止条件はn ≦ 1¶
n = 1でもn = 0でも、戻り値は0です。
② 引数は2ずつ減る¶
calc(5) → calc(3) → calc(1)の順で呼び出されます。calc(1)で停止条件を満たします。
③ 逆順に戻って計算する¶
| 関数 | 計算 | 戻り値 |
|---|---|---|
calc(1) |
停止条件なので0 | 0 |
calc(3) |
3 + calc(1) = 3 + 0 |
3 |
calc(5) |
5 + calc(3) = 5 + 3 |
8 |
正解はア:8です。
よくある間違いは、引数を5, 4, 3, 2, 1と1ずつ減らしてしまうこと。この例ではn - 2なので、5, 3, 1と変化します。再帰が複雑に見えたときこそ、再帰呼び出しの括弧内を確認してください。
例題3:関数を呼んだあとに計算するか、先に計算するか¶
次の2つのコードを比べてみます。
コードA:戻り値を使って合計する
○整数型: a(整数型: n)
if (n = 0)
return 0
endif
return n + a(n - 1)
a(3)は3 + 2 + 1 + 0なので、6になります。
コードB:戻り値を加工する
○整数型: b(整数型: n)
if (n = 0)
return 1
endif
return 2 × b(n - 1)
b(3)は2 × 2 × 2 × 1なので、8になります。
どちらも呼び出し順は3 → 2 → 1 → 0です。しかし、停止条件の戻り値と、呼び出しから戻ったあとの計算式が異なるため、結果が変わります。
「呼び出し方だけ」で答えを決めず、必ずreturn文全体を読みましょう。
科目Bの再帰問題を解くための3ステップ¶
本番形式の問題を読むときは、以下の順番で確認すると整理しやすいです。
- 停止条件に線を引く:どんな値で何が返るか、先に決める。
- 引数の変化だけを追う:最初は計算を保留し、
n → n-1やn → n-2を紙に書く。 - 戻る順番で表を埋める:最後に呼んだ関数から戻り値を確定する。
トレース表の書き方を基礎から確認したい人は、基本情報科目Bのトレース表の書き方も参照してください。
迷ったら、最初の引数を小さくして試す¶
f(10)だと頭の中で追い切れなくても、f(2)やf(3)なら順番を確認できます。小さな値で規則を確かめてから本題へ戻るのが有効です。
再帰と繰返しの違いを一言で整理¶
forやwhile:同じ処理を繰り返し、変数を更新する。- 再帰:同じ関数を呼び出し、それぞれの呼び出しが独自の引数や戻る場所を持つ。
どちらでも同じ計算を実現できる場合はありますが、問題文にある処理の流れをそのまま追うことが大切です。無理に繰返しへ書き換える必要はありません。
再帰問題のよくある4つのミス¶
| ミス | 何が起こるか | 確認方法 |
|---|---|---|
| 停止条件を読み飛ばす | どこまで呼び続けるか分からなくなる | ifとそのreturnを先に囲む |
| 引数の減り方を間違える | 余分な関数呼び出しを数えてしまう | f(n-1)かf(n-2)か確認 |
| 戻り値を上から計算する | 下の関数の値が未確定で混乱する | 最下段から表を埋める |
returnの外側の演算を忘れる |
n × f(n-1)をf(n-1)と取り違える |
計算式全体を書き写す |
再帰呼び出しは、最初から速く解こうとするよりも、呼び出し順・戻り順を正確に書き出す習慣が効果的です。
どこで再帰問題を練習できる?¶
Giji Academyには、無料の入門問題と、会員向けの基礎・中級・過去問レベルの演習があります。再帰を含む応用問題は「過去問レベル」の有料会員向け範囲として案内されています。まず無料問題で代入・条件分岐・戻り値の基礎を確認し、必要に応じて応用演習へ進む方法がおすすめです。
特定の教材で任意の再帰コードをそのまま実行できるかどうかは、教材ごとの仕様によります。この記事の例題は、まず紙のトレース表でも十分に練習できます。
よくある質問¶
再帰呼び出しは暗記するだけで解けますか?¶
階乗などの有名な公式だけを覚えても、初見の再帰問題では対応できません。停止条件、引数の変化、戻り値の計算を追う練習が必要です。
停止条件が2つあるときはどうすればいい?¶
各条件に当てはまる引数と、そのとき返す値を先に表にしてください。そのうえで、呼び出し順を追います。
1つの関数で2回再帰呼び出しをするときは?¶
例えばf(n-1) + f(n-2)なら、呼び出しが枝分かれします。左と右の枝をそれぞれ小さい引数まで追い、戻り値が確定したら足し合わせます。呼び出し回数を数える設問では、同じ引数が複数回登場することにも注意してください。
まとめ¶
科目Bの再帰問題は、難しい式に見えても次の順番で整理できます。
停止条件を確認する → 呼び出す順番を書く → 逆順に戻り値を求める。
まずは記事中のfact(4)とcalc(5)を、解説を見ずにもう一度トレースしてみてください。自分で戻り値を説明できれば、再帰への苦手意識を減らす第一歩になります。