재귀 함수(Recursive Function) - 초급 편

재귀 함수는 처음 알고리즘을 접하는 이들에게는 조금은 머리를 써야하는 챕터이다. 나는 실제로 대학교 2학년 알고리즘 수업 때 처음 재귀 에 대해 수업을 들었는데, 완벽히 이해하는데 추가적인 시간이 필요한 경험이 있어, 기초부터 심화 수준까지 정리해보려고 한다.

다음과 같이 n개의 줄에 걸쳐 5개의 별을 출력하는 문제를 다음과 같이 생각해 볼 수는 없을까?

*****
*****
*****

물론 반복문을 이용하여 충분히 출력할 수 있을 것이다. 하지만 좀 더 쌈박한(?) 방법으로 구해보자.

public static void printStar(int n) { // 1부터 n번째 줄까지 별을 출력하는 함수
    printStar(n - 1);                 // 1부터 n - 1번째 줄까지 출력하는 함수
    System.out.println("*****");      // n번째 줄에 해당하는 별 출력
}

위에 제시된 코드를 통해 재귀함수의 시작을 알리려고 한다
소스 코드를 유심히 보자. 재귀 함수를 처음 접하는 이는 누구든지 당황스러울 것이다.
"printStar라는 함수안에 또 함수가 있네?" 일단 침착하고 제시된 코드를 돌려보자.

안타깝게도... 이 코드를 이용해 printStar(5)를 수행하게 되면, 프로그램이 영영 끝나지 않게 될 것이다. 그 이유는 printStar(5) 함수가 printStar(4)를 부르게 되고, 4는 3을, 3은 2를, ... 계속 무한정 부르게 될 것이기 때문이다. 그래서 재귀함수에서 가장 중요한 요소는 바로 <종료 조건> 이다. 종료조건을 올바르게 설정해줘야만 , 재귀 함수는 올바르게 동작하게 된다.

위 예시에서 n이 1인 경우를 생각해보자. 함수 정의상 1부터 1번째 줄까지의 별을 출력하는 함수이므로 printStar(0)을 수행한 뒤, 1번째 줄에 해당하는 별 5개를 출력하게 된다. 이는 올바르게 동작하는 것이다. 하지만 n이 0인 경우를 생각해보면, 함수 정의상 1부터 0번째 줄까지의 별을 출력하는 함수이며 지금 개형대로라면 printStar(-1)을 호출 한 뒤 별을 5개 출력하게 된다.

public class Main {
    public static void printStar(int n) { // 1부터 n번째 줄까지 별을 출력하는 함수
        if(n == 0)                        // n이 0이라면, 더 이상 진행하지 않고 종료
            return;                      
        
        printStar(n - 1);                 // 1부터 n - 1번째 줄까지 출력하는 함수
        System.out.println("*****");      // n번째 줄에 해당하는 별 출력
    }

    public static void main(String[] args) {
        System.out.println("start");
        printStar(3);
        System.out.println("end");
    }
}

함수의 가장 끝에 도달했을 경우에도 알아서 함수는 return을 하며 빠져나오게 된다. 이때, 함수가 어디로 돌아가게 되는지에 대해 자세히 살펴봐야 한다.

✌️결과:
😜 위에 내용을 이해했다면 밑에 게시되어 있는 코드를 생각해보자.

public static void printStar(int n) {
    if(n == 0)
        return;
    
    for(int i = 0; i < n; i++)
        System.out.print("*");
    System.out.println();
    printStar(n - 1);
    for(int i = 0; i < n; i++)
        System.out.print("*");
    System.out.println();
}

바로 두 직각삼각형이 위아래로 붙어있는 모양을 받아보게 된다. 크게 봤을 때 상상을 해보면, printStar(n - 1)을 실행하기 직전에 n개의 별을 출력하고, n - 1개를 처리한 이후에 다시 n개의 별을 출력하므로 위아래로 n개를 출력하고 계속 안쪽으로 별을 채워넣어가는 모양이 될 것이라 예상할 수 있다.
밑에 결과가 있는데 보기전에 꼭 곰곰히 생각해보고 체크해보길 바란다.

✌️ 결과:
.
.
.
.
.

입력 : 3
***
**
*
*
**
***