次のC言語のプログラムを実行したときに出力される結果はどれか。
#include <stdio.h>
int p(int x, int y) {
if (x > y) return p(x - y, y);
if (x < y) return p(y - x + 2, x);
return x;
}
int main() {
printf("%d", p(5, 6));
}
① 1 ② 2 ③ 3 ④ 4 ⑤ 5
答え
①
解説
設問のプログラムは、関数pの中で、関数pが呼び出される再帰的な構造になっています。
- x > y → p(x - y, y)で再帰処理
- x < y → p(y - x + 2, x)で再帰処理
- a, b以外(x = y) → xを返す
main関数では、関数p(5, 6)の結果を出力しているので、実際に値を入れて順に見て行きます。
1回目
x < y なので b → p(6 - 5 + 2, 5) → p(3, 5)
2回目
x < y なので b → p(5 - 3 + 2, 3) → p(4, 3)
3回目
x > y なので a → p(4 - 3, 3) → p(1, 3)
4回目
x < y なので b → p(3 - 1 + 2, 1) → p(4, 1)
5回目
x > y なので a → p(4 - 1, 1) → p(3, 1)
6回目
x > y なので a → p(3 - 1, 1) → p(2, 1)
7回目
x > y なので a → p(2 - 1, 1) → p(1, 1)
8回目
x = y なので x = 1 を返す
よって出力される結果は 1 になります。