[JavaScript] 재귀함수 호출 예시

pow (2, 3)를 호출하는 순간, 실행 컨텍스트엔 변수 x = 2, n = 3이 저장되고, 실행 흐름은 함수의 첫 번째 줄에 위치합니다.

이를 도식화하면 다음과 같습니다.

• Context: { x: 2, n: 3, 첫 번째 줄 } pow(2, 3)

위 그림은 함수 실행이 시작되는 순간을 나타낸 것입니다. 지금 상태론 조건 n == 1을 만족하지 못하므로 실행 흐름은 if의 두 번째 분기로 넘어갑니다.

 

 

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

alert( pow(2, 3) );

변수는 동일하지만, 실행 흐름의 위치가 변경되면서 실행 컨텍스트도 다음과 같이 변경됩니다.

• Context: { x: 2, n: 3, 다섯 번째 줄 } pow(2, 3)

x * pow (x, n - 1)을 계산하려면 새로운 인수가 들어가는 pow의 서브 호출(subcall), pow (2, 2)을 만들어야 합니다.

pow(2, 2)

중첩 호출을 하기 위해, 자바스크립트는 실행 컨텍스트 스택 에 현재 실행 컨텍스트를 저장합니다.

지금 보고 있는 예시에선 실행 컨텍스트 스택에 동일한 함수 pow를 호출하였는데, 이는 중요치 않습니다. 모든 함수에 대해 아래 프로세스가 똑같이 적용됩니다.

1. 스택 최상단에 현재 컨텍스트가 '기록’됩니다.
2. 서브 호출을 위한 새로운 컨텍스트가 만들어집니다.
3. 서브 호출이 완료되면. 기존 컨텍스트를 스택에서 꺼내(pop) 실행을 이어나갑니다.

다음은 서브 호출 pow (2, 2)이 시작될 때의 실행 컨텍스트 스택입니다.

• Context: { x: 2, n: 2, 첫 번째 줄 } pow(2, 2)
• Context: { x: 2, n: 3, 다섯 번째 줄 } pow(2, 3)

굵은 테두리로 표시한 새 실행 컨텍스트는 상단에, 기존 컨텍스트는 하단에 있네요.

이전 컨텍스트에 변수 정보, 코드가 일시 중단된 줄에 대한 정보가 저장되어있기 때문에 서브 호출이 끝났을 때 이전 컨텍스트가 문제없이 다시 시작됩니다.

주의:

예시엔 한 줄에 서브 호출 하나만 있기 때문에, 그림에서 '줄’이라는 단어를 사용했습니다. 하지만 한 줄에는 pow(…) + pow(…) + somethingElse(…) 같이 복수의 서브 호출이 있을 수 있습니다.

따라서 좀 더 정확히는 실행이 '서브 호출 바로 직후’에 시작된다고 이야기 할 수 있습니다.

pow(2, 1)

동일한 과정이 다시 반복됩니다. 다섯 번째 줄에서 인수 x = 2, n = 1과 함께 새로운 서브 호출이 만들어집니다.

새로운 실행 컨텍스트가 만들어지고, 이전 실행 컨텍스트는 스택 최상단에 올라갑니다(push).

• Context: { x: 2, n: 1, 첫 번째 줄 } pow(2, 1)
• Context: { x: 2, n: 2, 다섯 번째 줄 } pow(2, 2)
• Context: { x: 2, n: 3, 다섯 번째 줄 } pow(2, 3)

기존 컨텍스트 두 개가 밑에, pow (2, 1)에 상응하는 컨텍스트가 맨 위에 있는 것을 확인할 수 있습니다.

실행 종료

pow (2, 1)가 실행될 땐 상황이 달라집니다. 이전과는 달리 조건 n == 1을 만족시키므로 if문의 첫 번째 분기가 실행됩니다.

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

이젠 호출해야 할 중첩 호출이 없습니다. 따라서 함수는 종료되고 2가 반환됩니다.

함수가 종료되었기 때문에 이에 상응하는 실행 컨텍스트는 쓸모가 없어졌습니다. 따라서 해당 실행 컨텍스트는 메모리에서 삭제됩니다. 스택 맨 위엔 이전의 실행 컨텍스가 위치하게 됩니다.

• Context: { x: 2, n: 2, 다섯 번째 줄 } pow(2, 2)
• Context: { x: 2, n: 3, 다섯 번째 줄 } pow(2, 3)

pow (2, 2)의 실행이 다시 시작됩니다. 서브 호출 pow (2, 1)의 결과를 알고 있으므로, 쉽게 x * pow (x, n - 1)를 계산해 4를 반환합니다.

그리고 다시 이전 컨텍스트가 스택 최상단에 위치하게 됩니다.

• Context: { x: 2, n: 3, 다섯 번째 줄 } pow(2, 3)

마지막 실행 컨텍스트까지 처리되면 pow (2, 3) = 8이라는 결과가 도출됩니다.

지금 보신 예시의 재귀 깊이는 3 입니다.

도식을 통해 살펴보았듯이, 재귀 깊이는 스택에 들어가는 실행 컨텍스트 수의 최댓값과 같습니다.

실행 컨텍스트는 메모리를 차지하므로 재귀를 사용할 땐 메모리 요구사항에 유의해야 합니다. n을 늘리면 n이 줄어들 때마다 만들어지는 n개의 실행 컨텍스트가 저장될 메모리 공간이 필요하기 때문입니다.

한편, 반복문 기반 알고리즘을 사용하면 메모리가 절약됩니다.

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

  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

반복을 사용해 만든 함수 pow는 컨텍스트를 하나만 사용합니다. 이 컨텍스트에서 i와 result가 변경됩니다. 실행 컨텍스트가 하나이기 때문에 n에 의존적이지 않고, 필요한 메모리가 적습니다. 사용 메모리 공간도 고정됩니다.

재귀를 이용해 작성한 코드는 반복문을 사용한 코드로 다시 작성할 수 있습니다. 반복문을 사용하면 대개 함수 호출의 비용(메모리 사용)이 절약됩니다.

하지만 코드를 다시 작성해도 큰 개선이 없는 경우가 있습니다. 조건에 따라 함수가 다른 재귀 서브 호출을 하고 그 결과를 합칠 때가 그렇습니다. 분기문이 복잡하게 얽혀있을 때도 메모리가 크게 절약되지 않습니다. 이런 경우엔 최적화가 필요하지 않을 수 있고 최적화에 드는 노력이 무용지물일 수 있습니다.

재귀를 사용하면 코드가 짧아지고 코드 이해도가 높아지며 유지보수에도 이점이 있습니다. 모든 곳에서 메모리 최적화를 신경 써서 코드를 작성해야 하는 것은 아닙니다. 우리가 필요한 것은 좋은 코드입니다. 이런 이유 때문에 재귀를 사용합니다.