基本情報【科目B】令和4年度サンプル問題問7解説(再帰):本質は｢引数の変化｣

基本情報技術者試験科目Bの「令和4年度(12月公開) サンプル問題問7」(再帰・階乗 factorial)を、選択肢の絞り込み手順で解説します。再帰の鉄則 「元の引数を変化させて呼び出す」 を押さえれば、トレースなしでも正解できます。

動画で見たい方はこちら▼

index

問題(令和4年度サンプル問題問7)

次のプログラム中の【　　　】に入れる正しい答えを、解答群の中から選べ。

関数 factorial は非負の整数 n を引数にとり、その階乗を返す関数である。
非負の整数 n の階乗は n が 0 のときに 1 になり、それ以外の場合は 1 から n までの整数を全て掛け合わせた数となる。

〔プログラム〕

○整数型：factorial（整数型：n）
　if（n ＝ 0）
　　return 1
　endif

　return 【　　　】

解答群

ア　(n − 1) × factorial(n)
イ　factorial(n − 1)
ウ　n
エ　n × (n − 1)
オ　n × factorial(1)
カ　n × factorial(n − 1)

正解は カ n × factorial(n − 1) です。

①「1 から n までの整数すべてを掛け合わせた」とあるため、1×2×3...×n(もしくは n×(n-1)×(n-2)...×1)と､引数によって処理回数が変わります｡

処理回数が固定ではない場合､繰り返しか再帰が必ず必要です。プログラム上、繰り返し処理は無いため、再帰しながら掛け算をしている ア・オ・カに絞られます。

②再帰する場合、元の引数を変化させて呼び出さないと無限ループ になります。

選択肢	呼び出し	引数の変化	判定
ア	`(n − 1) × factorial(n)`	n のまま	× 無限ループ
オ	`n × factorial(1)`	固定値1	× 無限ループ
カ	`n × factorial(n − 1)`	n を 1 ずつ減らす	○

これで カ一択 に絞れます。

③トレースで検証(n=4)

4 × ~~factorial(3)~~ → 3 × ~~factorial(2)~~ → 2 × ~~factorial(1)~~ → 1

4 の階乗 24 になるので、カで正しいです。

Memo: 再帰は似たような問題が出る可能性大

再帰を使った階乗は、プログラミング学習では定番です。穴埋めにして難しすぎない問題が他に作りにくいため、似た形式が今後も出る可能性が高いです。判別2ステップ(① 再帰してる選択肢に絞る、② 引数が変化していないものを除く)を覚えておきましょう。

再帰問題は 「引数が変化していない選択肢は無限ループになる」 で選択肢を絞れます。トレースは最後の確認用に取っておけば十分です。