問題

問８　自然数nに対して，次のように再帰的に定義される関数f(n)を考える。f(5)の値はどれか。

f (n)：if　n≦1　then　return　1　else　return　n＋f(n－1)

ア　6
イ　9
ウ　15
エ　25

テクノロジ系>基礎理論>アルゴリズムとプログラミング>アルゴリズム

解説と解答

　関数f(n)の定義を言葉に置き換えると，「f(n)は，nが1以下のときは1，そうでないならn＋f(n－1)となる」となります。

　実際にf(5)を計算してみましょう。

f(5)＝5＋f(4)

　次に，f(4)を計算します。

f(4)＝4＋f(3)

　同様に，f(3)，f(2)，f(1)を計算します。

f(3)＝3＋f(2)
f(2)＝2＋f(1)
f(1)＝1

よって，f(5)は以下のように計算できます。

f(5)＝5＋f(4)
　　＝5＋4＋f(3)
　　＝5＋4＋3＋f(2)
　　＝5＋4＋3＋2＋f(1)
　　＝5＋4＋3＋2＋1
　　＝15

以上より，正解は，選択肢ウです。