자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Recursive_이진수 출력_재귀)

 

 

2. 이진수 출력(재귀)

예시 입력 1 

11

예시 출력 1

1011

10진수를 2진수로 바꿀때 나눈 나머지가 2진수가 됩니다.

 

public class Main {

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

    public static void main(String[] args) {
        Main T = new Main();
        T.DFS(11);
    }
}

11 5 2 1

목표는 몫이 아니라 나머지이기 때문에 아래처럼 코드를 수정해줍니다. 또한 1011순서로 출력되기 위해 print함수를 DFS호출하는 아래에 넣어줍니다.

public class Main {

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

    public static void main(String[] args) {
        Main T = new Main();
        T.DFS(11);
    }
}

1 0 1 1

 

 

이런 내용을 스택프레임으로 어떻게 동작하는지 다시 확인해보겠습니다.

 

하나 씩 자기 할일을 끝나면 pop이 되고 출력하면서 1011이 반환됩니다, 스택이 비면서 Main으로 복귀되면서 끝납니다.