들어가며
뭘 하던 저장을 생활화 합시다.
9.0 재귀를 사용한 재귀적 반복
이후 나올 대부분의 알고리즘을
이해하려면
재귀(recursion)의 핵심 개념을
알아야 한다.
재귀를 사용하면 까다로운 문제를
놀라도록 간단하게 풀 수 있다.
대개는 원래 작성했을 코드보다
훨씬 작다.
대충 다음처럼 정의한 blah() 함수를
호출하면 무슨 일이 벌어질까?
function blah() {
blah();
} 대충 짐작했겠지만 blah()가 자신을
호출하고, 또 blah()가 자신을 호출하여
반복적으로 자신을 호출하면서 함수
자신을 무한대로 호출할 것이다.
재귀는 함수가 자기 자신을 호출할
때는 말하는 공식 명칭이다.
일반적으로 무한 함수 호출은
쓸모가 없고 위험하기까지 하지만
재귀는 활용 가능성이 큰 강력한 도구다.
또한, 재귀의 힘을 활용하면 지금부터
보게 될 특히 까다로운 문제를 풀 수 있다.
9.1. 루프 대신 재귀
당신은 지금 NASA에서 일하고 있고
우주선 발사에 스일 카운트 다운
함수를 프로그래밍해야 한다.
작성할 함수느 10과 같은 숫자를 받아
10부터 0까지 숫자를 표시해야 한다.
잠시 쉬면서 이 함수를 사용자가
원하는 언어로 구현해 보자.
구현이 끝났다면 이어서 글을 읽어보라.
십중팔구 다음 자바스크립트 구현처럼
간단한 루프로 작성했을 것이다.
function countdown(number) {
for(var i=number; i>=0; i--) {
console.log(i);
}
}
countdown(10); 구현에는 문제가 없지만 루프가
필요 없었을 수도 있다.
루프 대신에 재귀를 사용해보라.
다음은 재귀로 countdown 함수를
구현한 첫 번째 시도다.
function countdown(number) {
console.log(number);
countdown(num-1);
}
countdown(10);코드를 한 단계씩 살펴보자.
1단계: countdown(10)을 호출하므로 인자 number에는 10이 들어있다.
2단계: number가 10이므로 10을 콘솔에 출력한다.
3단계: countdown 함수가 끝나기 전에 countdown(number-1)이므로 countdown(9)를 호출한다.
4단계: countdown(9)가 실행된다. 이때 전달받은 number는 9이고, 이를 콘솔에 출력한다.
5단계: countdown(9)가 끝나기 전에 countdown(number-1)이므로 countdown(8)를 호출한다.
6단계: countdown(8)이 실행된다. 이때 전달받은 number는 8이고, 이를 콘솔에 출력한다.
단계별로 코드를 계속 살펴보기 전에
어떤 방식으로 재귀를 이용해
목적을 달성하는지 짚고 넘어가자.
루프 구조체 없이 단순히 countdown
함수 호출만으로
10부터 카운트다운해서 각 숫자를
콘솔에 출력하고 있다.
루프를 사용할 수 있는 경우라면 거의
대부분 재귀도 쓸 수 있다.
물론 재귀를 쓸 수 있다는 이유만으로
무조건 재귀를 써야 한다는 것은 아니다.
재귀는 명쾌한 코드를 작성해 줄 수
있는 하나의 도구다.
앞선 예제의 경우 재귀적인 방법이
전형적인 for 루프보다
더 효율적이거나 훌륭하지 않다.
하지만 재귀가 빛을 발하는 예제를
곧 살펴보겠다.
그때까지는 재귀가 어떻게 동작하는지
계속해서 알아보자.
9.2. 기저 조건
countdown 함수를 단계별로 이어서
살펴보자.
간결하게 볼 수 있도록 몇몇 단계는
생략하겠다.
21단계: countdown(0)을 호출한다.
22단계: 0을 콘솔에 출력한다.
23단계: countdown(-1)을 호출한다.
24단계: -1을 콘솔에 출력한다.
보다시피 이 방법은 무한대로
음수를 출력하므로 완벽하지 않다.
카운트 다운을 0에서 끝내고,
재귀가 영원히 지속되는 것을 막을
방법이 있어야 완벽한 방법이 된다.
number가 0이면 더 이상 countdown()을
호출하지 않는 조건문을 추가해서
문제를 해결할 수 있다.
function countdown(number) {
console.log(number)
if(number === 0) {
return;
} else {
countdown(num-1);
}
}
countdown(10); number가 0이면 코드는 countdown()
함수를 다시 호출하지 않고
반환만 하므로 다른 countdown()은
호출되지 않는다.
재귀에 쓰이는 용어로, 메서드가
반복되지 않는 이러한 경우를
기저 조건*이라 부른다.
* base case, 중단 조건
예제의 countdown() 함수는 0이
기저 조건이다.
9.3. 재귀 코드 읽기
시간과 연습을 통해 재귀에 익숙해질
수 있으며
궁극적으로 2가지 스킬,
재귀 코드 읽기와 재퀴 코드 작성하기를
배우게 된다.
재귀 코드를 읽는 게 조금 더 쉬우므로
읽기 연습을 먼저 해 보자.
계승(팩토리얼)을 계산하는 예제를 살펴보자.
이는 예제로 가장 잘 설명된다.
3의 계승은 다음과 같다.
3 * 2 * 1 = 6
5의 계승은 다음과 같다.
5 * 4 * 3 * 2 * 1 = 120
다음 루비 코드는 주어진 수의
계승을 반환하는 함수를
재귀적으로 구현한 것이다.
def factorial(number)
if number == 1
return 1
else
return number * factorial(number - 1)
end
end 언뜻 보기에 이 코드는 복잡해
보이지만,
재귀 코드를 읽는 방법을 알면 쉽다.
1. 기저 조건이 무엇인지 찾는다.
2. 기저 조건을 다룬다는 가정하에 함수를 살펴본다.
3. 기저 조건 바로 전 조건을 다룬다는 가정 하에 함수를 살펴본다.
4. 한 번에 한 조건씩 올라가면서 계속 분석한다.
위 절차를 예제 코드에 적용해 보자.
코드를 분석해 보면 경로가 2개임을
금방 알아차릴 것이다.
if number == 1
return 1
else
return number * factorial(number - 1)
end 보다시피 factorial이 자신을 호출하는
부분에서 재귀가 일어난다.
else
return number * factorial(number - 1)
end 따라서 함수가 자기 자신을 호출하지
않는 조건인 다음 코드가
기저 조건임이 틀림없다.
if number == 1
return 1 결론적으로 number가 1일때가
기저 조건이다.
이제 기저 조건, 즉 factorial(1)을
처리한다,
라고 가정하고 factorial 메서드를
살펴보자.
관련 코드는 다음과 같다.
if number == 1
return 1꽤 간단하다.
기저 조건이므로 어떤 재귀도
일어나지 않는다.
factorial(1)을 호출하면 메서드는
단순히 1을 반환한다.
이제 메모장을 켜서 이 사실을
기록하자.
factorial(1) return 1
다음 사례인 factorial(2)를 호출하면
2 * factorial(1)을 반환한다.
2 * factorial(1)을 계산하려면 factorial(1)이
무엇을 반환하는지 알아야 한다.
메모장을 확인해 보면 1을 반환하는
것을 알 수 있다.
따라서 2 * factorial(1)은 2 * 1로,
즉 2를 반환한다.
그리고 이 사실을 메모장에 기록하자.
factorial(2) return 2
factorial(1) return 1
이제 factorial(3)을 호출하면 어떻게 될까?
마찬가지로 관련 코드 라인은
다음과 같다.
else
return number * factorial(number - 1)
end따라서 return 3 * factorial(2)로 바뀐다.
factorial(2)는 무엇을 반환하는가?
메모장에 적었으므로 처음부터
다시 알아볼 필요는 없다.
factorial(2)는 2를 반환한다.
따라서 factorial(3)은 3 * 2를,
즉 6을 반환한다.
세상에 맙소사 빨리 메모장에
기록하자.
factorial(3) return 6
factorial(2) return 2
factorial(1) return 1
잠쉬 시면서 factorial(4)는 무엇을
반환하는지 스스로 알아보자.
이처럼 기저 조건부터 분석을
시작해서 나아가는 것은
재귀 코드를 추론하는 훌륭한
방법이다.
사실 이러한 절차를 따라 재귀를
개념화하는 것은
인간에게만 좋은 방법이 아니다.
컴퓨터도 유사한 접근법을 사용한다.
어떻게 하는지 알아보자.
9.4. 컴퓨터의 눈으로 바라본 재귀
factorial 메서드를 생각해 보면
factorial(3)을 호출할 때
다음과 같은 일이 일어난다.
컴퓨터는 factorial(3)을 호출하고,
이 메서드가 끝나기 전에
factorial(2)를 호출하고, 이 메서드가
끝나기 전에 factorial(1)을 호출한다.
엄밀히 말해 컴퓨터가 factorial(1)을
실행하는 동안
여전히 factorial(2)를 실행중이며,
마찬가지로 factorial(3)도 실행하는
중이다.
컴퓨터는 스택을 사용해 어떤 함수를
호출 중인지 기록한다.
이러한 스택을 목적에 딱 맞게
호출 스택이라 부른다.
factorial 예제를 사용해 호출 스택이
어떻게 동작하는지 살펴보자.
컴퓨터는 factorial(3)을 호출하며
시작한다.
하지만 이 메서드가 종료되기 전에
factorial(2)를 호출한다.
컴퓨터가 아직 factorial(3)을 실행
중인지 알려면
컴퓨터는 이러한 정보를 호출 스택에
푸시해야 한다.
| ↓(Top) |
| factorial(3) |
이어서 컴퓨터는 factorial(2)를 실행한다.
이제 factorial(2)는 연이어 factorial(1)을
호출한다.
하지만 컴퓨터가 factorial(1)을 실행하기
전에 컴퓨터는
아직 factorial(2)를 실행 중임을 기억해야
하므로 마찬가지로 호출 스택에 푸시한다.
| ↓(Top) | |
| factorial(3) | factorial(2) |
이어서 컴퓨터는 factorial(1)을 실행한다.
1이 기저 조건이므로 factorial(1)은
factorial 메서드를 호출하지 않고 끝낸다.
호출 스택에 데이터가 들어 있으므로,
즉 아직 실행중인,
즉 끝내야 할 메서드가 남아 있으므로
컴퓨터는 factorial(1)을 끝냈더라도
해야 할 일이 다 끝나지 않았음을
알고 있다.
기억하겠지만 스택에는 탑 원소만
확인할 수 있다는 제약이 있다.
따라서 컴퓨터가 할 다음 작업은
호출 스택 가장 위의 원소,
즉 탑 원소를 가져오는 것이다.
현재는 factorial(2)가 탑이다.
factorial(2)가 호출 스택의 마지막
항목이라는 것은
factorial(2)가 가장 최근에 호출된
메서드라는 의미이므로
지금 바로 메서드를 완료해야
한다는 뜻이다.
이제 컴퓨터는 호출 스택에서
factorial(2)를 팝한다.
| Top | factorial(2) |
| factorial(3) | ↑ |
컴퓨터가 factorial(2)의 실행을 끝낸다.
이어서 컴퓨터는 호출 스택을 확인해서
다음으로 어떤 메서드를 완료해야
하는지 알아본다.
호출 스택이 현재, 다음과 같으므로
| Top |
| factorial(3) |
컴퓨터는 스택에서 factorial(3)을
팝한 후 완료한다.
이 시점에서 스택은 비어 있으므로
컴퓨터는 메서드를 모두 실행했음을
알게 되고, 재귀는 끝난다.
전체적인 과정을 다시 살펴보면
컴퓨터가 3!을 계산한 순서는
다음과 같다.
- factorial(3)이 먼저 호출된다.
- factorial(2)가 두 번째로 호출된다.
- factorial(1)이 세 번째로 호출된다.
- factorial(1)이 먼저 완료된다.
- factorial(2)가 factorial(1)의 결과(반환값)를 토대로 완료된다.
- factorial(3)이 factorial(2)의 결과(반환값)를 토대로 완료된다.
흥미롭게도 무한 재귀*가 있을 때,
* 9장의 가장 첫 번째 예제와 같이, 재귀 호출이 멈추지 않고 계속되어 멈추지 않는 경우
프로그램은 컴퓨터 메모리에 더 이상
공간이 없을 때까지
계속해서 같은 메서드를 호출 스택에
푸시한다.
이로 인해 스택 오버플로우라는
오류가 발생한다.
9.5. 재귀 다뤄보기
NASA 카운트다운과 팩토리얼 계산을
처리하는 예제는 재귀로도 풀 수 있지만,
전형적인 루프(반복문)로도 쉽게
풀 수 있다.
재귀가 흥미롭긴 하지만 이러한 문제를
푸는데 있어 사실상 이점이 없다.
하지만 재귀는 한 알고리즘 내에서
같은 알고리즘을 반복해야하는 상황과
자연스럽게 들어맞는다.
곧 보겠지만 이럴 때 재귀를 사용하면
보다 읽기 쉬운 코드로 만들 수 있다.
파일 시스템을 순회하는 예제를
살펴보자.
어떤 디렉터리 내에 있는 모든
파일에 대해 어떤 작업을 하는
스크립트가 있다고 하자.
하지만 하나의 디렉터리 내에 있는
파일만 처리하는 스크립트가 아니라
그 디렉터리의 하위 디렉터리,
그리고 그 하위디렉터리의 하위
디렉터리에 있는
모든 파일에 대해 수행되길 원하다.
주어진 디렉터리의 모든 하위
디렉터리명을 출력하는
간단한 루비 스크립트를 만들어 보자.
|
1
2
3
4
5
6
7
8
9
10
|
def find_directories(directory)
Dir.foreach(directory) do |filename|
if File.directory?("#{directory}/#{filename}") && filename != "." && filename != ".."
puts "#{directory}/#{filename}"
end
end
end
# 현재 디렉터리에 대해 find_directories 메서드를 호출한다.
find_directories(".")
|
cs |
위 스크립트는 주어진 디렉터리 내에
각 파일을 순회한다.
파일이 하위 디렉터리라면* 해당
하위 디렉터리명을 출력한다.
* 단 현재 디렉터리를 뜻하는 마침표나 이전 디렉터리를 뜻하는 쌍마침표가 아니면
위 스크립트도 잘 동작하긴 하지만
현재 디렉터리의 바로 아래에 있는
하위 디렉터리 명만 출력한다.
하위 디렉터리의 하위 디렉터리명은
출력하지 않는다.
한 단계 더 깊이 탐색할 수 있도록
스크립트를 업데이트 해보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
def find_directories(directory)
# 바깥 디렉터리를 순회한다.
Dir.foreach(directory) do |filename|
if File.directory?("#{directory}/#{filename}") && filename != "." && filename != ".."
puts "#{directory}/#{filename}"
# 안쪽 하위 디렉터리를 순회한다.
Dir.foreach("#{directory}/#{filename}") do |inner_filename|
if File.directory?("#{directory}/#{filename}/#{inner_filename}") && filename != "." && filename != ".."
puts "#{directory}/#{filename}/#{inner_filename}"
end
end
end
end
end
# 현재 디렉터리에 대해 find_directories 메서드를 호다.
find_directories(".")
|
cs |
이제 디렉터리를 찾을 때마다
그 디렉터리의 하위 디렉터리에
대해 동일한 루프를 수행해서
하위 디렉터리명을 출력한다.
하지만 이 스크립트도 한계가 있다.
두 단계 아래까지만 찾기 때문이다.
셋이나 넷, 다섯, 그 이상의 깊이까지
찾기 위해서는 어떻게 해야 하는가?
하위 디렉터리가 더이상 없을 때까지
찾으려면 어떻게 해야 하는가?
재귀의 장점이 바로 이것이다.
재귀를 사용하면 원하는 만큼 아래로
가는 스크립트를 작성할 수 있다.
게다가 매우 간단하다.
|
1
2
3
4
5
6
7
8
9
10
11
|
def find_directories(directory)
Dir.foreach(directory) do |filename|
if File.directory?("#{directory}/#{filename}") && filename != "." && filename != ".."
puts "#{directory}/#{filename}"
find_directories("#{directory}/#{filename}")
end
end
end
# 현재 디렉터리에 대해 find_directories 메서드를 호출한다.
find_directories(".")
|
cs |
위 스크립트는 파일이 하위 디렉터리면
그 하위 디렉터리에서
find_directories 메서드를 호출한다.
따라서 이 스크립트는 모든 하위
디렉터리를 찾을 때까지
깊이 들어가게 된다.
빅 오 측면에서 보면 재귀만으로는
알고리즘의 효율성이 꼭 나아지지 않는다.
하지만 10장에서 재귀가 알고리즘
속도에 영향을 주는
핵심요소가 될 수 있음을 보이겠다.
9.6. 마무리
파일 시스템 예제에서 봤듯이,
알고리즘 자체만으로는 얼마나 많은
단계를
깊이 들어가야 하는지 알 수 없을 때
재귀가 좋은 방법일 수 있다.
재귀를 안다는 것은 초인적인 힘이
생긴다는 것이다.
매우 효율적이지만 아직 덜 향상된
알고리즘을 곧 다루게 될 텐데
이 중 상당수는 재귀 원리에 기반한다.
참고 및 출처
 |
|
