次の関数f(n, k)がある。
f(4, 2)の値は幾らか。
f(n, k) = 1 (k=0)，
f(n, k) = f(n-1, k-1) + f(n-1, k) (0<k<n)，
f(n, k) = 1 (k=n)。
正答4
解説
正解は4です。
関数 f(n, k) は再帰的に定義されています。
k=0 または k=n のときは1を返し、それ以外は二つの f の和になります。
【計算】
f(4, 2) = f(3, 1) + f(3, 2) です。
f(3, 1) = f(2, 0) + f(2, 1) です。
f(2, 0) = 1（k=0）です。
f(2, 1) = f(1, 0) + f(1, 1) = 1 + 1 = 2 です。
したがって f(3, 1) = 1 + 2 = 3 です。
f(3, 2) = f(2, 1) + f(2, 2) = 2 + 1 = 3 です。
よって f(4, 2) = 3 + 3 = 6 です。
【選択肢別解説】
1：× 3は f(3, 1) や f(3, 2) の値です。
f(4, 2) はその二つの和です。
2：× 4にはなりません。
k=0 と k=n の場合を1とする定義どおりに展開すると6になります。
3：× 5にはなりません。
f(3, 1) と f(3, 2) はどちらも3なので、和は6です。
4：○ 上の計算のとおり、f(4, 2) = 6 です。
【ポイント】
この関数は、n個からk個を選ぶ組合せの数（二項係数）を求めるパスカルの三角形の漸化式です。
実際に 4個から2個を選ぶ組合せは 4×3÷2 = 6 通りで、結果と一致します。