[재귀 함수] 순서대로 또는 역순으로 출력하기

재귀 함수란 자기 자신을 호출하여 반복하는 것을 말한다. 

의미없는 반복이 되지 않으려면 대상을 더 작은 단위로 나누어서 재귀호출을 해야 하고,

반복이 종료되는 시점을 지정해주어야 한다. 

 

EX1)  1부터 n까지, 또는 n부터 1까지 출력하는 것을 재귀함수를 이용해서 출력해보자.

public class RecursiveExample {

    public static void recursive(int n) {
        if(n == 0) return; // 재귀 탈출 조건
        recursive(n - 1); // n을 1씩 줄여나가며 재귀적으로 자기자신 호출
    }

    public static void main(String[] args) {
        recursive(3);
    }
}

 

n이 주어지고, n에서 1을 뺀 값을 재귀적으로 호출하는 방식으로 반복하게 된다. 

출력 순서가 1부터든 n부터든 어쨌든 1까지만 출력해야 하니 탈출 조건을 지정해준다.

if(n == 0) return;

n 이 0이 되면 return 되어 함수가 종료되고 더이상 재귀호출을 하지 않는다. 

이전의 재귀 함수들에서도 재귀 호출 이후 더이상 실행될 코드가 없으므로  모든 재귀 함수가 순차적으로 종료될 것이다. 

 

이제 출력을 어떻게 할지 생각해보자. 

재귀 호출 이전에 출력하고 다음 재귀 호출을 하도록 한다면?

public class RecursiveExample {

    public static void recursive(int n) {
        if(n == 0) return; // 재귀 탈출 조건

		System.out.print(n + " "); // 재귀 호출 이전에 n 출력 => 재귀함수가 호출된 순서대로 출력
        recursive(n - 1); // n을 1씩 줄여나가며 재귀적으로 자기자신 호출
    }

    public static void main(String[] args) {
        recursive(3);
    }
}

// 출력 결과
3 2 1

다음 재귀 호출을 하기 전에 자기 자신을 출력하고 다음 재귀 호출을 하게 된다. 

현재는 n 부터 n을 1씩 줄여가며 재귀호출을 하고 있으므로, n 부터 (n - 1) (n - 2) ... 이런 순서로 출력이 될 것이다. 

그러므로 recursive(3)을 메인에서 호출하면 출력 결과는 3 2 1 이 된다. 

결과적으로 n 부터 역순 출력이 된 셈.

 

그렇다면 순서대로 출력이 하고 싶다면 어떻게 해야 할까?

순서대로 출력을 하겠다는 것은 마지막으로 호출되는 재귀함수에서의 n(== 1) 부터 출력하겠다는 의미이다. 

이는 재귀 호출을 한 이후에 출력을 하도록 하면 된다. 

스택 구조로 재귀 호출 함수가 처리되기 때문에 가장 마지막에 호출된 재귀부터 처리되고 처리되는 방식이다.

그러므로 재귀 호출 코드 다음에 출력 코드를 작성하면,

모든 재귀가 호출되어 탈출조건에 도달하고 가장 마지막 재귀 호출 함수부터 재귀 호출 다음 코드로 넘어가게 될 것이다. 

그러면 가장 마지막에 호출된 재귀함수의 n 부터 출력되는 결과가 나온다. 

public class RecursiveExample {

    public static void recursive(int n) {
        if(n == 0) return; // 재귀 탈출 조건


        recursive(n - 1); // n을 1씩 줄여나가며 재귀적으로 자기자신 호출
		System.out.print(n + " "); // 재귀 호출 이후에 n 출력 => 마지막 재귀함수부터 출력 
    }

    public static void main(String[] args) {
        recursive(3);
    }
}

// 출력 결과
1 2 3

 

 

EX2) 재귀를 이용하여 10진수 n을 이진수로 출력해보자.

10진수를 2진수로 변환하려면 주어진 수를 계속헤서 2로 나누어 몫이 0이 될 때까지 나눈 후,

그 때까지의 나머지를 거꾸로 이어붙이면 된다. 

 

• 재귀 탈출 조건 : n == 0이 되었을 때
• 다음 재귀 호출할 수 : n/2
• 가장 마지막의 나머지가 가장 먼저 와야 하므로 재귀호출 이후에 나머지를 출력하도록 한다. 

public class RecursiveExample2 {
    public static void recursive(int n) {
        // 계속 n 을 2로 나눈 나머지를 거꾸로 출력해야 한다.
        // n 을 2로 나눈 몫이 0이 되면 재귀 종료

        if(n == 0) return;
        else {
            recursive(n/2);
            System.out.print(n%2);
        }
    }

    public static void main(String[] args) {
        recursive(11);
    }
}

// 출력 결과
1011