재귀함수를 이용한 이진수 출력

설명

10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요. 단 재귀함수를 이용해서 출력해야 합니다.

 

입력

첫 번째 줄에 10진수 N(1<=N<=1,000)이 주어집니다.

 

출력

첫 번째 줄에 이진수를 출력하세요.

 

예시 입력 1 

11

 

예시 출력 1

1011

 

문제 해결

 

DFS(n) 함수가 호출되며, n을 2로 나누는 재귀 호출을 계속 하며 2진수로 변환하는 과정이다.

n이 0이 될때까지 재귀함수를 수행하면 되는데, n이 0이면 함수는 반환된다. 

나머지가 나온 순서는 1101이지만 1011로 출력해야하므로 앞 문제에서 설명한 스택프레임 이용해서 풀어보자.

 

System.out.println();의 호출이 DFS(n/2) 보다 이후에 있기에 아래와 같이 동작함.
           

• • DFS(11) 호출 → 11 % 2 = 1 (출력되지 않음, 스택에 저장됨)
  • DFS(5) 호출 → 5 % 2 = 1 (출력되지 않음, 스택에 저장됨)
  • DFS(2) 호출 → 2 % 2 = 0 (출력되지 않음, 스택에 저장됨)
  • DFS(1) 호출 → 1 % 2 = 1 (출력되지 않음, 스택에 저장됨)
  • DFS(0) 호출 → 함수 반환 시작 :
  • DFS(1)이 반환되며, 스택 프레임에 저장된 1 출력
  • DFS(2)이 반환되며, 스택 프레임에 저장된 0 출력
  • DFS(5)이 반환되며, 스택 프레임에 저장된 1 출력
  • DFS(11)이 반환되며, 스택 프레임에 저장된 1 출력

 

 

최종 코드

 

import java.util.Scanner;

public class P02_이진수출력_재귀 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        DFS(N);
    }

    public static void DFS(int n) {
        if(n==0) return;
        else {
            DFS(n/2);
            System.out.print(n%2);
        }
    }
}