[Code Tree] 1까지 나누는 재귀함수

정수 n이 주어졌을 때, n이 짝수면 2로, 홀수면 3으로 나누어 나눈 몫을 취하는 작업을 n에서 1이 될때까지 반복하고 나누는 작업을 거칠때마다 나오는 결과값을 출력하는 프로그램을 재귀함수를 이용하여 작성해보세요.

 

입력 

1 <= n <= 1,000

 

출력

첫 번째 줄에 모든 출력값 사이에 공백을 두고 출력.

 

ex ) 

입력

124

 

출력

124 62 31 10 5 1

 

#include <iostream>

using namespace std;

int main() {

    int n;

    cin >> n;

    while(n){

        cout << n << " ";

        if(n % 2 == 0) n /= 2;

        else n /= 3;

    }

    return 0;

}

 

 

*재귀함수 문제이지만 반복문으로 풀었고 n이 커질 수록 재귀는 피하는 것이 함수 호출 stack을 줄이는 면에서 좋다.

**재귀함수의 경우 N이 매우 커지고 같은 동작을 반복 할 때, DP 문제로 나올 수 있다.

(n이 여러번 주어지고 1까지 가기위해 거치는 숫자의 개수를 구하는 등의 형식으로 변형 가능)