재귀를 사용한 재귀적 반복.

유방현·2022년 9월 17일

자료구조와 알고리즘

목록 보기

10/17

재귀는 함수가 자기 자신을 호출 할 때를 뜻하는 용어이다. 무한 재귀는 전혀 쓸모가 없지만, 올바르게 재귀를 사용한다면 강력한 도구가 될 수 있다.

루프 대신 재귀

for문을 사용해서 카운트 다운하는 프로그램이 있다고 하자.
    public static void countdown_for(int num){
        for(int i = num; i >= 0; i--){
            System.out.println(i);
        }
    }
위와 같은 프로그래밍을 재귀 함수를 사용하면 어떻게 구현 할 수 있을까??
    public static void countdown_recursive_(int num){
        System.out.println(num);
        if (num <= 0) return;
        countdown_recursive_(num-1);
        return;
    }
파라미터로 주어진 매개 변수 n을 출력한다. 그 후 매개 변수가 0보다 작다면 더이상 재귀를 반복하지 않는다. 마치 포문과 똑같이 동작하지 않는가??

루프를 사용 할 수 있는 경우라면 대부분 재귀로 해결 할 수있다.
재귀는 명쾌한 코드를 작성하게 해줄 수 있는 도구다. 위 코드는 for 루프보다 재귀가 훌륭하거나 효율적이지는 않다. 하지만 재귀가 빛을 발하는 경우도 있다.

기저 조건

    public static void countdown_recursive_(int num){
        System.out.println(num);
        if (num <= 0) return;
        countdown_recursive_(num-1);
        return;
    }
위의 재귀 코드는 파라미터 num이 0보다 작거나 같으면 더이상 재귀를 반복하지 않는다.
재귀에 쓰이는 용어로 함수가 반복되지 않는 이러한 경우를 기저 조건이라고 부른다. 위 코드의 기저 조건은 0보다 작거나 같다가 기저 조건이다. 모든 재귀는 함수가 무한으로 반복되지 않기 위해 반드시 기저 조건을 가지고 있어야 한다.

재귀 코드 읽기

재귀 코드를 확인하고 어떻게 동작하는지 확인 방법을 알아보자.
아래와 같이 factorial을 구하는 코드가 있다.
public static int factorial(int num){
        if(num <= 1) return num;
        else return num * factorial(num - 1);
    }
재귀 코드를 읽는 방법을 알아 보자.

1. 기저 조건을 찾는다.
2. 기저 조건에서 함수가 어떻게 동작하는지 살핀다.
3. "끝에서 두 번째" 조건을 찾는다.(기저 조건 바로 전 조건)
4. "끝에서 두 번째" 조건이 어떻게 동작하는지 확인한다.
5. 방금 분석한 조건의 바로 전 조건을 찾아가며 위 절차를 반복하고 그 때마다 함수가 어떻게 동작하는지 확인한다.

이재 위 절차를 예시 코드에 대입해보자.
이 코드는 보다시피 return num * factorial(num - 1) 부분에세 재귀가 발생한다. 따라서 함수가 자기 자신을 호출하지 않는 (num <= 1) 조건이 기저 조건이다. 이제 기저 조건을 즉factorial(1)을 처리한다고 가정하자. 그러면 이 메소드는 단수히 1을 반환한다.
이제 다음 조건인 factorial(2)로 넘어가자. 이 경우 factorial(1) * 2를 반환한다. 따라서 1 * 2 = 2를 반환한다. 이제 factorial(3)을 호출하면 어떻게 될까??
이는 factorial(1) * factorial(2) *3을 반환한다. 이는1 * 2 * 3= 6이다.
이처럼 기저 조건부터 분석을 시작해서 나아가는 것은 재귀를 추론하는 훌륭한 방법이다.

컴퓨터의 눈으로 바라보는 재귀

재귀를 완벽하게 이해 하려면 컴퓨터가 재귀 함수를 어떻게 처리하는지 알고 있어야 한다.
지금부터 컴퓨터가 재귀 함수를 어떻게 처리하는지 알아보자.

가령 컴퓨터가 factorial(3)을 처리한다고 생각해보자. 3은 기저 조건이 아니므로 컴퓨터는 factorial(2)를 실행한다. 이 때 컴퓨터가 factorial(2)를 실행할 때 아직 factorial(3) 실행은 끝나지 않는다. 그렇기에 컴퓨터의 재귀가 까다로운 것이다.
factorial(2) 또한 기저 조건이 아니므로 factorial(1)을 실행한다. 이 때 fatorial(2)는 끝나지 않는다. 즉 factorial(1)은 factorial(2)와factroial(3)을 실행하는 도중 실행된다. 컴퓨터는 어떻게 이러한 정보를 전부 기록할까?? factorial(1)이 끝나면 factorial(2)를 마저 실행해야 한다는 사실을 어떻게 기억할까??

호출 스택

컴퓨터는 스택을 사용해서 어떤 함수를 호출 중인지 기억한다. 이 스택을 목적에 딱 맞게 호출 스택이라고 부른다. 위 factorial 코드에서 호출 스택이 어떻게 동작하는지 알아보자.

컴퓨터는 factorial(3)을 호출하며 시작한다. 하지만 메서드가 종료되기 전에 factorial(2)를 호출한다. 컴퓨터가 아직 factorial(3)을 실행 중인지 알려면 컴퓨터는 이 정보를 호출 스택에 푸시해야한다. 호출 스택 []에 factorial(3)를 푸시한다. -> [factorial(3)], factorial(2) 또한 기저 조건이 아니므로 호출 스택에 푸시한다. -> [factorial(3),factorial(2)], 이어서 컴퓨터틑 factorial(1)을 호출한다. 이는 기저 조건이므로 factorial() 메소드를 실행하지 않는다. 이 후 컴퓨터는 호출 스택을 확힌해 실행 중인 함수가 있는지 확인한다. 호출 스택에서 pop한다. -> [factorial(3)], 이제 컴퓨터는 factorial(2)를 완료한다. 이 후 위 과정을 반복하여 factorial(3)을 완료한다. 이제 호출 스택에 함수는 존재 하지 않는다. 즉 재귀는 완료된다.
이를 정리하면 다음과 같다.

1. factorial(3)이 먼저 호출된다. 완료하기 전에...
2. factorial(2)가 두 번째로 호출된다. 완료하기 전에...
3. factorial(1)이 세 번째로 호출된다. 완료하기 전에...
4. factorial(1)이 완료된다.
5. factorial(2)가 factorial(1)결과를 토대로 완료된다.
6. factorial(3)이 factorial(2) 결과를 토대로 완료된다.

이러한 방법을 호출 스택을 통해 값 위로 전달하기라고 부르기도 한다. 즉 각 재귀 함수는 계산된 값을 부모 함수에 반환한다. 마침내 최초로 호출된 함수가 최종 값을 계산한다.

스택 오버플로

무한 재귀를 할 경우 호출 스택은 어떻게 될까???
무한 재귀가 발생하면 컴퓨터는 반복해서 같은 함수를 호출 스택에 푸시한다. 이러면 단기 메모리가 더 이상 데이터를 저장할 공간이 없을 때 까지 호출 스택은 점점 늘어난다. 결국 스택 오버플로라는 오류가 발생한다. 컴퓨터는 강제로 재귀를 종료하고 메모리가 다 찼으니 더 이상의 함수 호출을 거부한다! 라고 프로그래머에게 알려준다.

파일 시스템의 순회

재귀와 맞는 문제의 유형은 몇 단계나 반복해야 하는지 모르는 상황을 가진 문제이다. 파일 시스템을 순회하는 예제를 살펴보자. 어떤 디렉토리를 루트 디렉토리로 설정하고 그 안에 존재하는 모든 디렉토리 목록을 출력한다.
public static void findDirectory(File rootDir){
        File[] listAll = rootDir.listFiles();
        if (listAll == null) return;
        for (File file: listAll){
            if (file.isDirectory()){
                System.out.println("file = " + file);
                findDirectory(file);
            }
        }
    }
이 코드의 경우 디렉토리 안에 존재하는 모든 파일을 읽는다. 그리고 안에 파일 or 디렉토리가 없을 경우가 기저 조건이다. 만약 파일이나 디렉토리가 존재한다면 findDirectory() 함수를 호출한다. 그리고 이 과정을 반복한다. 그럴경우 루트 디렉토리 안에 있는 모든 디렉토리를 확인 할 수 있다. 이는 DFS(깊이 우선 탐색)을 이용해 해결하였다.