平成24年度 秋期 午前 問7

✓ これが正解イ4

解説

足し算に落ちた呼出しだけを数えます。

数えるのは加算の回数であって、求まる値ではありません。定義を見ると、x が 2 より小さいときは 1 を返して終わりなので、そこでは足し算が起きません。x が 2 以上のときだけ、二つの呼出しの結果を足します。つまり加算の回数は、x が 2 以上で呼ばれた回数と一致します。そこで呼出しを木にして追います。g(4) は g(3) と g(2) を呼び、g(3) は g(2) と g(1) を呼び、g(2) は g(1) と g(0) を呼びます。x が 2 以上で呼ばれたのは、g(4) が一度、g(3) が一度、そして g(2) が二度です。g(2) が二度あるのは、g(4) から呼ばれるものと g(3) から呼ばれるものが別々に計算されるからで、ここが再帰の無駄にあたります。合わせて 4 回が答えになります。値のほうも出しておくと、g(0) と g(1) が 1、g(2) が 2、g(3) が 3、g(4) が 5 となり、これはフィボナッチ数列です。値と回数はどちらも小さな整数になるので、設問がどちらを聞いているかを先に確かめてください。

ほかの選択肢はなぜ違うのか

• ア3：一度計算した結果を覚えておいて使い回すと、足し算をする呼出しは三つで済みます。定義どおりに展開すると引数が 2 のものが二度別々に計算されるので、その分だけ足りません。
• ウ5：これは g(4) の値そのものです。数列の何番目かを求めた結果であって、途中で何度足したかではありません。設問が回数を問うている点を読み飛ばすとここに落ちます。
• エ7：終わりの条件を、x が 1 より小さいときと読み替えて数えるとこの回数になります。引数が 1 のところでも足し算に落ちるため、展開が一段深くなって回数が増えます。