재귀함수와 콜 스택
💬 재귀함수란?
➿ 프로그래밍에서 재귀의 사전적 정의
"어떠한 것을 정의할 때 자기 자신을 참조하는 것"
위키백과
- 위의 사전적용어와 같이 자기 자신을 다시 호출하는 함수를 재귀함수라고 한다
for문으로 완전히 동일히 작동하는 코드로직을 구성할 수 있지만, 재귀를 돋보이게 만드는 주요 요인 중 하나는 재귀를 사용하지 않을 때와 달리 몇 줄의 코드로 복잡한 작업을 수행할 수 있다는 것이다.- 또한 재귀 함수에는 항상 자기자신의 호출을 중지하는 조건(break)이 필요하다.
그렇지않으면?
Maximum call stack size exceeded 즉, stackoverflow가 나타난다
🍢 Call Stack
- 자바스크립트엔진은 콜 스택과 힙(heap)으로 구성되어있는데,
- 함수 호출시, 함수 실행 컨텍스트가 순차적으로 콜 스택에
push되어, 순차적으로 실행된다 - 콜스택에서의 순차적인 실행이란, 선입후출(First In Last Out,FILO)방식으로 동작된다
- 가장 먼저 호출된 함수는 가장 나중에 종료됨
- 가장 최근에 호출된 함수는 가장 먼저 종료됨
따라서, 콜 스택이 재귀함수와도 밀접한 연관이 있는데,
1. 콜 스택은 프로그램 실행 중 발생하는 함수 호출을 추척한다
2. 재귀함수는 자기자신을 다시 호출하므로, 각 재귀 호출마다 콜 스택에 호출정보가 추가된다(push)
3. 재귀함수내의 걸어놓은 조건(breakPoint)에 달하면, 해당 호출이 콜스택에서 제거(pop)되고, 각 함수의 반환값에 따라 최종 결과가 결정되는 흐름이다.
해당 재귀함수로 이루어진 콜스택에서 가장 상단의 함수가 종료조건을 만나면?
🌃 예시로 for문과 재귀함수 비교해보기
첫번째인수 x에 두번째인수n승 해주는 pow()를 만들어보자
일반적인 for문에서
function pow1(x, n) {
let result = 1;
//n만큼 반복문을 돌면서 result에 x를 곱한다
for (let i = 0; i < n; i++) {
result *= x;
}
return result;
}
pow1(2,3) //2의 3승인 8이 나오게된다.- 위 코드에선
pow1()내의result라는 변수를 할당해 해당 변수에 인자로받은n만큼 돌면서,result에x의 값을 곱한후 해당resul의 값을 반환하는 형태이다.
이걸 재귀함수로 만들면?
const pow2 = (x, n) => {
if (n === 1) {
return x;
}
return x * pow2(x, n - 1);
};
pow2(2, 3);
- 해당 코드의 로직을 살펴보면,
n의 값이1이됬을때x의 값을 반환한다는게 있는데, 이게 해당 재귀함수에서의 brakepoint 즉, 조건처리이다. - 또 n의 값이 1이 아닐때의 경우를 살펴보면,
x에pow2(x,n-1)을 한 값을 곱하고 있다 이게 무슨의미냐면 x를n-1번 곱한 값을 반환한다는 의미이다.
즉, pow2(x,n)을 구하는것은 x에다가 pow2(x,n-1)을 한번 더 곱하는것과 같다.
pow2(2, 3)은2에다가pow2(2, 2)를 곱한 값pow(2, 2)는2에다가pow(2, 1)을 곱한 값
pow2(2,6)으로 n의 인수로 6을 전달했을때를 디버깅툴로 확인해보자.
pow2()의 가장 첫번째 재귀함수 실행 (콜스택 첫번째로 쌓임)
pow2()의 두번째 재귀함수 실행
pow2()의 세번째 재귀함수 실행
pow2()의 네번째 재귀함수 실행
pow2()의 다섯번째 재귀함수 실행
pow2()의 여섯번째 재귀함수 실행 (n값이 1이 됨과 동시에 x를 반환하고 재귀함수가 종료되었다)
pow2()함수의 총 호출스택 여기선 인수가 총 6개이므로, 6개가 된 순간 위에서부터 아래로 제거된다
🦜 재귀함수 활용하기
😒 for문이나 재귀함수나 코드양은 거기서거기인데??
- 재귀함수는의 장점으로는,재귀를 사용하지 않을 때와 달리 몇 줄의 코드로 복잡한 작업을 수행한다는게 존재한다고했다.
- 직접 코드 구성을 해보자
이렇게 중첩으로된 객체가 존재할때,
const SocialPartiners = {
foundingDate: 2021,
team: {
marketing: [
{
name: "이진아",
salary: 3_250_000,
},
{
name: "박연성",
salary: 2_600_000,
},
],
design: {
ui: [
{
name: "송우진",
salary: 3_920_000,
},
{
name: "김지평",
salary: 2_743_000,
},
],
uxd: [
{
name: "이수아",
salary: 4_000_000,
},
{
name: "최철상",
salary: 3_208_000,
},
{
name: "고요미",
salary: 2_106_000,
},
],
},
},
};
- 만약
for문으로 돌아서 해당 객체들의value을 전부 일일히 분해해서 얻는건 상당한 고역일것이다
for(let value in randomUser){
if(Object.prototype.hasOwnProperty.call(randomUser,value)){
const L1 = randomUser[value];
console.log('Level 1 : ' + value);
if(typeof L1 === 'object'){
for(let value in L1){
if(Object.prototype.hasOwnProperty.call(L1,value)){
const L2 = L1[value];
console.log('\tLevel 2 : ' + value);
if(typeof L2 === 'object'){
... 이하생략 🫣
}
}
}
}
}
}- 이때 해당
object의value를 한번에 찾을려고하면for문보다 재귀함수를 사용해서 자기자신을 직접호출하는 편이 훨씬 더 코드도 간결해지고, 가독성도 높아진다.
const getAllValues = (department) => {
let valuesArray = [];
for (let key in department) {
if (Object.prototype.hasOwnProperty.call(department, key)) {
let value = department[key];
if (typeof value === "object" && !Array.isArray(value)) {
valuesArray = valuesArray.concat(getAllValues(value));
} else if (Array.isArray(value)) {
value.forEach((item) => {
valuesArray = valuesArray.concat(getAllValues(item));
});
} else {
valuesArray.push(value);
}
}
}
return valuesArray;
};- 먼저
for in문으로 해당 객체의 프로퍼티를 순회한다 hasOwnProperty로 해당 객체가 프로퍼티를 가지고 있는지 확인하고- 있다면, 다시 조건처리를 하게되는데, 해당 객체가 object여야하고, 배열이아니여야한다, 그럼 해당 object를 선언해뒀던 빈 배열
valuesArray에getAllValues(value)함수를 재귀적으로 호출하며 찾아나간후concat한다. - 만약 객체의 value들을 전부 배열로 만들을땐, 해당 value의
forEach를 돌아 다시getAllValues(item)을 재귀적으로 호출해 배열에 담아나간다. - 마지막으로 전부 담아간 배열 (valuesArray)를 반환한다.
getAllValues()를 사용해 중첩객체들의 value들만 모인 배열을 만든 모습
