【基本情報技術者9問】再帰関数を解く「2つの工夫」
再帰関数の難しさは2点。
計算が終了できるまで繰り返すので、たくさん計算することになる
関数の計算中に、さらに関数を呼び出すので、どの関数がどこで終わったかが分かりにくい
私はIT専門学校で「2つの工夫」を学生さんに教えています。
・矢印や行揃え（インデント）で関数の開始と終了を分かり易くする
・選んだ条件の番号を書いて、条件選択を分かり易くする
急いでいても丁寧に解いて下さいね。
解きミスを防いで、見直しもスムーズになりますから。
このNoteには、基本情報技術者修了試験の最新R06年01月～R02年06月から再帰関数だけ10問を集めました。簡単・基本・出題頻度で並べて、段階的に問題演習できるよう構成も工夫しました。
ぜひ最初の5～6問までは確実に解けるようになって、得点源にして欲しいです。
それでは始めましょう！
方程式の「移項」で解く問題
正答はア。
問題文より、「第n世代の個数f(n)」と「1世代後の最近の数」が「f(n+1)」であることが読み取れたならOKです。
中学校で習った「方程式の移項」を用いて「f(n+1)=f(n)を絡めた式」のように、f(n+1)とf(n)を左辺と右辺にキレイに分離できれば勝ち。
$$
f(n+1) + 0.2 \times f(n) = 2 \times f(n)\\
f(n+1) = 2 \times f(n) - 0.2 \times f(n)\\
f(n+1) = 1.8 \times f(n)
$$
以上より、f(n)を1.8倍すればf(n+1)になるのが分かります。したがって正答はア。
まずはウォーミングアップでした。
再帰関数は「（2分岐や3分岐の）再帰関数を計算せよ」パターンが一番多く出題されます。
2分岐の再帰関数（数式表現）
正答はイ。
y=0になってxを出力するまで、F(y , x mod y)の計算を繰り返します。
x mod yは大丈夫ですよね。「x ÷ y をした時の余り」です。
$$
F(231, 15) 条件②より= F(15, 231\mod 15) = F(15, 6) \\
条件②より= F(6, 15\mod 6) = F( 6, 3) \\
条件②より= F(3, 6\mod 3) = F( 3, 0)\\
条件①より=3
$$
2分岐の再帰関数（英語表現）
正答はウ。
数式から「n≦1の時は1」「それ以外では n + f(n-1)」と読み取れれば、勝ちです。
2分岐の再帰関数（英語表現）
正答はイ。
$$
f(775, 527)条件②より=f(527, 248)\\
条件②より=f(248, 31)\\
条件②より=f(31, 0)\\
条件①より、xを出力するので、31。
$$
3分岐の再帰関数
正答はエ。
条件①と③が発動して「1」になるまで、ひたすら計算を繰り返します。
落ち着いて、矢印と条件番号を書きましょう。解きミスを防ぐだけでなく、見直した時もスムーズになりますから。
再帰関数を作る問題
ア～エの全て再帰関数で計算をして、正しい式・正しい計算ができる選択肢を特定する解法は、過去問道場さん（基本情報技術者平成20年秋期 午前問14）にお任せします。
ここでは、推測して絞っていく方法を試します。
例えば、F(3) = 3 × 2 × 1となるような式を特定できれば良いですよね。
また、n=0にならないと計算が追わないのも分かります。終了条件はf(0)=1なので、f(n-1)の形が必ず入っているはず。
よって、アかウです。アに「+」、ウに「×」があるので、「3 × 2 × 1」を作るからウだろうなと分かります。
確かめてみます。
最後に「×1」が多くなりますが、計算結果には影響がないので良しとします。
おまけで細かい話をします（スキップしてもOK）。
キレイにするには「n>1」「n=1」の条件にすれば良いと思いますね。しかし実は0の階乗「0!=1」と決められています。
「n>1」「n=1」を条件にすると、f(0)が計算できなくなってしまいます。よって「n>0」「n=0」を条件にしていたようです。
2分木と絡めた珍しい問題
＞＞逆ポーランド記法の解説Note＜＜ で扱ったので、既に読んだ方は飛ばしてOKです。
まず簡単な例で動作を理解してくださいね。
解き方が分からない時は、仮説をたてて試算するぐらいの根性が必要です。
では次は、本番行きましょう。
行頭を揃える・線を引くなど、書き方を工夫しましょう。
解きミスを防ぐだけでなく、見直す時に短時間で済みます。急いでいるからと殴り書きすると苦労するのは自分です。
過去問ドットコムさんの解説リンク（基本情報技術者平成26年春期 午前問6）も貼っておきます。私の説明が分かりにくい場合は別アプローチへ。
関連して ＞＞逆ポーランド記法の解説Note＜＜ もどうぞ。
プログラムのような問題（順次処理）
正答はイ。
いきなり解くよりも、簡単な数字で動作を確認した方が慎重で良いですね。
では本番をします。
プログラムのような問題（配列）
正答はア。
まとめ | 丁寧に書き出して解こう！
再帰関数は自分自身を呼び出し続けるので、難しいです。
プログラムでもなるべく使いたくありません。終了条件をミスると無限ループにあってしまいますからね。
このNoteで見たように、資格問題を解く時は
・矢印や行頭（インデント）などで経緯を明確に。
・①②などのどの条件が発動したのかを明確に。
などの工夫をして解きましょう。
急いでいても丁寧に書いて下さい。解くのは後回しでもOKです。
丁寧に書き出すと、解きミスを防げますし、見直しの時もスムーズです。
今後も計算問題シリーズを準備していくので、また来てくださいね！
＼力試しは修了試験で！4回分の解説です／
p.s. 普段は >> 専門学校とIT就職のブログ << をやってます。
でわでわ（・ω・▼）ノシ
いいなと思ったら応援しよう！
