基本情報技術者試験 (FE) 科目 B — 練習問題 第 18 問 / 全 20 問 · 本番相当
二重の再帰呼び出し
関連レッスン: 関数と手続き — ○ から始まる定義の読み方
次のプログラムを実行したとき、出力される内容はどれか。
○整数型: フィボ(整数型: n)
if (n ≦ 2)
return 1
endif
return フィボ(n - 1) + フィボ(n - 2)
print(フィボ(6))解説
正解: ウ 8
呼び出しの木を上から展開すると同じ計算が何度も現れて追いきれません。**小さいほうから積み上げる**のが正解への近道です。フィボ(1) = 1、フィボ(2) = 1、フィボ(3) = 1 + 1 = 2、フィボ(4) = 2 + 1 = 3、フィボ(5) = 3 + 2 = 5、フィボ(6) = 5 + 3 = 8 となります。
終了条件が n ≦ 2 で 1 を返す点に注意してください。n ≦ 1 で 1 を返す定義と 1 つずれるため、同じ「6 番目」でも値が変わります。再帰の問題では、まず終了条件を読んで表の左端を確定させてください。
この関数は フィボ(6) を求めるだけで 15 回の呼び出しが発生します。同じ引数を何度も計算し直す非効率さが再帰の弱点で、計算結果を配列に覚えておく (メモ化) と 1 回ずつで済みます。
呼び出しを上から展開すると破綻する。終了条件から小さい順に表を作る。
演習量を増やしたい方へ(おすすめ書籍)
擬似言語の記法の読み方から、トレースして答えを出すまでを一冊で通せる科目B特化本。手を動かして追う練習量を確保したいときの定番。
科目Bの出題パターンを網羅的に演習できる対策書。構文を理解した後、解法の型を身につける段階で効く。
科目Bの出題範囲を絞り込んだ薄型の対策書。頻出アルゴリズムと情報セキュリティを短期間で一周したいときに。
本セクションはAmazonアソシエイトのリンクを含みます。
プログラムの読み方でつまずいたら。
たいてっくが、アルゴリズムの追い方から SQL・データベース設計まで、1対1で学習をサポートします。「コードを目で追っても何をしているか分からない」段階からで大丈夫です。まずは無料相談から。
「教え方も上手で、お人柄も良いメンターです。DB周りの知識はもちろん、何より、しっかり教えてあげようという姿勢がとてもありがたかったです。データベース、SQLの学習を考えている方にはおススメです。」
— H 様(DB・SQL コース受講)「体系的に知識を教えてくださり、実際の業務でも大変役立っております。特に短い時間で効率よく知識の習得や、練習をできているのは期待以上でした。」
— M 様(DB・SQL コース受講)「大変充実したコンテンツでわかりやすいご説明をありがとうございました。基本的な質問にも丁寧にご説明いただき、また業務のご相談にも乗って頂き大変有意義な時間でした。」
— K 様(DB・SQL コース受講)