自然数nに対して，次のとおり再帰的に定義される関数f(n)を考える。
f(5)の値はどれか。
f(n): if n≦1 then return 1 else return n+f(n-1)
正答3
解説
正解は3です。
再帰関数は、自分自身を呼び出して値を求める関数です。
f(n)は、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)まで再帰をたどる必要があります。
2：× 9は、5+4のように途中までしか加えていない値です。
f(1)まで呼び出しを続けると15になります。
3：○ f(5)=5+4+3+2+1=15です。
4：× 25は5×5で、加算ではなく乗算をした値です。
【ポイント】
このf(n)は1からnまでの和を求める関数で、n(n+1)/2と一致します。
再帰の問題は、終了条件まで呼び出しを展開してから、戻りながら値を組み立てると確実です。