이진수 출력(재귀)

재귀를 이용하여 이진수 출력하는 법을 알아보자. 11의 이진수를 출력하는 코드이며 결과값은 1011이 나와야 한다.

코드

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

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

 

설명

우선 자바는 함수 호출 시 스택 영역에 프레임이라는 것이 생긴다. 해당 프레임에는 함수의 실행 정보나 지역변수 등이 담겨 있다. 그럼 위의 코드를 예시로 스택에 어떤식으로 쌓이는지 보면 아래 그림과 같이 쌓이게 된다.(메인 프레임은 제외했다.)

메인에서 DFS(11)을 호출하며 해당 프레임이 들어가게 되며 로직을 수행하다가 자기 자신을 다시 한번 호출하며 매개변수 n을 2로 나눈 몫을 넘긴다. 그림에서와 같이 DFS(5)를 호출한다고 보면된다. 이때 DFS(11)의 프레임에는 몇번째 라인까지 수행했는지의 정보도 담겨있다. 

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

위의 코드를 다시 가져와서 보면 예시로 if문 라인이 1 else 라인이 2 DFS(n / 2)가 3이면 3번째라인까지 수행했다라는 정보가 들어가있다고 보면 된다. 

 

그 다음 DFS(5) 메소드 또한 실행하면서 DFS(2)를 호출하게 되며 위의 순서대로 DFS(1) - DFS(0) 프레임들이 스택에 순차적으로 쌓인다. 그리고 제일 마지막 DFS(0)의 경우 n == 0의 조건을 만족하며 retrun을 하게 되는 순간 해당 프레임은 스택에서 빠지게 된다. 그럼 아래 그림과 같은 상태가 된다. 

DFS(0)이 빠지게 되면서 DFS(1)을 다시 실행시키게 되며 DFS(1)은 3번째 라인까지 수행했다는 정보가 남아있기 때문에 그 이후의 라인을 실행하며 n % 2의 값을 출력하고 종료한 후 스택에서 빠진다. 이후 순차적으로 DFS(1)이 출력하고 빠지듯이 스택에 쌓여있던 프레임들이 n % 2 라인을 실행하고 빠지며 종료된다. 

 

이렇게 재귀 원리를 사용하여 10진수의 2진수 값을 출력할 수 있다. 

---

*인프런 - 자바 알고리즘 문제풀이 입문