基本情報の再帰関数がわからない人へ｜科目Bの解き方を図解

基本情報技術者試験の科目Bで、再帰関数が出てくると急に手が止まる人は多いです。自分自身を呼び出す処理なので、普通の順番どおりに読もうとすると、どこへ進んでいるのか、いつ戻ってくるのかが見えにくくなります。

ただ、再帰関数は才能やひらめきで解く問題ではありません。終了条件、引数の変化、戻り値の戻り方を分けて書けば、科目Bの擬似言語でもかなり読みやすくなります。この記事では、基本情報の再帰関数を「手で追う」ための順番を、初心者向けに整理します。

基本情報の再帰関数の読み方

再帰は自分を呼ぶ関数

再帰関数とは、処理の途中で同じ関数をもう一度呼び出す関数です。たとえば「nから1までを順に掛ける」処理を考えると、nの答えを出すためにn-1の答えが必要になり、さらにn-2の答えが必要になる、という形になります。この「同じ形の小さい問題に分ける」考え方が再帰の中心です。基本情報の科目Bでは、擬似言語の中で関数が自分自身を呼び出す形として出ることがあります。

苦手に感じる理由は、処理が一方向に進まないからです。通常のループなら上から下へ、条件が合う間だけ繰り返すと読めます。一方、再帰関数は呼び出すたびに新しい作業場所が作られ、そこでまた同じ処理が始まります。見た目は同じ関数名でも、引数や途中の値は呼び出しごとに別物です。ここを一つの変数としてまとめて考えると混乱します。

まず押さえたいのは、再帰は「同じ関数の中に戻っている」のではなく、「同じ形の処理を新しい状態で呼び出している」と見ることです。ノートに書くときも、同じ行に上書きするのではなく、呼び出しごとに行を分けます。n=4の呼び出し、n=3の呼び出し、n=2の呼び出しというように、別々の箱を積む感覚ですね。

この見方ができると、再帰関数は特別な魔法ではなくなります。大きな問題を小さな問題へ渡し、いちばん小さい問題で答えを確定し、そこから順番に答えを返すだけです。科目Bでは難しい数式よりも、この「呼び出し」と「戻り」の順番を正確に追えるかが問われます。

問題文で関数名が何度も出てきても、まずは怖がらなくて大丈夫です。同じ処理を別の入力で試しているだけだと見れば、追う対象をかなり減らせます。

• 再帰は同じ形の小さい問題へ分ける処理
• 呼び出しごとに引数や途中値は別物
• ノートでは呼び出しを1行ずつ分けて書く

終了条件を先に見る

再帰関数を読むときは、最初に終了条件を探します。終了条件とは、これ以上自分自身を呼び出さずに値を返す条件です。多くの場合、nが0、nが1、配列の添字が範囲外、木のノードが空、などの形で書かれます。ここを見つけないまま読み始めると、再帰呼び出しがどこまで続くのか分からず、不安なまま問題文を追うことになります。

終了条件は、再帰のゴールです。ゴールが分かると、引数がそのゴールへ近づいているかを確認できます。たとえば n が1になったら1を返す関数なら、再帰呼び出しの引数が n-1 になっていれば、いつか1へ近づきます。反対に、n+1 のように終了条件から遠ざかる形なら、問題としては無限に呼び出す危険があるため、選択肢の誤りを見抜く材料になります。

科目Bの問題では、終了条件がif文の先頭に置かれることもあれば、再帰呼び出しの後ろに埋もれていることもあります。先に関数全体をざっと眺め、returnしている箇所を丸で囲むと読みやすいです。returnが複数ある場合は、「すぐ返るreturn」と「再帰の結果を使って返るreturn」に分けると、処理の性質が見えてきます。

終了条件を確認したら、問題文の入力例を小さい値に置き換えてみます。n=1で終わるならn=2、n=3くらいを使います。いきなりn=10や配列全体を追う必要はありません。小さい値で終了条件に到達する流れが分かれば、同じ構造で大きい値も読めるようになります。

本番では、終了条件の行に印を付けてから選択肢を見るだけでも、焦りがかなり減ります。止まる場所が分かれば、あとはそこへ近づく式かどうかを確認できます。

見る場所	確認すること
if文	どの条件で再帰を止めるか
return文	値を直接返すのか、再帰結果を使うのか
引数	終了条件へ近づいているか

引数の変化を書き出す

終了条件を見つけたら、次は引数の変化だけを書き出します。再帰関数の問題で混乱しやすい人は、処理の中身、計算式、選択肢を同時に追いがちです。まずは余計な情報をいったん置き、関数がどんな引数で呼ばれるのかだけを表にします。これだけで、再帰が深くなっていく向きがはっきりします。

たとえば f(4) が f(3) を呼び、f(3) が f(2) を呼び、f(2) が f(1) を呼ぶなら、表には f(4)、f(3)、f(2)、f(1) と並べます。この時点では戻り値を計算しなくて構いません。大切なのは、どの順番で呼び出しが積まれていくかを見える形にすることです。再帰は頭の中だけで追うと、1つ前の状態を忘れやすくなります。

配列や文字列を扱う再帰では、引数が数値1つとは限りません。添字、探索範囲の左端と右端、現在のノード、残り文字数などが変わります。この場合も、変化する値だけを列にすれば十分です。関数の中で更新されない変数まで表に入れると、かえって見づらくなります。

引数の表は、トレース表の一部として考えると楽です。すでにトレース表の作り方に慣れている人は、再帰呼び出しを「処理行」ではなく「呼び出し段」として書くと整理しやすくなります。関連して、基本情報のトレース表の書き方も確認しておくと、科目Bの追跡がかなり安定します。

表を書くときは、きれいに作ることより、後から戻り値を書き足せる余白を残すことを優先してください。呼び出し順の横に空欄を作っておくと、終了条件まで到達したあとに戻り値を上へ埋められます。この書き方に慣れると、長い擬似言語でも途中状態を見失いにくくなります。

• まず関数名と引数だけを書き出す
• 戻り値の計算は後回しにする
• 変化する値だけを表に入れる
• 小さい入力例で呼び出し順を確かめる

戻り値は下から戻る

再帰関数は、呼び出しが深くなる方向と、値が戻る方向が逆になります。ここが最大のつまずきどころです。f(4)から始まってf(3)、f(2)、f(1)へ進む場合、最初に値が確定するのはf(1)です。その値がf(2)へ戻り、f(2)の計算結果がf(3)へ戻り、最後にf(4)の答えが決まります。つまり、呼び出しは上から下へ、戻り値は下から上へ進みます。

階乗のような問題なら、f(1)=1が先に決まり、f(2)=2×f(1)、f(3)=3×f(2)、f(4)=4×f(3)という順番で戻ります。この戻り方を理解せずに、f(4)の式だけを見て計算しようとすると、途中で「f(3)は何だったか」と迷います。再帰では、呼び出した先の答えが返ってきてから、今いる段の計算が完了すると考えるのが自然です。

戻り値を追うときは、引数表の右側に「返る値」の列を作ります。まず終了条件の行だけ値を書き、そこから上に向かって空欄を埋めます。これは科目Bの穴埋め問題にも効きます。選択肢の式が正しいかどうかを、上からではなく下から戻して確認できるからです。

戻りの順番は、木構造の探索や分割統治でも同じです。左側の子を処理してから右側の子を処理するのか、子を処理してから自分を数えるのかによって、返る値や表示順が変わります。見た目のコードが短くても、呼び出しの深さと戻り方を分けて書けば、選択肢をかなり絞りやすくなります。

基本情報の科目Bは問題文が長く見えることがありますが、再帰部分の本質は「どの条件で止まり、どの値を返し、前の段でどう使うか」です。戻り値の列を下から埋めるだけで、複雑そうに見える処理が一つずつ確定していきます。

スタックで状態を分ける

再帰関数を正確に読むには、呼び出しごとに状態を分けて考える必要があります。この状態を積み重ねるイメージがスタックです。スタックは、後から入れたものが先に出る構造です。再帰関数では、あとから呼び出された関数が先に終了し、その結果が前の呼び出しへ戻ります。だから、再帰の戻り方はスタックと相性が良いのです。

たとえば f(4) の処理中に f(3) を呼ぶと、f(4)の途中状態は一時停止します。次にf(3)の処理が進み、f(2)、f(1)と深くなります。f(1)が終了してから、止まっていたf(2)、f(3)、f(4)が順に再開します。呼び出しごとに途中状態が保存されている、と考えると理解しやすいですね。

科目Bでスタックという用語が直接出てこなくても、この考え方は役に立ちます。特に、再帰呼び出しの前後に処理がある問題では、呼び出し前に何をするか、呼び出し後に何をするかで結果が変わります。表示や加算の位置が少し違うだけで、出力順や合計値が変わるため、状態を分けずに読むとミスしやすくなります。

ノートでは、関数呼び出しを縦に積み、各段に「引数」「まだ終わっていない式」「返る値」を書きます。1段に情報を詰め込みすぎる必要はありません。むしろ、同じ関数でも呼び出しごとに別の段として扱うことが重要です。配列やリストと一緒に出る場合は、基本情報の配列・リスト・ポインタの考え方も合わせて押さえると、参照先や添字の変化まで追いやすくなります。

スタックの図は、正確な専門用語として覚えるより、答案作成の補助線として使うのがおすすめです。上書きせずに積む、最後に積んだものから戻る、この二つだけでも十分に役立ちます。

スタックで見る項目	書く内容
呼び出し段	f(4)、f(3)のような関数名と引数
保留中の式	戻り値を待っている計算
返る値	終了条件から上へ戻して決まる値

基本情報の再帰問題の解き方

階乗問題で流れを追う

再帰関数の練習は、階乗問題から始めるのが分かりやすいです。階乗は、n! = n × (n-1)! という形で、小さい問題に分けやすいからです。nが1になったら1を返す、そうでなければnにf(n-1)を掛ける、という流れは、終了条件と再帰呼び出しの関係を理解する教材として向いています。

たとえば f(4) を考えると、呼び出しは f(4) → f(3) → f(2) → f(1) と進みます。f(1) は終了条件なので1を返します。そこから f(2)=2×1、f(3)=3×2、f(4)=4×6 と戻って、最終的に24になります。この流れを一度でも紙に書くと、再帰は「先に深く進んで、あとで計算して戻る」処理だと実感できます。

科目Bの問題では、階乗そのものが出るとは限りません。ただ、合計、最大値、要素数のカウント、文字列の長さ、木の深さなど、多くの問題が階乗と同じ読み方で追えます。大きい値の答えを出すために、小さい範囲の答えを使っているなら、考え方はかなり近いです。

練習するときは、表を作って「呼び出し」と「戻り」を別々に書きます。呼び出し列には f(4)、f(3)、f(2)、f(1)。戻り列には 1、2、6、24 と下から上へ記入します。最初から暗算で答えを出すより、表にして順番を確認した方が本番で崩れにくいです。

IPAが公開している科目Bサンプル問題でも、擬似言語を読みながら処理を追う力が問われます。公式の問題形式に慣れる意味でも、短い再帰例を自分の手で表にする練習は有効です。

木構造は順序に注目する

再帰関数は、木構造の探索でもよく使われます。木構造は、1つの要素から複数の子要素へ分かれる形です。親から子へ、さらに孫へと同じ処理を繰り返すため、再帰で表しやすいのです。基本情報の科目Bでは、ノード、左部分木、右部分木、空の子などの表現が出てくることがあります。

木構造の再帰では、どの順番で処理するかが重要です。自分の値を先に処理してから左と右へ進むのか、左を処理してから自分、最後に右へ進むのか、左右の子を処理してから自分を処理するのかで、出力順が変わります。コードの行数は短くても、処理の位置が少し違うだけで答えが変わるので注意が必要です。

読むときは、関数内の再帰呼び出しが何回あるかを確認します。1回なら直線的に深く進む問題が多く、2回なら左右や前後に分かれる問題が多いです。2回呼び出す場合は、1つ目の呼び出しが完全に終わって戻ってから、2つ目の呼び出しへ進むと考えます。左右が同時に動くわけではありません。

木構造の問題でも、小さい例を自分で作るのが有効です。ノードが3つだけの木を描き、関数の中にある処理を順番にたどります。左の子へ進む、空なら戻る、親の値を処理する、右の子へ進む、というように、呼び出しと戻りを矢印で書くと、出力順やカウント結果を判断しやすくなります。

木構造が苦手な人は、用語の意味と図を分けて覚えるより、実際に手でなぞる方が早いです。親、子、葉、空の子という言葉を確認したら、あとは関数呼び出しの順番に沿って印を付けます。再帰関数は図と相性が良いので、問題文の余白に小さく木を書くだけでも理解が進みます。

• 再帰呼び出しが1回か2回かを見る
• 左と右の呼び出し順を確認する
• 処理が呼び出し前か後かを区別する
• 小さい木で出力順を試す

穴埋めは条件から逆算

科目Bでは、再帰関数の一部が空欄になり、正しい式や条件を選ぶ問題もあります。このタイプでは、空欄だけを見て考えるより、終了条件と再帰呼び出しの関係から逆算する方が安定します。何を返すべき関数なのか、どんな入力で止まるべきなのかを先に決めると、選択肢の違いが見えやすくなります。

まず、関数の目的を一文で書きます。「配列の合計を返す」「木の要素数を数える」「n番目の値を求める」のように、戻り値の意味を言葉にします。次に、最小ケースでは何を返すべきかを考えます。空の配列なら0、空のノードなら0、n=1なら1など、自然な値が見えてきます。

そのうえで、再帰呼び出しに渡す引数が目的に合っているかを確認します。配列の残り部分を処理したいのに同じ添字を渡していれば進みません。右側の範囲を処理したいのに左端が変わっていなければ、同じ範囲を繰り返す可能性があります。穴埋めでは、終了条件へ近づく選択肢を優先して見ると外しにくいです。

戻り値の式も、目的から逆算できます。合計なら「今の値 + 残りの合計」、個数なら「1 + 子の個数」、最大値なら「今の候補と再帰結果の大きい方」です。選択肢が似ている場合は、小さい入力を1つ入れて、期待する答えになるかを試します。数学的に証明しようとするより、科目Bでは小さい例で矛盾を見つける方が速い場面が多いです。

特に注意したいのは、再帰呼び出しの位置とreturnの組み合わせです。再帰結果を受け取ってから加工するのか、そのまま返すのか、条件によって別の値を返すのかで答えが変わります。空欄の前後にある変数名を見て、何を待っている式なのかを確認しましょう。

空欄の種類	逆算の見方
終了条件	最小ケースで自然な値を返すか
引数	問題が小さくなっているか
戻り値	関数の目的に合う合成になっているか

練習は小さい値から始める

再帰関数の練習で一番大切なのは、小さい値から始めることです。科目Bの問題文には、配列の要素が多かったり、木構造が大きかったり、条件分岐が複数あったりします。しかし、いきなり全体を追う必要はありません。まずはn=1、n=2、要素数2、ノード3つなど、手で追えるサイズに縮めます。

小さい値で試すと、終了条件に届くか、引数が正しく変わるか、戻り値がどの順番で決まるかがすぐに分かります。もし小さい値で説明できないなら、大きい入力でも正しく追えません。逆に、小さい例で流れが見えれば、本番の大きな問題は同じ操作を繰り返すだけになります。

練習量を増やすときは、ランダムに問題を解くより、テーマを分けると効率的です。最初は階乗や合計のような直線型、次に二分探索や範囲分割、最後に木構造や複数回呼び出しへ進むと、負荷が急に上がりません。基本情報のアルゴリズム全体の流れは、基本情報のアルゴリズム対策と合わせて確認すると、再帰だけでなく科目B全体の位置づけも見えます。

また、解説を読むだけで終わらせないことも重要です。再帰は読んだ瞬間には分かった気になりやすい一方、別の問題になると手が止まりやすい分野です。必ずノートに呼び出し順を書き、戻り値を下から埋める練習を入れましょう。1問に時間をかけても、型が身につけば次から速くなります。

無料で演習したい場合は、基本情報の過去問アプリで科目Bの問題を解くのも手軽です。解いたあとに正解だけを見るのではなく、再帰呼び出しがある問題では、必ず「終了条件」「引数」「戻り値」の3点を自分の言葉で確認してください。

• n=1やn=2から試す
• 呼び出し順と戻り値を別々に書く
• 直線型から木構造へ進める
• 正解後も自分でトレースを残す

基本情報の再帰関数まとめ

基本情報の再帰関数は、見た目よりも読み方の型が大切です。まず終了条件を探し、次に引数がどう変わるかを書き出し、最後に戻り値を下から上へ埋めます。この順番を守るだけで、再帰処理はかなり落ち着いて読めるようになります。頭の中だけで追わず、呼び出しごとに状態を分けるのがポイントです。

科目Bで再帰関数が出ると、関数名が何度も登場するため複雑に見えます。しかし、実際には同じ処理を小さい問題へ渡しているだけです。終了条件に到達したら値が確定し、その値が1段ずつ戻っていきます。呼び出しの方向と戻り値の方向を分けて考えれば、階乗、合計、木構造、穴埋め問題にも対応しやすくなります。

勉強の順番としては、最初に階乗や合計のような短い例で型を作り、その後に配列、範囲分割、木構造へ広げるのがおすすめです。いきなり難しい問題を解こうとすると、再帰そのものではなく、データ構造や条件分岐でつまずきます。まずは小さい値で確実に追える状態を作りましょう。

本番では、すべての処理を完璧に暗算する必要はありません。選択肢を絞るために、小さい入力で矛盾を見つける、終了条件へ近づかない式を除外する、戻り値の向きが逆の選択肢を消す、といった実践的な読み方が役立ちます。再帰は慣れるまで時間がかかりますが、型が身につくと得点源にできます。

最後に、再帰関数は「わかったつもり」で終わらせないことが大切です。この記事の手順を使って、1問ずつ呼び出し表と戻り値表を書いてみてください。数問続けると、どこで止まり、どこへ戻り、何を返すのかが自然に見えるようになります。