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

1. 재귀(recursion)

• 재귀는 큰 목표 작업하나를 통일하면서 간단한 작업 여러 개로 나눌 수 있을 때 유용한 프로그래밍 패턴이다.
• 예를들어 x를 n제곱해주는 함수 pow(x, n)가 있다고 해보자

1. for 문을 사용하는 방법

function pow(x, n) {
  let result = 1;
  
  //반복문을 사용해 x를 n번 곱해준다.
  for (let i = 0; i < n; i++) {
    result = result * x;
  }
  
  return result;
}

pow(2, 3); // 8

2. 재귀를 사용하는 방법

function pow(x, n) {
  if (n === 1) { // n이 1일 경우에는 x만 리턴
    return x;
  } else {
    return x * pow(x, n - 1) // x를 곱해주고 n에만 1을 빼주고 pow함수를 다시 부른다.
  }
}

pow(2, 3) // 8

재귀하는 과정을 차근차근 생각해 보면 
1. pow(2, 3) = 2 * pow(2, 2)
2. pow(2, 3) = 2 * pow(2, 1)
3. pow(2, 1) = 2

여기에서 가장 처음 하는 호출을 포함한 중첩 호출의 최대 개수는 재귀 깊이(recursion depth) 라고 한다. 그래서 함수pow(x, n)에서는 n이 재귀의 깊이가 된다.

2. 스택(stack)

실행 중인 함수의 실행 절차에 대한 정보는 함수의 실행 컨텍스트(execution context)에 저장된다.
실행 컨텍스트는 함수 실행에 대한 세부 정보를 담고 있는 내부 데이터 구조이다. 제어 흐름의 현재 위치, 변수의 현재 값, this의 값 등 상세 내부 정보가 실행 컨텍스트에 저장된다.
그래서 함수를 실행할수록 실행 컨텍스트에 많이 저장하게 된다. 즉 재귀의 깊이(위 예시에서는 n)가 커지면 많은 메모리를 차지하게 된다.