平成21年度 春期 午前 問8
アルゴリズム
関数に関する問題
自然数 n に対して,次のように再帰的に定義される関数 f(n) を考える。f(5) の値はどれか。
〔関数の定義〕
f(n):if n≦1 then return 1 else return n+f(n−1)
- ア6
- イ9
- ウ15
- エ25
答えと解説を見る
✓ これが正解ウ15
解説
1 から 5 までを足すので 15 になります。
この関数は自分自身を呼ぶ形で定義されています。読み方の順序は決まっていて、まず終わりの条件を見つけ、そこまで展開し、最後に戻りながら計算します。定義によれば、引数が 1 以下になったときだけ 1 を返し、それ以外は引数の値と、引数を 1 減らして呼び直した結果との和を返します。そこで 5 から順に 4 、3 、2 と呼び出しをたどると、1 に達したところで止まります。あとは内側から順に足し戻していけば値が定まります。結局この関数は、引数から 1 までの自然数をすべて足し合わせたものを返しており、和の公式を使えば別の道からも同じ値を確かめられます。見分けるときの軸は、終わりの条件を先に押さえてから戻る向きに計算することです。
ほかの選択肢はなぜ違うのか
- ア6:6 を挙げる内容です。展開を途中で切り上げ、引数が 3 のときの値をそのまま答えとした場合に出てきます。定義は引数が 1 以下になるまで呼び直すと述べています。
- イ9:9 を挙げる内容です。呼び出しの展開を二つ目で止め、5 と 4 だけを足した場合に現れます。残りの三つ分の呼び出しが計算に入っていません。
- エ25:25 を挙げる内容です。引数の 5 に 5 を掛けた値、すなわち 5 を 2 乗した値であり、定義に書かれているのは掛け算ではなく、引数と呼び直した結果との足し算です。
出典:平成21年度 春期 基本情報技術者試験 午前 問8(改変:原典の図表をテキストに書き起こした)
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する(メールが開きます)