재귀와 실행컨텍스트
재귀 : 함수내부에서 자기 자신을 호출하는 것
// 반복문을 통한 방법
function pow(x, n) {
let result = 1;
for(let i=0; i<n; i++) {
result *= x;
}
return result;
}
// 재귀를 이용한 방법
function recPow(x, n) {
if(n === 1) {
return x;
}
return x * recPow(x, n-1);
}
// 재귀를 이용한 더 나은 방법
function betterPow(x, n, res=1) {
if(n === 1) {
res *= x;
return res;
}
if(n%2 === 0) {
x *= x;
n = parseInt(n / 2);
} else {
res *= x;
x *= x;
n = parseInt(n / 2);
}
return betterPow(x, n, res);
}
재귀에서 가장 처음 하는 호출을 포함한 중첩 호출의 최대 개수를 재귀 깊이(recursion depth) 라고 합니다. 위의 예시에서 recPow(x, n) 의 재귀 깊이는 n 입니다. 자바스크립트 엔진은 최대 재귀 깊이를 만개까지는 확실하게 허용하지만, 어떤 엔진도 십만이라는 수는 다루지 못합니다.
실행 컨텍스트와 스택
실행 중인 함수의 실행 절차에 대한 정보는 해당 함수의 실행 컨텍스트(execution context) 에 저장됩니다. 실행 컨텍스트는 함수 실행에 대한 세부 정보를 담고 있는 내부 데이터 구조입니다. 제어 흐름의 현재 위치, 변수의 현재 값, this 의 값 등 상세 내부 정보가 저장됩니다.
각 함수 호출이 일어날 때 마다 하나의 실행 컨텍스트가 생성되며, 재귀 호출이 있을 때 다음 절차가 수행됩니다.
- 현재 함수의 실행이 일시 중지
- 중지된 함수와 연관된 실행 컨텍스트는 실행 컨텍스트 스택 이라는 자료구조에 저장
- 재귀 함수 실행
- 재귀 함수의 실행(중첩 함수)이 끝난 이후 실행 컨텍스트 스택에서 일시 중단한 함수의 실행 컨텍스트를 꺼내오고, 중단한 함수 위치에서 이어서 실행
실행 컨텍스트 예제
recPow(2, 3);
위와 같이 recPow(2, 3)을 호출하는 순간, 실행 컨텍스트에는 변수 x=2, n=3 이 저장되고, 실행 흐름은 함수의 첫 번째 줄에 위치합니다.
- Context: {x: 2, n: 3, line 1} - call: recPow(2, 3)
여기서 n이 1이 아니므로 실행 흐름은 if문을 벗어난 다음 줄이 실행됩니다. 이 때 변수는 동일하지만, 실행 흐름의 위치가 변경되면서 실행 컨텍스트도 변경됩니다.
- Context: {x: 2, n: 3, line 5} - call: recPow(2, 3)
5번 째 줄에서 재귀 호출을 실행하게 되는데, 이 값을 계산하려면 새로운 인수가 들어가는 recPow(2, 2) 가 만들어집니다.
recPow(2, 2);
여기서 중첩 호출을 하기 위해서 자바스크립트는 실행 컨텍스트 스택 에 현재 실행 컨텍스트를 저장합니다. 따라서 현재 상황에서 실행 컨텍스트 스택을 보면 다음과 같습니다.
- Context: {x: 2, n: 2, line 1} - call: recPow(2, 2)
- Context: {x: 2, n: 3, line 5} - call: recPow(2, 3)
스택 구조이기 때문에 재귀를 돌면서 바라보는 컨텍스트는 가장 위에 있는 것만 보게되고, 함수가 종료되면 스택에서도 컨텍스트를 제거하게 됩니다. 따라서 컨텍스트에 변수 정보, 코드 중단 위치에 대한 정보가 저장되어 있기 때문에 서브 호출이 끝났을 때 문제없이 이전 컨텍스트가 동작할 수 있습니다.
함수를 재귀적으로 작성했을 때는 재귀 깊이만큼 실행 컨텍스트가 생기는 것을 알 수 있습니다. 따라서 반복문을 사용하게 되면 실행 컨텍스트는 한 개만 생성되기 때문에 필요한 메모리가 적고, 사용 메모리 공간도 고정되는 장점이 있습니다. 하지만 재귀적으로 함수를 작성했을 때 코드가 짧아지고, 유지보수에도 이점이 있으며, 반복문으로 작성할 때 보다 효율적인 코드를 작성하는 것이 가능해집니다.(betterPow의 경우)
재귀적 순회
let company = {
sales: [{
name: 'John',
salary: 1000
}, {
name: 'Alice',
salary: 1600
}],
development: {
sites: [{
name: 'Peter',
salary: 2000
}, {
name: 'Alex',
salary: 1800
}],
internals: [{
name: 'Jack',
salary: 1300
}]
}
};
재귀는 객체를 순회할 때 사용하면 좋습니다.
회사의 조직도가 위와 같다고 했을 때, 직원들의 급여를 모두 더한 값을 구해야 하는 경우를 예로 들어보겠습니다. 물론 반복문을 사용해도 되지만, 조직 개편이 자주 일어나는 경우 development 부서의 sites가 두 개의 부서로 나뉘어질 수도 있는 등 깊이가 달라지게 될 경우 계속해서 유지보수를 해야하는 번거로운 일이 생깁니다.
그래서 재귀적으로 위의 객체를 순회한다고 했을 때는 두 가지 경우로 나누어 생각할 수 있습니다.
- 임직원 배열 을 가진 부서 - 반복문으로 급여 합계를 구할 수 있다.
N개의 하위 부서가 있는 객체 - 각 하위 부서에 속한 임직원의 급여 함계를 얻기 위해N번의 재귀 호출, 최종적으로 모든 하위부서 임직원의 급여를 더한다.
배열을 사용하는 첫 번째 경우는 재귀의 베이스, 즉 함수 내부에서 동작하게 될 로직이 됩니다. 그리고 객체를 사용하는 두 번째 경우는 한 단계 깊이를 타고 들어가야 하므로 재귀 단계가 됩니다.
let company = { // 동일한 객체(간결성을 위해 약간 압축함)
sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 1600 }],
development: {
sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
internals: [{name: 'Jack', salary: 1300}]
}
};
// 급여 합계를 구해주는 함수
function sumSalaries(department) {
if (Array.isArray(department)) { // 첫 번째 경우
return department.reduce((prev, current) => prev + current.salary, 0); // 배열의 요소를 합함
} else { // 두 번째 경우
let sum = 0;
for (let subdep of Object.values(department)) {
sum += sumSalaries(subdep); // 재귀 호출로 각 하위 부서 임직원의 급여 총합을 구함
}
return sum;
}
}
alert(sumSalaries(company)); // 7700
코드를 보면 객체를 만났을 때는 재귀를, 배열을 만났을 때는 임직원들의 임금 합계를 계산하는 로직을 동작한다는 것을 확인할 수 있습니다.
댓글