📖 '누구나 자료구조와 알고리즘'책을 공부한 내용을 담고 있습니다!
10장 재귀를 사용한 재귀적 반복
재귀(recursion)는 고급 알고리즘을 이해하기 위한 컴퓨터 과학의 핵심 개념입니다. 재귀를 잘 사용하면 까다로운 문제 유형을 간단하게 풀 수 있다.
10-1. 루프 대신 재귀
숫자 10를 받아 10부터 0까지 숫자를 표시한 함수를 구현해보자.
- for 문을 이용한 알고리즘
function countdown(number) {
for(let i = number; i>=0; i--) {
console.log(i)
}
}
countdown(10);- 재귀를 활용한 알고리즘
function countdown(number) {
console.log(number);
countdown(number - 1);
}재귀를 이용하면 루프없이 해당 알고리즘을 구현할 수 있다. 루프를 사용할 수 있다면 대부분 재귀도 쓸 수 있다.
10-2. 기저 조건
모든 재귀 함수에는 무한대로 호출되지 않게 하는 '기저 조건'이 적어도 하나 있어야 한다.
- 재귀를 활용한 알고리즘
function countdown(number) {
console.log(number);
countdown(number - 1);
}countdown 함수는 0를 출력하고 끝나야 하지만, 위 코드에서는 계속해서 number 출력한다.
number가 0이면 더이상 countdown 함수를 호출하지 않는 조건문을 추가해야 한다.
- 기저조건을 추가한 재귀 알고리즘
function countdown(number) {
console.log(number);
if(number === 0) {
return;
} else {
countdown(number - 1);
}
}10-3. 재귀 코드 읽기
예제를 통해 재귀 코드 읽기를 연습해보자.
- 계승(factorial)을 계산하는 예제
function factorial (number){
if(number === 1) {
return 1;
} else {
return number * factorial(number - 1);
}
}else 구문에 factorial이 자신을 호출하는 부분에서 재귀가 일어난다. 함수가 자기 자신을 호출하지 않는 조건인 다음 코드가 기저 조건에 해당한다.
if (number === 1) {
return 1;
}기저 조건부터 분석을 시작해서 재귀 코드를 추론할 수 있다.
10-4. 컴퓨터의 눈으로 바라본 재귀
재귀를 완벽히 이해하기 위해 컴퓨터가 재귀 함수를 어떻게 처리하는지 알아보자.
function factorial (number){
if(number === 1) {
return 1;
} else {
return number * factorial(number - 1);
}
}위 재귀 코드를 사용해서 factorial(3)를 호출한다고 하자. 3은 기저 조건이 아니므로 3 * factorial(2) 를 실행한다. factorial이 끝나기 전에 factorial (2)를 실행한다. factorial(2)를 실행하면 factorial(1)를 실행한다. factorial(1)의 실행이 끝나면 다시 돌아가 factorial(2)와 factorial(3)를 차례대로 완료한다.
호출 스택
재귀 함수 실행 과정을 호출 스택으로 설명해보자.
1. factorial(3)를 실행한다. factorial(3)를 스택에 푸시한다.
| factorial(3) |
|---|
2. factorial(3) 실행 중에 factorial(2)이 호출된다. 스택에 factorial(2)를 Push한다.
| factorial(2) |
|---|
| factorial(3) |
3. factorial(2) 실행 중에 factorial(1)이 호출된다. 스택에 factorial(1)를 Push 한다.
| factorial(1) |
|---|
| factorial(2) |
| factorial(3) |
4. 스택은 후입선출 방식으로 처리되기 때문에 factorial(1)부터 실행을 완료한다.(POP)
5. 그리고 각 함수에서 계산되 값을 "부모"함수에 반환하여 최조 호출된 함수가 최종 값을 계산한다.
스택 오버플로
10-5. 파일 시스템 순회
파일 시스템 순회 예제를 통해 재귀함수를 이해해보자.
어떤 디렉터리 내에 있는 모든 파일에 대해 모든 하위 디렉터리명을 출력하는 작업을 하는 스크립트를 구현한다.
const fs = require('fs').promises; // fs 모듈의 promises API 사용
const path = require('path'); // path 모듈 사용
async function findDirectories(directory) {
const files = await fs.readdir(directory, { withFileTypes: true }); // 디렉터리 내의 파일 및 하위 디렉터리 목록을 가져옴
for (const file of files) {
// 파일이 디렉터리인지 확인하고, '.' 혹은 '..'이 아닌지도 체크
if (file.isDirectory() && file.name !== '.' && file.name !== '..') {
const fullPath = path.join(directory, file.name); // 전체 경로 생성
console.log(fullPath); // 전체 경로 출력
}
}
}
위 코드는 현재 디렉터리의 하위 디렉터리만 출력한다. 하위 디렉터리의 하위 디렉터리명을 출력하지 않는다.
계속해서 하위 디렉터리를 찾을 수 있도록 재귀 함수를 이용해보자.
const fs = require('fs').promises;
const path = require('path');
async function findDirectories(directory) {
const items = await fs.readdir(directory, { withFileTypes: true });
for (const item of items) {
if (item.isDirectory()) {
const fullPath = path.join(directory, item.name);
console.log(fullPath); // 하위 디렉터리의 경로 출력
await findDirectories(fullPath); // 재귀 호출
}
}
}요약
- 재귀 함수는 함수 내부에서 자기 자신을 다시 호출하는 것이다.
- 무한 재귀가 되지 않기 위해 '기저조건'이 필요하다.
- 스택 오버플로(stack overflow)는 무한 재귀가 발생할 경우 단기 메모리에 공간이 없어서 컴퓨터에서 강제로 재귀를 중단하고 오류 메시지를 반환하는 것이다.
- 몇 단계를 반복할지 모르는 경우 재귀를 사용하면 좋을 것 같다.
