基本情報技術者 予想問題｜B 第71問

解説

fib(n)は、n≦1のときnをそのまま返し、それ以外は fib(n-1) + fib(n-2) を返すフィボナッチ数列の再帰関数である。小さい方から順に値を積み上げると、fib(0)=0、fib(1)=1、fib(2)=0+1=1、fib(3)=1+1=2、fib(4)=1+2=3、fib(5)=2+3=5、fib(6)=3+5=8 となり、イの8が正解である。ウの13はfib(7)、エの21はfib(8)、アの5はfib(5)であり、数列の数え始めの位置を誤ると選んでしまう値である。本問の鍵は基底条件が「n≦1でnを返す」、すなわちfib(0)=0、fib(1)=1から始まる点で、これを確認せずに思い込みで数えると1項ずれる。再帰問題ではまず基底条件の値を確かめてから展開する、小さいnから表を作って積み上げる、という2つの定石を徹底したい。