再帰関数の戻り値を順に求めるには？
基本情報技術者試験 令和元年度秋期 午前 問11 ／ アルゴリズムとプログラミング › アルゴリズム
過去問にチャレンジ
自然数nに対して，次のとおり再帰的に定義される関数f(n)を考える。f(5)の値はどれか。 f(n): if n≦1 then return 1 else return n＋f(n－1)
- ア
6
- イ
9
- ウ
15
- エ
25
会話形式の解説
講師この問題では、再帰関数がどこで止まり、そこからどんな値を返すかを確かめます。
受験者f(5)から順に式を広げると、途中の値を見失いそうです。どこから計算すればよいですか。
講師まず停止条件を見ます。nが1以下になったら1を返すので、f(1)=1です。
受験者そこから戻ると、f(2)は2+1で3ですね。
講師そのとおりです。次はf(3)=3+f(2)なので、3+3で6です。
受験者候補に6がありますが、これはf(3)の値で、まだf(5)ではありませんね。
講師はい。f(4)=4+6で10、さらにf(5)=5+10で15です。
受験者9という候補は5+4ですが、f(4)を単に4として扱ってしまった値ですか。
講師そうです。f(4)には、さらに小さいnで計算した戻り値も含まれます。
受験者25は5を5回足した値ですが、呼び出すたびにnが減るので違いますね。
講師はい。加える数は5、4、3、2と減り、最後は停止条件から1が返ります。
受験者つまり、5+4+3+2+1=15なので、正解は15です。
講師再帰計算では、先に停止条件を確認し、小さいnから戻り値を書き出すと、途中で止める間違いを防ぎやすいです。
まとめ
この関数はnが1以下になると1を返します。そこから順に計算すると、f(2)=3、f(3)=6、f(4)=10、f(5)=15です。したがって正解は15です。途中の戻り値で計算を止めず、小さいnから確かめることが大切です。
解答・解説
正解はウです
この問題のテーマ
再帰関数を停止条件までたどり、戻り値を求める問題です。
解き方の考え方
まず n≦1 のときに f(n)=1 を返すことを確認します。そこから順に戻り値を求めると、f(2)=2+1=3、f(3)=3+3=6、f(4)=4+6=10、f(5)=5+10=15 です。したがって、正解であるウの値と一致します。
選択肢ごとの解説
- ×ア 6アの6は f(5) の値ではありません。f(4) まで計算した結果が10なので、最後に5を加える必要があります。
- ×イ 9イの9は5と4だけを加えた値です。f(4) はそこで止まらず、さらに小さい n の戻り値を含むため、9では足りません。
- ○ウ 15ウの15が、停止条件までたどって得られる f(5) の値です。5から1までを一度ずつ加えた結果にも一致します。
- ×エ 25エの25は5を5回加えた値です。この再帰式では n を1ずつ減らして加えるため、各回で加える数は同じではありません。
POINT
- 再帰関数では、まず呼出しが止まる条件を確かめます。
- nが1より大きい間は、現在のnと一つ前の戻り値を加えます。
- 途中の戻り値を小さいnから順に求めると、計算を確かめやすくなります。