アルゴリズム(全80問中45問目)
No.45解説へ
自然数nに対して，次のように再帰的に定義される関数ƒ(n)を考える。ƒ(5)の値はどれか。
ƒ(n)：if n≦1 then return 1 else return n＋ƒ(n－1)
ƒ(n)：if n≦1 then return 1 else return n＋ƒ(n－1)
出典：平成21年春期 問 8
- 6
- 9
- 15
- 25
広告
解説
再帰関数は、関数内で自分自身を読み出す構造になっている関数です。
設問の再帰関数 ƒ(n) は以下のような処理を行います。
ƒ(5)
＝5＋ƒ(4) //ƒ(5)=5＋ƒ(4)
＝5＋4＋ƒ(3) //ƒ(4)=4＋ƒ(3)
＝5＋4＋3＋ƒ(2) //ƒ(3)=3＋ƒ(2)
＝5＋4＋3＋2＋ƒ(1) //ƒ(2)=2＋ƒ(1)
＝5＋4＋3＋2＋1 //ƒ(1)=1
＝15
したがって、ƒ(5)の値は15です。
設問の再帰関数 ƒ(n) は以下のような処理を行います。
- 引数nが1以下のとき
- 1を返す
- それ以外の場合
- n＋ƒ(n－1)を返す
ƒ(5)
＝5＋ƒ(4) //ƒ(5)=5＋ƒ(4)
＝5＋4＋ƒ(3) //ƒ(4)=4＋ƒ(3)
＝5＋4＋3＋ƒ(2) //ƒ(3)=3＋ƒ(2)
＝5＋4＋3＋2＋ƒ(1) //ƒ(2)=2＋ƒ(1)
＝5＋4＋3＋2＋1 //ƒ(1)=1
＝15
したがって、ƒ(5)の値は15です。
広告