재귀란?
⇒ 함수가 자기 자신을 호출할 때 사용하는 용어
반복문(루프)과 재귀의 차이
// 루프
function countdown(number){
for(let i=number; i>=0; i--){
console.log(i);
}
}
countdown(10);// 재귀
function countdown(number){
console.log(i);
if(number === 0) return;
countdown(number - 1);
}
countdown(10);루프를 사용할 수 있는 경우엔, 거의 대부분 재귀도 쓸 수 있다.
if(number === 0) return; → 기저조건(함수가 반복되지 않는 경우 === 무한대로 출력되지 않게)
계승 문제 - 재귀코드읽기
- 321 = 6
function factorial(number){
if(number === 1){
return 1;
}else{
return number * factorial(number - 1);
}
}기저조건 → number가 1일때,
factorial(1) → 1
factorial(2) → 2
factorial(3) → 6
이런식으로 기저조건부터 분석을 시작해서 나아가는 것 === 재귀코드의 추론
→ 인간이 봤을 때는 어딘가에 기록(예를 들어 냅킨) 할 수 있어 이것들을 금방 추론할 수 있다. 하지만, 컴퓨터라면? → 어딘가에 기록을 할 수 있을까?
컴퓨터가 바라보는 재귀
factorial(2) 실행을 시작할 때 아직 factorial(3) 실행은 끝나지 않는다.! 즉, 컴퓨터는 factorial(3)를 다 실행하지 않았는데, factorial(3) 를 실행하는 중에 factorial(2) 실행을 시작하는 것이다.
마찬가지로 factorial(1)도 마찬가지이다.
결국 factorial(1)은 factorial(2)와 factorial(3) 둘 다를 실행하는 중에 실행되는 것이다.
컴퓨터는 factorial(1)이 끝나면 다시 factorial(2)로 가서 마저 실행해야 한다는 사실을 어떻게든 기억해야한다.
?→ 어떻게 기록할까?
- 호출 스택
컴퓨터는 스택을 사용해 어떤 함수를 호출 중인지 기록한다.
- 즉, factorial(3)을 호출하며 시작하고, 이 메서드가 종료되기 전에 factorial(2)를 호출한다. 그럼 컴퓨터가 아직 factorial(3)을 실행 중인지 알려면 이 정보를 호출 스택에 푸시해야한다.
위 그림은 컴퓨터가 factorial(3)을 실행중이라는 뜻이다. (실제로 컴퓨터는 실행하던 코드 줄과 변숫값 등도 저장해야 하지만 위 그림에서는 단순하게 묘사)
- 이어서 컴퓨터는 factorial(2)를 실행한다. factorial(2) 역시 factorial(1)을 불러오기 때문에 factorial(2)가 실행 중임을 기억하기 위해 호출 스택에 푸시한다.
- 이어서 컴퓨터는 factorial(1)을 실행한다. 1이 기저 조건이므로, factorial(1)은 factorial 메서드를 호출하지 않고 끝난다.
- 컴퓨터는 factorial(1)을 끝낸 후 호출 스택을 확인해 실행 중이던 함수가 있는지 본다. 호출 스택에 데이터가 있으면 컴퓨터에 아직 해야 할 일이 남았다는 뜻이며 실행 중인 다른 함수를 마무리해야한다.
스택은 LIFO(last in first out) 이기 때문에 가장 최근에 호출된 함수가 먼저 POP 된다.
- 즉, 스택에 있는 factorial(2) → factorial(3) 순으로 POP을 하게 되고 , 스택이 비어 있으몀 컴퓨터는 메서드를 모두 실행했음을 알게되고 재귀는 끝난다.
스택 오버플로우
function blah(){
blah();
}blah() 는 자기 자신을 무한정 호출한다.
이렇게 될 경우, 호출 스택은 어떻게 될까??
무한 재귀에서는 컴푸터가 반복해서 같은 함수를 호출 스택에 푸시한다. 단기 메모리에 더 이상 데이터를 저장할 공간이 없을 때까지 호출 스택은 점점 늘어난다. 결국 스택 오버플로 라는 오류가 발생!! → 컴퓨터는 재귀를 강제로 중단하고 “메모리가 다 찼으니 더 이상의 함수 호출을 거부한다” 라는 멘트를 날리는 것!
재귀 예시 코드
- 파일 시스템 순회
어떤 디렉터리 내에 있는 모든 파일에 대해 모든 하위 디렉터리명을 출력하는 등의 작업을 하는 스크립트
단 하나의 디렉터리 내에 있는 파일만 처리하는 스크립트가 아니라 그 디렉터리의 하위 디렉터리, 그리고 하위 디렉토리의 하위 디렉터리에 잇는 모든 파일에 대해 수행 되어야한다.
⇒ 이걸 반복문으로 한다면? 2단계만 해도 벌써, 반복문이 2번 써진다. 3이나 4, 5단계 밑까지 찾으려면 어떻게 할까? depth가 얼마나 깊은지 모르니, 지정할 수 없다..
이럴 땐 재귀를 사용한다. 재귀를 사용하면 원하는 만큼 아래로 가는 스크립트를 작성할 수 있다.
const fs = require('fs');
const path = require('path');
function findDirectories(directory) {
// 디렉토리 내의 모든 파일 및 디렉토리 가져오기
fs.readdirSync(directory).forEach((filename) => {
const fullPath = path.join(directory, filename);
// 해당 경로가 디렉토리인지 확인
if (fs.lstatSync(fullPath).isDirectory() && filename !== '.' && filename !== '..') {
console.log(fullPath); // 디렉토리 경로 출력
findDirectories(fullPath); // 재귀적으로 하위 디렉토리 탐색
}
});
}
// 테스트 실행
const startDirectory = './start'; // 탐색 시작 경로를 지정
findDirectories(startDirectory);- 코드 도식화
마무리
알고리즘이 임의의 단계 만큼 깊이 들어가야한다면 재귀가 좋은 방법일 수 있다. 하지만 막상 재귀 함수를 작성하려고 할 때 어려움을 격는다. 다음 포스팅에서는 재귀적으로 작성하는 법을 보다 쉽게 익히는 기법을 알아보겠다.!
여
연습문제
const data = [1, [2, 3], [4, [5, 6]], 7];
function recursive(array){
array.forEach((item)=>{
if(Array.isArray(item)){
recursive(item);
} else{
console.log(item);
}
})
}
recursive(data); // 모든 숫자 출력!바깥 배열의 각 항목을 순회한다. 값이 또 다른 배열이면 그 하위 배열에 함수를 재귀적으로 호출한다. 배열이 아니면 값을 그냥 화면에 출력하는 것이 기저 조건이다.
