CodeUp / Recursion(재귀) / 1929번 / 우박수(3n+1) - reverse / C++

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

 

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

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

3. nn이 짝수이면 n2n2를 한다.

4. 이 nn이 11이 될때까지 2 32 3과정을 반복한다.

 

예를 들어 55는 55 → 1616 → 88 → 44 → 22 → 11 이 된다.

 

그런데 이번에는 이 순서의 역순을 출력하고자 한다.

즉, 11 22 44 88 1616 55 가 출력되어야 한다.

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

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

 

금지 키워드 : for while goto

 

입력

자연수 nn이 입력된다.(1<=n<=10,000,000)(1<=n<=10,000,000)

 

출력

3n+13n+1의 과정을 출력한다.

 

입력 예시

5

 

출력 예시

1 2 4 8 16 5

 

#include <iostream>
using namespace std;

void recursion(int k) {
	if (k == 1) {
		cout << k << endl;
		return;
	}

	if (k % 2 == 0) recursion(k / 2);
	else recursion(3 * k + 1);

	cout << k << endl;
}

int main() {
	int k;
	cin >> k;
	
	recursion(k);
}