自然数nに対して，次のように再帰的に定義される関数f(n)を考える。
f(5)の値はどれか。
f(n)：if n≦1 then return 1 else return n+f(n-1)
正答3
解説
正解は3です。
再帰的に定義された関数の値を、定義に従って順に展開して求める問題です。
n が1以下のときは1を返し、それ以外は n に f(n－1) を足した値を返します。
【計算】
f(5)＝5＋f(4) です。
f(4)＝4＋f(3) です。
f(3)＝3＋f(2) です。
f(2)＝2＋f(1) です。
f(1) は n≦1 なので 1 を返します。
逆にたどると、f(2)＝3、f(3)＝6、f(4)＝10、f(5)＝15 です。
【選択肢別解説】
1：× 6 は f(3) の値です。
f(5) までさらに4と5を足す必要があります。
2：× 9 は、5＋4 で止めた値です。
f(3) 以下の部分も足し続ける必要があります。
3：○ 5＋4＋3＋2＋1＝15 となるので正しいです。
4：× 25 は 5×5 の値です。
この関数は掛け算ではなく、1から n までの和を求めています。
【ポイント】
この関数は 1＋2＋…＋n を求めるもので、f(n)＝n(n＋1)/2 と等しくなります。
再帰の問題は、終了条件（ここでは n≦1）に到達するまで展開してから戻ると確実です。