応用情報技術者 2012年 秋期 午前2 問07

次の関数$g(x)$の定義に従って$g(4)$を再帰的に求めるとき、必要な加算の回数は幾らか。【午前2 解説】

要点まとめ

• 結論：$g(4)$を再帰的に計算する際の加算回数は4回です。
• 根拠：$g(x)$はフィボナッチ数列の定義に似ており、再帰呼び出しごとに加算が発生します。
• 差がつくポイント：再帰呼び出しの展開を正確に追い、加算回数を数えることが重要です。

正解の理由

よくある誤解

解法ステップ

1. $g(4)$を計算するために$g(3)$と$g(2)$を呼び出す。
2. $g(3)$は$g(2)$と$g(1)$を呼び出し、$g(2)$はベースケースで1を返す。
3. 各非ベースケースで加算が1回発生することを確認する。
4. 加算回数を$g(4)$、$g(3)$、$g(2)$の計算時にそれぞれ1回ずつ数え、合計4回とする。

選択肢別の誤答解説

• ア: 3回は加算回数の数え漏れがあるため誤りです。
• イ: 4回は正しい加算回数です。
• ウ: 5回は加算回数を過大評価しています。
• エ: 7回は再帰呼び出しの総数と混同した誤りです。

補足コラム

FAQ