JAVA백준 문제풀이 (16) 17478:재귀함수가 뭔가요?

 

 

개발에 입문했다면 누구나 한 번쯤 들어봤을만한 재귀 드립이다.

혹시 재귀 자체가 잘 이해가 되지 않는다면 아래 팩토리얼 문제 풀이를 읽어보도록 하자. 30초만에 다 읽을 수 있다.

(https://7357.tistory.com/131)

 

아마 대부분의 초보자들은 재귀의 개념 자체를 이해하지 못한다기보다는 나처럼 재귀가 익숙하지 않아 뭔지 알지만 머리에 쉽사리 그려지지 않는 상태일텐데, 딱 그 정도 레벨에서 직접 화면에 그려가며 재귀랑 친해지기 위한 문제인 것 같다.

 

맨날 숫자랑 영어, 연산기호만 보다가 갑자기 장문의 한글을 보니 깜짝 놀라고 당황스러울 수도 있지만 재귀 문제인 것을 알고 있으니 침착하게 기저 조건을 찾아보자.

* 기저 조건 : 재귀 함수가 가장 작은 단계까지 가서 더 이상 쪼개지지 않고 종료되는 재귀 호출.

 

________"재귀함수가 뭔가요?"
________"재귀함수는 자기 자신을 호출하는 함수라네"
________라고 답변하였지.

 

이 부분에서 반복이 종료되고 있는 것을 확인할 수 있다.

그러면 재귀함수 메서드에 해당 코드를 먼저 조건식으로 작성하면 된다.

 

if ( num == 0 ) {
    System.out.println("\"재귀함수가 뭔가요?\"");
    System.out.println("\"재귀함수는 자기 자신을 호출하는 함수라네\"");
    System.out.println("라고 답변하였지.");
}

 

참고로 이런 문제는 직접 한 글자씩 타이핑하겠다고 헛짓하지 말고 무조건 복사 붙여넣기하자. 띄어쓰기 하나 틀렸는데 못 찾고 난 분명히 다 맞았거늘 왜 통과 안되냐고 분노의 맞왜틀을 외치게 될 수 있다.

그렇다. 내 얘기다.

 

쩝.. 얘기가 잠깐 옆으로 샜는데 대견스럽게도 벌써 기저조건을 찾아냈으니 나머지는 너무 쉽다.

재귀의 특징이 무엇인가?

재귀함수(num) { return 재귀함수(num-1) }라는 메서드에 num=4를 대입해서 호출한다면 재귀함수(4)가 (3)을 부르고 (3)이 (2)를 부르고..

결과적으로 재귀함수(0)이라는 메서드가 가장 먼저 결과를 반환하고 (1) (2) (3) (4)로 다시 거슬러 올라오며 결과를 반환하는 것이 재귀함수라는 것을 우리는 아주 잘 알고 있다. ( 기저 조건이 0일 경우의 이야기이다. )

 

이제 문제로 돌아가 가장 먼저 출력되는 문장을 찾아보자

"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."

가장 처음 출력되는 값은 underline이 없고 반복될수록 unerline이 추가되고 있는 것을 알 수 있다.

가장 처음 출력되는 값? 재귀함수(0)

그렇다면 재귀함수의 인자 값 (0)이 증가할 수록 그에 비례해서 underline이 추가되야한다는 사실을 알 수 있다.

혹시 이 문제를 혼자 풀지 못해 이 글을 읽으러 온 사람이 있다면 여기까지 읽고 직접 풀어보자.

 

여기까지 읽었는데 코드를 작성하지 못한다면 알고리즘 이해 부족이 아니라 코딩 능력이 부족한 것이다.

다양한 코드를 작성해보자!

 

 

 

정답 ⬇️

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    // underline 횟수 카운트용
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int inputNum = Integer.parseInt(br.readLine());
        // 반복되지 않는 첫 문장
        System.out.println("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.");
        printRecursion(inputNum, count);
    }

    public static void printRecursion(int num, int cnt) {
        if ( num == 0 ) {
        // 기저 조건 (재귀 함수 호출이 종료되는 지점)
            System.out.println(printUnderline(cnt) + "\"재귀함수가 뭔가요?\"");
            System.out.println(printUnderline(cnt) + "\"재귀함수는 자기 자신을 호출하는 함수라네\"");
            System.out.println(printUnderline(cnt) + "라고 답변하였지.");
        }
        else {
            System.out.println(
                    printUnderline(cnt) + "\"재귀함수가 뭔가요?\"\n" +
                            printUnderline(cnt) + "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n" +
                            printUnderline(cnt) + "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n" +
                            printUnderline(cnt) + "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\""
            );
            // 이 부분이 헷갈릴 수 있다. 그러면 그냥 count를 인자로 넣지 말고 밖으로 꺼내서 count+=1이라고 생각해보자.
            printRecursion(num - 1, ++count);
            System.out.println(printUnderline(cnt) + "라고 답변하였지.");
        }
    }
    
    // underline 그리기를 담당하는 메서드(형태는 중요하지 않으니 그냥 원하는대로..)
    public static String printUnderline(int cnt) {
        String underline = "____";
        String temp = "";
        for ( int i=0; i<cnt; i++ ) {
            temp+=underline;
        }
        return temp;
    }
}

 

 

아마도 printRecursion(num-1)까지는 이해가 되는데 ++count에서 혼란스러워하는 사람이 분명히 있을 것 같다.

printRecursion(0)까지 가는 과정에서 ++count가 계속 호출되는데 왜 underline이 증가하지 않지..?

다시 생각해보자. 재귀함수에서 가장 먼저 값을 반환하는 것은 누구인가?

이걸 생각하면 확실하게 이해가 될 것이다.