[javaScript] 재귀 함수와 메모리 사용량 간의 관계

📌 재귀함수란 

재귀함수는 함수 내에서 자기 자신을 다시 호출하는 방법이다.

 

---

🤼‍♀️  재귀 vs 반복문

	재귀	반복문
장점	코드가 짧고 간결하다. 유지보수가 쉬워진다.	메모리가 절약된다. 속도가 상대적으로 빠르다.
단점	메모리 차지가 크다. (📌 아래에서 설명 예정) 깊이 제한이 있다. (엔진에 따라 다르지만, 십만까지는 보통 불가능) 속도가 상대적으로 느리다.	코드가 길고 복잡하다. 분기문이 복잡하게 얽혀있을 때는 재귀에 비해 크게 메모리가 절약되는 것은 아니다.

 

반복문 코드

function pow(x, n) {
  let result = 1;

  // 반복문을 돌면서 x를 n번 곱함
  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

 

재귀 코드

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) ); // 8

 

🛑 일반적으로 재귀함수가 반복문으로 대체가능한 경우가 많지만,

모든 재귀함수가 모두 반복문으로 대체되는 것은 아니다.

중첩이 몇번이 이루어졌는지 모르는 상태에선 재귀가 유리하다.(마트료시카, 선물상자 문제)

 

---

🔗 재귀 함수와 메모리 사용량 간의 관계

 

재귀의 단점은 메모리 차지가 크다는 것이다.

재귀가 메모리를 어떻게, 얼마나 차지하는가는 "실행 컨텍스트"와 관련지어 생각해보아야 한다.

실행 컨텍스트란 간단히 말하자면, 실행할 코드에대한 정보들을 모아놓은 객체이다. (참고)

 

예를 들어 아래와 같이

숫자를 넣으면 팩토리얼 값을 리턴하는 재귀함수가 있다고하면, (factorial(3) === 1*2*3)

 

function factorial(n) {
  return n === 0 ? 1 : n * factorial(n - 1);
}

// factorial(10)
//  => 3628800
// factorial(32768)
//  => Uncaught RangeError: Maximum call stack size exceeded

 

위 함수는 아래와 같은 실헹 컨텍스트를 갖는다.

 

 

 

 

 

재귀가 실행될 때마다, 실행컨텍스트가 하나씩 늘어나고, 늘어나는 실행컨텍스트만큼 메모리 차지가 커진다.

실행컨텍스트가 재귀에따라 추가되는 과정을 차근차근 자세히 보려면 링크를 참고한다.

 

 

---