C言語で再帰関数 f を次のように定義するとき、 関数呼び出し f(2,1)の返す値
として正しいものはどれか。
int f(int x, int y) {
if (x == 0) return y + 1;
else if (y == 0) return f(x - 1、1);
else return f(x - 1, f(x, y - 1));
}
① ４
② ５
③ ６
④ ７
⑤ ８
if (x == 0) return y + 1; ・・・(1)
else if (y == 0) return f(x - 1、1); ・・・(2)
else return f(x - 1, f(x, y - 1)); ・・・(3)
とすると、
f(2,1)
=f(2-1, f(2,1-1)) = f(1,f(2,0)) ・・・(3)より
=f(1,f(2-1,1)) = f(1,f(1,1)) ・・・(2)
=f(1,f(1-1,f(1,1-1))) = f(1,f(0,f(1,0))) ・・・(3)
=f(1,f(0,f(1-1,1)))=f(1,f(0,f(0,1))) ・・・(2)
=f(1,f(0,1+1))=f(1,f(0,2)) ・・・(1)
=f(1,2+1)=f(1,3) ・・・(1)
=f(1-1,f(1,3-1))=f(0,f(1,2)) ・・・(3)
=f(0,f(1-1,f(1,2-1)))=f(0,f(0,f(1,1))) ・・・(3)
=f(0,f(0,f(1-1,f(1,1-1))))=f(0,f(0,f(0,f(1,0)))) ・・・(3)
=f(0,f(0,f(0,f(1-1,1))))=f(0,f(0,f(0,f(0,1)))) ・・・(2)
=f(0,f(0,f(0,1+1))))=f(0,f(0,f(0,2)))) ・・・(1)
=f(0,f(0,2+1))=f(0,f(0,3)) ・・・(1)
=f(0,3+1)=f(0,4) ・・・(1)
=4+1 ・・・(1)
=5
【補足】
f(2,1)=f(1,3)=f(0,4)=5
f(1,2)=f(0,3)=4
f(2,0)=f(1,1)=f(0.2)=3
f(1,0)=f(0,1)=2
EXCELのマクロのご相談なら ファーストマクロ へ
タグ：再帰関数
