【基本情報技術者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)の計算を繰り返します。

$$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就職のブログ << をやってます。

でわでわ（・ω・▼）ノシ