문제

콜라츠의 추측, 3n+1 문제, 우박수 문제라고 불리는 이 문제는 다음과 같다.

1, 어떤 자연수 n이 입력되면,

2. n이 홀수이면 3n+1을 하고,

3. n이 짝수이면 n/2를 한다.

4. 이 n이 1이 될때까지 2, 3과정을 반복한다.

예를 들어 5는 5 → 16 → 8 → 4 → 2 → 1 이 된다.

이 처럼 어떤 자연수 n이 입력되면 위 알고리즘에 의해 1이 되는 과정을 모두 출력하시오.

이 문제는 반복문 for, while 등을 이용하여 풀수 없습니다.

IO example : 입력

5

출력

5
16
8
4
2
1

풀이

# include <stdio.h>

void p(int a)
{
	printf("%d\n",a);
	if(a == 1)	
		return;
	
	if(a%2 == 1)
		p(a*3+1);
	else	
		p(a/2);
}

int main(){
	int n;
	scanf("%d",&n);
	p(n);
	return 0;
}

1. n이 짝수라면, n을 2로 나눈다.
2. n.이 홀수라면, n에 3을 곱하고 1을 더한다.
3. n이 1이 되면 연산을 중단한다.

재귀함수 p에서 a가 1이면 return하고 종료하고, a를 2로 나누었을 때 나머지가 1이면 p(a*3+1)로 재귀함수 재호출하고, 아니면 p(a/2)로 재귀함수를 재호출한다.