Ch.10 재귀를 사용한 재귀적 반복 (도서 요약 "누구나 자료구조와 알고리즘")

재귀(recursion)를 올바르게 사용하면 까다로운 문제 유형을 놀랍도록 간단하게 해결할 수 있다.

 

public void recursion() {
	recursion();
}

 

위 메서드를 호출하면 자신을 반복적으로 호출하면서 무한대로 호출된다.

재귀는 함수가 자기 자신을 호출할 때를 뜻한다. 

10. 1  루프 대신 재귀

---

만약 당신이 NASA에서 우주선 발사에 쓰일 카운트다운 메서드를 프로그래밍해야 한다면 어떻게 하겠는가? 10부터 0까지 숫자를 표시해야 하면 보통 '루프' 메서드를 사용할 것이다.

 

public void countdown(int number) {
	for (int i = number; i >= 0 ; i--) {
    	System.out.println("카운트 다운 " + i);
    }
}

 

구현에는 문제가 없지만, 루프가 필요 없을 수도 있다. 루프 대신 재귀를 써보자.

 

public void countdown(int number) {
	System.out.println("카운트 다운 " + number);
    countdown(number - 1);
}

 

코드를 한 단계씩 살펴보면,

(1) countdown(10)을 호출하므로 인수 변수인 number는 10부터 시작한다.

(2) number(값 10)를 콘솔에 출력한다.

(3) countdown 메서드가 끝나기 전에 number - 1은 9이니 countdown(9)를 호출한다.

(4) countdown(9)가 실행된다. 이때 number(값 9)를 콘솔에 출력한다.

(5) countdown(9)가 끝나기 전에 countdown(8)를 호출한다.

(6) countdown(8)가 실행된다. 이때 number(값 8)를 콘솔에 출력한다.

....   < 하지만 무한대로 호출해서 결국 오류를 발생할 것이다 >

 

루프를 사용할 수 있는 경우라면 거의 대부분 재귀도 쓸 수 있다.

 

물론 재귀를 쓸 수 있다는 이유만으로 무조건 재귀를 써야 하는 것은 아니다. 재귀적인 방법이 전형적인 for 루프보다 더 훌륭하거나 효율적이지는 않기 때문이다. 하지만 재귀가 빛을 발하는 경우가 있다.

10. 2  기저 조건

---

위 재귀 메서드는 무한대로 음수를 출력하는 문제를 가진다.

카운트다운을 0에서 끝내고 재귀가 영원히 지속되는 것을 막을 방법이 있어야 한다. number가 0이면 더 이상 countdown()을 호출하지 않는 '조건문'을 추가하면 가능하다.

 

public void countdown(int number) {
    System.out.println("카운트 다운 " + number);
	if (number == 0) {
    	return;
    } else {
    	countdown(number - 1);
    }
}

 

number가 0이면 코드는 countdown() 함수를 다시 호출하지 않고 반환만 하므로 더는 countdown()이 호출되지 않는다. 재귀에서 쓰이는 용어로 메서드가 반복되지 않는 이러한 경우를 '기저 조건(base case)'이라 부른다. 위 예제의 countdown() 메서드는 0이 기저 조건이다. 

 

모든 재귀 함수에는 무한대로 호출되지 않게 하는 '기저 조건'이 적어도 하나 있어야 한다.

10. 3  재귀 코드 읽기

---

'계승(factorial)'을 계산하는 예제는 재귀 코드를 읽는 대표적인 연습이 된다.

 

3의 계승은 다음과 같다.

 

3  x  2  x 1  =  6

 

5의 계승은 다음과 같다.

 

5  x  4  x  3  x  2  x  1  =  120

 

public static int factorial(int number) {
    if (number == 1) {
        return 1;
    } else {
        return number * factorial(number - 1);
    }
}

 

해당 코드가 어떻게 동작하는지 살펴보자.

 

(1) 기저 조건을 찾는다.

(2) 기저 조건에서 메서드가 어떻게 동작하는지 살핀다.

(3) "끝에서 두 번째" 조건을 찾는다. 그것이 기저 조건 바로 전 조건이다.

(4) "끝에서 두 번째" 조건에서 메서드가 어떻게 동작하는지 살핀다.

(5) 방금 분석한 조건의 바로 전 조건을 찾아가며 위 절차를 반복하고 그때마다 메서드가 어떻게 동작하는지 살핀다.

 

위 코드는 '함수가 자기 자신을 호출하는 부분'(재귀)과 '자기 자신을 호출하지 않는 조건'(기저), 2가지 경로로 나뉜다.

기저 조건, 즉 factorial(1)을 처리하면 어떤 재귀도 일어나지 않아서 메서드는 단순히 1을 반환한다.

 

factorial(1) return 1

 

다음 조건인 factorial(2)를 호출하면 2 * factorial(1)을 반환한다. 따라서 2 * factorial(1)은 2 x 1, 즉 2를 반환한다.

 

이제 fatorial(3)을 호출하면 어떻게 될까?

 

return number * factorial(number - 1);

 

관련 코드 줄을 보면 3 * factorial(2)로 바뀐다. factorial(2)는 2를 반환하기 때문에 factorial(3)은 6을 반환한다.

 

이처럼 기저 조건부터 분석해서 나아가는 것은 재귀 코드를 추론하는 훌륭한 방법이다.

10. 4  컴퓨터의 눈으로 바라본 재귀

---

컴퓨터가 이해하는 재귀 함수는 인간과 조금 다르다.

 

가령 factorial(3)을 호출한다고 했을 때, 3은 기저 조건이 아니므로 컴퓨터는 다음 코드 줄로 가서 함수 factorial(2)를 실행한다.

 

return number * factorial(number - 1);

 

여기서 주목해야 할 것은, 컴퓨터가 factorial(2) 실행을 시작할 때 아직 factorial(3) 실행이 끝나지 않았다는 점이다!

컴퓨터는 아직 factorial(3)을 다 실행하지 않았는데 factorial(2)를 시작하는 것이다. 게다가 factorial(2)가 factorial(1)을 실행시키니 factorial(2) 역시 끝이 아니다. 결국 factorial(1)은 factorial(2)와 factorial(3) 둘 다를 실행하는 중에 실행되는 것이다.

 

컴퓨터는 factorial(1)이 끝나면 다시 돌아가 factorial(2)를, 또한 factorial(2)를 끝낸 후 factorial(3)를 마저 실행해야 한다는 사실을 기억해야 한다.

 

이를 구현하기 위해 '스택'을 이용한다. 이 스택을 목적에 맞게 '호출 스택(call stack)'이라 부른다.

 

컴퓨터는 factorial(3)을 호출하며 시작한다. 하지만 이 메서드가 종료되기 전에 factorial(2)를 호출한다. 컴퓨터가 아직 factorial(3)을 실행 중인지 알려면 이 정보를 호출 스택에 푸시해야 한다.

 

컴퓨터가 factorial(3)를 실행 중

 

이어서 컴퓨터는 factorial(2)를 실행한다. 아직 factorial(2)를 실행 중임을 기억해야 하므로 마찬가지로 호출 스택에 푸시한다.

 

컴퓨터가 factorial()를 푸시함

 

컴퓨터는 factorial(1)을 끝낸 후 호출 스택을 확인해 실행 중이던 메서드가 있는지 확인한다. 호출 스택에 데이터가 있으면 아직 해야 할 일이 남았다는 뜻이다.

 

스택은 가장 위 원소만 팝할 수 있다는 제약이 있다. 가장 위 원소는 가장 최근에 호출된 함수이니, 이러한 제약은 재귀에 이상적이다. 그래서 컴퓨터는 호출 스택 가장 위 원소를 팝 한다. 현재는 factorial(2)다.

 

factorial(2)를 팝함

 

이제 컴퓨터는 스택에서 다음 항목을 팝 한다. 이때 스택에는 factorial(3)만 남았으니 이 항목을 팝 해서 factorial(3) 실행을 완료한다. 그제야 스택이 비어서 컴퓨터는 메서드를 모두 실행했음을 알게 되고, 재귀는 끝난다.

 

이 절차를 정리하면,

 

1) factorial(3)이 먼저 호출된다. 완료하기 전에...

2) factorial(2)가 두 번째로 호출된다. 완료하기 전에...

3) factorial(1)이 세 번째로 호출된다.

4) factorial(1)이 먼저 완료된다.

5) factorial(2)가 factorial(1)의 결과를 토대로 완료된다.

6) factorial(3)이 factorial(2)의 결과를 토대로 완료된다.

 

결국 계산은 factorial(1)이 자신의 결과를 factorial(2)에 전달함으로써 이뤄진다. 이러한 방법을 "호출 스택을 통해 값 위로 전달하기"라고 부르기도 한다. 즉 각 재귀 함수는 계산된 값을 '부모' 메서드에 반환한다. 마침내 최초로 호출된 함수가 최종 값을 계산한다.

10. 5  파일시스템 순회

---

재귀와 자연스럽게 들어맞는 한 가지 문제 유형은 몇 단계나 깊이 들어가야 하는지 모르는 상황에서 문제를 여러 단계로 파고들어야 할 때다.

 

예를 들어 파일시스템을 순회하는 예제가 있다. 어떤 디렉터리 내에 있는 모든 파일에 대해 모든 하위 디렉터리명을 출력하는 작업을 한다고 생각해보자. 재귀를 사용하면 원하는 만큼 아래로 가는 코드를 작성할 수 있다.

10. 6  마무리

---

알고리즘이 임의의 단계만큼 깊이 들어가야 한다면 재귀가 좋은 방법일 수 있다.

 

하지만 대부분의 개발자들에게 재귀 함수를 작성하는 방법은 도전적이다. 다음 장에선 재귀적으로 작성하는 법을 보다 쉽게 익히는 기법을 알아보자.

---

'누구나 자료구조와 알고리즘' / 저자: 제이 웬그로우

해당 글은 '누구나 자료구조와 알고리즘' 책의 내용을 기반으로 작성되었습니다.

오로지 학습용으로 작성하였음을 밝힙니다.

더 자세한 내용을 확인하고 싶다면 해당 저서를 참고하시길 바랍니다.