재귀와 실행컨텍스트



자바스크립트의 동작원리의 핵심은 callstack에서 함수를 실행시키는 것이다.

그리고 개발자는 원하는 동작을 위해서, 사용자와 인터렉션을 통해 callstack에 함수를 쌓는다.

말그대로 스택의 자료구조를 가지고있기 때문에, 함수가 완전히 종료되고 나서야, 다음 함수를 실행한다.

그리고 이벤트루프를 통해서 callback queue에 쌓인 함수를 넣어주기 위해서는 callstack이 비어있어야 한다는 조건이 있다.

 

재귀

재귀란 것은, 함수가 자기자신을 호출하는 것을 말한다.

재귀는 왜 사용하는것일까?

크고 일련의 규칙이있는 문제를 작게 단순화하여 해결하기 위함이라고 생각한다.

예를들어서 거듭제곱하는 함수 pow를 구현한다고 가정하면 일반 for loop와 재귀를 통한 구현을 할 수있는데, 여기서 재귀의 장점이 보인다.

 

for loop

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

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

  return result;
}

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

 

재귀

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

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

 

이때 재귀는 반드시 종료되는 조건을 명시해야한다. 그렇지 않으면 callstack이 무한이 쌓여, 브라우저나 node가 멈춰버리는 현상을 경험한다. 이렇게 종료되는 조건을 명확한 값을 도출한다고 하고, 재귀 베이스라고한다.

가끔 생각없이 테스트하다가 그런적이있는데, 정상적으로 되는데 한 5분은 걸렸다..

자바스크립트가 동작되는 환경마다 callstack의 최대한도가 정해져있다.

아래는 대략적인 한도이다.

• Node.js: 11,034
• Firefox: 50,994
• Chrome: 10,402

크롬과, node가 가장 범용적인 환경임으로 1만정도는 확실히 허용한다고 생각할 수 있다.

 

그래서 재귀는 재귀만이 가진 장점이있으나, 깊이 제한 때문에 실제로 적용하는데 제약이 있지만, 위 코드에서 본것처럼 간결하고, 유지보수가 쉬운 코드를 작성할 수 있기 때문에 널리 사용된다.

 

알고리즘 문제를 재귀적으로 풀다가 보면, n이 1만을 넘어간다면 재귀말고 다른 방법을 고려해야한다.

실행 컨텍스트

아주 기본적인 내용인데, 함수는 호출이되면 돌아올 자리를 기억해야한다.

프로그래밍에서 모든건 메모리주소를 가지고있다. 그 주소를 가지고 참조를하거나, 함수가 실행되고서 돌아갈 위치를 찾아가는 것이다.

자바스크립트에서는 함수가 실행되면 관련된 정보들이 함수의 실행 컨텍스트(execution context)에 저장된다.

실행 건텍스트는 함수 실행에 관한 세부 정보를 담고있는 내부 데이터 구조이다.

제어흐름의 현재 위치, 변수의 현재값, this의값 등이 저장된다.

함수 호출 하나당 정확히 하나의 실행 컨텍스트가 생성된다.

 

이때 실행되고있는 함수 내에서 중첩된 함수 호출이 발생하면 현재 함수 실행이 일시 중지된다.

이 중지된 함수의 실행 컨텍스트는 실행 컨텍스트 스택(execution context stack)에 저장되고, 중첩된 함수를 실행한다.

중첩된함수의 실행이 끝나면 이 스택에서 쌓아두었던 실행 컨텍스트를 꺼내오고, 중된되었던 지점에서 다시 실행을 이어간다.

 

알고리즘 문제를 풀면서 재귀함수를 많이 사용하고있고, 특히나 DFS를 구현할 때 재귀로 많이 해결한다.

처음에는 재귀함수가 안익숙해서, 이런저런 방식으로 어쨋든 재귀만 아니면된다는 생각으로 문제를 많이 풀었었는데,

한번 재귀를 이해하고나서는, 어떻게든 재귀로 간단하게 문제를 해결할 수없을까를 생각하고있었다.

특히나 자바스크립트에서는 callback기법이 빈번하게 사용되어 stack과 실행컨텍스트 또 클로저와 같은 동작을 이해하기 위해서 재귀는 핵심적인 개념이라 생각한다.