基本情報技術者試験 - 令和5年1月修了 - 問8

答え ： エ
分野 ： テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › アルゴリズム
解説 ：
関数 f(n，k) は，kが0またはnと等しいときには常に1を返し，それ以外の場合は f(n-1，k-1) と f(n-1，k) の和を返すという再帰的な定義になっています。この定義はパスカルの三角形における二項係数の計算方法と同じ構造を持っています。

f(4，2) を求めるには，f(3，1) と f(3，2) の和を計算する必要があります。さらに f(3，1) は f(2，0) と f(2，1) の和，f(3，2) は f(2，1) と f(2，2) の和というように，再帰的に値をさかのぼって計算していきます。

最終的に k=0 または k=n となる場所まで分解すると，全て1という値にたどり着き，それらを足し合わせていくことで f(4，2) の値が6であることが求まります。

これは二項係数で表すと₄C₂の値に相当し，実際にこれを計算しても6になることが確認できます。他の選択肢は再帰の展開を一部誤った場合に出てくる値です。再帰関数の問題では，木構造を描いて値をさかのぼりながら丁寧に計算することが重要です。