トップ過去問一覧応用情報技術者 平成24年・秋 > 問7
問7

次の関数g(x)の定義に従ってg(4)を再帰的に求めるとき,必要な加算の回数は幾らか。

 

g(x) = if x<2 then 1

                   else g(x-1)+g(x-2)

○正解
×不正解

3

4

5

7

解説

4

関数g(x)は、自分で自分を呼び出す再帰関数です。再帰関数を定義する際は、再帰を止める条件を設定することが重要です。さもないと際限なく再帰呼び出しが発生してしまいます。

 

最初に,定義の

g(x) = g(x-1) + g(x-2)

に従って展開すると以下の通りとなります。

g(4) = g(3) + g(2)

= g(2) + g(1) + g(1) + g(0)

= g(1) + g(0) +g(1)  +g(1)  +g(0)

=   1     1      1  +   1   +  1

 

よって,必要な加算の回数は4回です。

無料学習システムはこちら
→間違えた問題を繰り返し学習
→分野別学習
→模擬試験モード
デモサイト
無料ユーザ登録

問題文や解説文の内容の正確性については、できるかぎりチェックをしていますが、間違いがある可能性があります。 十分ご注意の上、参考までにご利用ください。