再帰的に定義される関数について

Question

今秋の基本情報技術者試験を受験するにあたって、表題の問題が全く理解できません。
回答の解説を読んでも、なぜそうなるのかがわかりません。
どなたか、解説が可能であればどうぞよろしくお願いいたします。

---

自然数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

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

Answer 1

●ちょっと回答を詳しく書き直してみました。

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

f(5)＝5＋f(4)←f(4) が不明

f(4)が不明のため
これではf(5)の具体的な値がわかりません。
とりあえず f(4)を計算します。

f(4)＝4＋f(3) ←f(3) が不明

まだ具体的な値がわからないので
f(3)，f(2)と具体的な数値が定まるまで計算します。

f(3)＝3＋f(2) ←f(2) が不明
f(2)＝2＋f(1) ←f(1) が不明
f(1)＝1←定まった!

f(1)が定まったのでf(2)が計算できます。
f(2)＝ 2 ＋ f(1)
＝ 2 + 1
＝ 3 ←定まった!

f(2)が定まったので
同様に f(3),f(4),f(5)と計算できます。

f(3)＝ 3 ＋ f(2)
＝ 3 + 3
＝ 6 ←定まった!

f(4)＝ 4 ＋ f(3)
＝ 4 + 6
＝ 10 ←定まった!

f(5)＝ 5 ＋ f(4)
＝ 5 + 10
＝ 15 ←定まった!

長い道のりを経てf(5)の答えが出ました

ちなみに数列の漸化式の考えを知っていれば
問題のようなプログラムは
f (n)：if n≦1 then return A else return B＋f(n－1)
初項：A 漸化式：a(n) = B＋a(n－1) で表される数列
(この場合は階差数列)のn番目の値a(n)を求めよ
という問題と同等と考えれば解き易いです

なのでこの場合は
初項：1 漸化式：a(n) = n＋a(n－1)
として簡単に計算できます
a(1) = 1
a(2) = 2+1 = 3
a(3) = 3+3 = 6
a(4) = 4+6 = 10
a(5) = 5+10 = 15

Comments

[nekomura]

e-cude様
わかりやすい回答をありがとうございました。
おかげさまで理解することが出来ました。

Answer 2

簡単にするために、f(2)を渡すことにします。
※下記の式は質問の式を説明しやすい様に変形したものです。
※丸数字は呼ばれる順番です。
f (n)：//①④
if n≦1//②⑤
then return 1 //⑥
else
return n + f(n－1)//③⑦
①:f(2)が呼ばれます。
②:2≦1は成り立たないため③へ
③:2 + f(2-1)となります、ここでf(2-1)の計算が終わってないので処理が続きます。
④:f(2-1)つまりf(1)が実行されます。
⑤:1≦1は成り立つので⑥へ
⑥:f(1)は結果として、1を返します。
⑦:ここで、③では2 + f(1)だったものが、⑥の結果を受けて2+1=3となります。
f(5)では説明が長くなるので、f(2)についてですが説明しましたが。長くなっただけで内容は同じ手順です。

Comments

[nekomura]

yona様
ご回答に感謝いたします。

簡単にわかるように数字を変えて解説いただきありがとうございます。
あまり表題の解説はネットにないので本当に助かります。

Answer 3

"nが1以下のときは1"・・・問題自体にも問題がありそうです。
・・・ｎ＞１という条件付いてないですか？
”f(n)は，nが1以下のときは1，そうでないならn”ならば
f(5)=5
f(4)=4
f(3)=3
f(2)=2
f(1)=1
になる事は分かりますか？
・・・で、本題ですが、再起というのは関数の中で自分自身を呼び出す事です。

f(5)のとき関数f()の中で行われるのは、5+f(n-1=4)ですよね？
次はf(4)だけを考えればf(4)では4+f(n-1=3)が実行されますね？
以下同様にf(3),f(2),f(1)となります。
実行順序は
f(5)
  f(4)
    f(3)
      f(2)
        f(1)←１になったら終了
      f(2)終了
    f(3)終了
  f(4)終了
f(5)終了

Comments

[nekomura]

cateya様
ご回答に感謝いたします。
ｎ＞１という条件
＞下記URLから引用したのですが特に見当たりませんでした。。。

http://itpro.nikkeibp.co.jp/article/COLUMN/20090707/333376/

これからご回答を熟読して理解を深めていきたいと思います。
ありがとうございました！

[n0tzschk]

横から失礼します。ｎ＞１という条件は「自然数ｎ」という部分に含まれていると思います。

[nekomura]

n0tzschk様
なるほど！
ありがとうございます。

[eripong]

自然数なので、n > 1 でなく、 n >= 1では？
n > 1という条件があると、f(1)が定義されなくなってしまいます。

[退会済みユーザー]

この場合簡単に考えるには、関数に１から順に入れて考えた方が分かり易いような。。

f(1)の場合、if n <= 1 の結果は真なので 1を返します。戻り値は 1。
f(2)の場合、if n <= 1 の結果は偽なので 2+f(1)の結果を返しますが、f(1)の結果は既に判ってますね。そう 1です。つまり2+1の結果を返します。戻り値は 3。

f(3)以降も基本的にf(2)と同じです。3+f(2)の結果が返ってきます。戻り値は 6。
※ f(2) = 3 ですので。

f(4) = 4+f(3)
f(5) = 5+f(4) の結果も同じ要領です。
これを逆から考えられるようになればバッチリなんですけど、これも慣れですかね。

それから、条件として「１以下」と「２以上」で処理が異なっていて、「１以下」が特別な条件になりますから、分類として「繰り返し行う処理と、特別な条件での処理」に分けて２通りを意識する必要があります。（特別な条件の方は "終了条件" とも呼ばれます。）

小さい処理を何度でも繰り返す操作をイメージできれば自然と答えが出てくるので、（操作が正しいかについては計算前後で確認が必要ですが）ここでは疑問を感じるよりもまず先に機械的に計算することが肝心かと。