재귀(Recursion)

재귀란 사전적 의미로 '원래의 자리로 되돌아 가거나 되돌아 옴.' 을 의미한다. 프로그래밍에서 재귀는 원래의 자리로 되돌아 온다라는 의미보다는 '돌고 돌다' 라는 의미가 더 어울릴 것이다. 재귀를 간단하게 설명하기 위해 0부터 10까지 출력하는 간단한 카운트다운 함수 코드를 먼저 보자.

public class Countdown {

    public static void countdown(int number) {
        System.out.println(number);
    }
    public static void main(String[] args) {
        for(int i = 1; i < 11; i++) {
            countdown(i);
        }
    }
}

for문을 이용한 반복으로 구현하였다. 재귀를 설명하기 앞서, 먼저 얘기하자면, 대부분의 for문은 재귀문으로 변형 될 수 있다. 다음이 위의 카운트다운 함수를 재귀적으로 표현한 예시이다.

public class Countdown {

    public static void countdown(int number) {
        
        if(number == 0) {
            return;
        }

        else {
            System.out.println(number);
            countdown(number - 1);
        }

        
    }
    public static void main(String[] args) {
        
        countdown(10);        
    }
}

10부터 1까지 차례대로 출력하고 프로그램이 종료될 것이다. countdonw 함수를 살펴보면, number가 0이 아닐때, number-1의 인수를 가지고 또다시 자기 자신을 호출하는 것을 볼 수있다. 함수내에서 자기 자신을 호출하는것, 이것을 재귀호출(Recursion Call)이라고 하며, 재귀호출을 포함하는 함수를 재귀함수(Recursion Function) 라고 부른다.

재귀 함수의 조건

재귀 함수가 성립하려면 반드시 재귀 함수가 종료되는 기저 조건(Basis Condition) 을 가져야한다. 그렇지 않는다면, 함수의 호출을 관리하는 호출 스택의 메모리가 가득차서 스택 오버플로우(Stack Overflow)를 발생시킬 것이다.

기저 조건

위의 함수를 다시한번 살펴보자

public class Countdown {

    public static void countdown(int number) {
        
        if(number == 0) {
            return;
        }

        else {
            System.out.println(number);
            countdown(number - 1);
        }

        
    }
    public static void main(String[] args) {
        
        countdown(10);        
    }
}

함수 내에 if문을 주목하자. number변수가 0이면, return을 이용하여 함수를 종료시킴을 알 수 있다. 이때 number가 0인 조건을 기저 조건 이라고 한다. else문의 명령만 실행시켜 보자. 조건의 끝을 알 수 없는 함수는 호출 스택이 가득차 Stack Overflow를 발생시킬 것이다.

호출 스택

컴퓨터의 관점에서 재귀함수를 실행한다고 생각해보자. number 변수가 3인 상태에서 호출을 시작한다.

첫번째, countdown(3)을 실행한다. 동시에 호출 스택에 countdown(3) 함수를 담는다. number가 0이 아니므로 countdown(3-1)을 호출한다.

중요한 것은 countdown(2)함수가 종료 안되면 countdown(3)의 프로세스도 종료되지 않는다.

두번째, 호출 스택의 맨 위에는 countdown(3)에서 countdown(2)가 호출되었으므로, 스택의 맨 위에는 countdown(2)가 위치하고, number 변수 또한 0이 아니므로, countdown(1)을 호출한다.

세번째, 호출 스택의 맨 위에, 마찬가지로 countdown(1)이 추가되고, number가 0이 아니므로, countdown(0)를 호출한다.

네번째, 호출 스택의 맨 위에, 마찬가지로 countdown(0)이 추가되고, 0이므로 countdown(0)함수를 스택에서 pop 한다.

다섯번째, countdown(0) 함수가 종료되었으므로, countdown(1) 함수도 종료되고, 연쇄적으로 종료되어 호출 스택을 모두 비우게 된다.

만약 number == 0 와 같은 기저조건이 존재하지 않다면, 호출 스택에 무한적으로 함수 호출이 쌓일것이다. 이 때, 호출 스택의 메모리를 초과하게 되고 Stack Overflow를 발생시키게 된다.