次の関数f(n，k)がある。
f(4，2)の値は幾らか。
f(n，k)＝
1 (k＝0)，
f(n－1，k－1)＋f(n－1，k) (0＜k＜n)，
1 (k＝n)。
正答4
解説
正解は4です。
再帰的に定義された関数の値を求める問題です。
f(n，k)はk＝0またはk＝nのとき1、それ以外はf(n－1，k－1)＋f(n－1，k)です。
これはパスカルの三角形と同じ規則で、二項係数nCkを表しています。
【計算】
f(2，1)＝f(1，0)＋f(1，1)＝1＋1＝2です。
f(3，1)＝f(2，0)＋f(2，1)＝1＋2＝3です。
f(3，2)＝f(2，1)＋f(2，2)＝2＋1＝3です。
f(4，2)＝f(3，1)＋f(3，2)＝3＋3＝6です。
【選択肢別解説】
1：× 3はf(3，1)やf(3，2)の値です。
f(4，2)はこの2つを足すので3にはなりません。
2：× 4はf(4，1)の値です。
kを取り違えるとこの値になります。
3：× f(4，2)は、f(3，1)＝3とf(3，2)＝3の和です。
途中の値を1つ取り違えると5のような値になりますが、定義どおりに計算すると5にはなりません。
4：○ 定義どおりに展開すると、f(4，2)＝3＋3＝6です。
二項係数4C2＝6とも一致します。
【ポイント】
再帰関数の問題は、小さい引数から順に値を求めて表にすると計算ミスを防げます。
この形の漸化式は二項係数（組合せの数）を表すと覚えておくと便利です。