01. 재귀함수란?

---

• 재귀란 특정 문제 해결을 위해 동일한 로직의 작은 단위부터 문제를 해결하는 방법을 의미한다.
• 작은 단위를 수행하는 함수 하나를 스스로 호출하는 것이 재귀함수이다.
• 즉 재귀는 반복할 구문을 함수 단위로 쪼개서, 특정 조건이 만족할 때까지 함수를 호출하는 패턴이다.
• 이러한 이유로 재귀는 반복문으로도 표현이 가능하다.
• 재귀함수는 무한반복을 방지하기 위해 반드시 재귀함수 내부에 탈출조건(Termination Case)가 필요하다.

🔨  1. 대표적인 재귀함수, 팩토리얼 함수

• (n === 0) 은 재귀함수의 탈출조건으로, 반드시 탈출조건이 존재해야 무한 방복을 방지할 수 있다,

function fa(n) {
 if(n === 0) {
  return 1;
  } 
return n * fac(n-1);
}

🔨  2. 반복되는 재귀함수의 리턴값엔 다음 재귀함수 호출이 포함되어 있다.

• 재귀함수의 최종 결과값은 마지막 호출부터 리턴값들이 계속해서 넘어오면서 쌓이게 되고,
• 탈출조건이 되는 마지막 호출에서 특정 결과값을 리턴한다.
• 또는 매 호출마다 다음 호출 리턴값을 가지고 활용하여 새로운 값을 전달하기도 한다.

function take(num. arr) {
 if (num === 0 || arr.length === 0) {
  return [];
 }
const head = arr[0];
const tail = arr.slice(1);

return [head].concat(take(num-1, tail));

🔨  3. 재귀함수와 클로저 그리고 스코프

• 재귀함수 설계 시, 아래와 같이 해당 재귀함수 클로저 내부 스코프만을 활용할 수 있으며(result 및 concat메서드), 클로저 외부스코프의 변수를 선언해 활용할 수도 있다.

function getElementByClassName(root, className) {
 let result = [];

if(root.classList.contains(className)) {
 result.push(root);
 }
for(let i = 0; i < root.children.length; i++) }
 let child = root.children[i];
 result = result.concat(getElementByClassName(child, className));
  }
return result;
}

02. 언제, 왜 재귀함수를 사용해야 할까?

---

• 모든 재귀함수는 동일한 작은 단위의 처리를 반복해서 처리하기 때문에 반복문으로도 충분히 표현가능하다.
• 그런데 왜 재귀함수를 써야 할까?

Why 왜?

→ 재귀함수를 사용하면, 코드가 보다 간결해지고 가독성이 좋다는 장점이 있다.

When 언제?

1. 주어진 문제의 로직이 비슷하고 더 작은 단위로 나눌 수 있는 경우
2. 중첩된 루프가 많거나 중첩의 정도를 미리 알수 없는 경우(몇 번을 반복해야하느지 알 수 없는 경우)

재귀함수의 단점은?

1. 재귀함수는 값이 리턴되기 전까지 매 호출마다 Call Stack을 생성해 → 메모리를 비효율적으로 사용하게 되고,
2. 반복되는 로직이나 리턴되는 값을 예측하기 어렵다면 → 오히려 가독성을 떨어뜨릴 수 있다.

→ 따라서 문제에 맞게 재귀함수 혹은 반복문을 적절히 선택해 활용해야 한다.

03. 재귀함수의 주의점

---

함수를 재귀적으로 너무 많이 호출하게 되면 콜스택이 계속 쌓이면서 더이상 기록할 공간이 없어지게 된다.

⇒ 결과적으로 프로그램 중단이 되거나, 에러가 뜨기도 한다.

※ 에러코드 Stack Overflow Error : 콜스택이 너무 많이 쌓여 한계점에 도달했을 때 뜨는 에러

🔨 1. Call stack 이란?

• 여러 함수들이 호출될 때, 해당 호출의 위치를 추적하는 자바스크립트 엔진을 위한 매커니즘이다.
• 현재 어떤 함수가 동작하고 있는지, 그 함수 내에서 어떤 함수가 호출되는지 등의 내용을 알 수 있다.
• 즉, 함수가 호출될 때 해당 함수는 Call Stack에 쌓이게 된다.

💡

규칙은 다음과 같다.

• A 함수를 호출되고 → Call Stack에 A가 쌓인다.
• A 함수 처리 중 다른 함수 B가 호출되면 → Call Stack A 호출 위에 쌓이고 → B 함수 처리를 수행한다.
• B함수 처리가 종료되면 → B함수는 Call stack에서 제거되고 → 아래 쌓여있던 A함수가 처리된다.

→ Call Stack의 이 개념은 push, pop 개념과 동일하다.

다시 재귀함수의 Call Stack으로 돌아오면…

• 이와 같은 원리로 재귀함수 호출 시, 매 호출들이 Call Stack에 쌓인다.
• 마지막 재귀함수 호출이 끝날 때까지 매 호출들이 Call Stack에 쌓이기 때문에 → 메모리가 비효율적으로 운영되고, Stack Overflow Error가 발생하기도 한다.

출처 : 여기