자바스크립트 재귀와 스택

kiki97 ㅣ 2022. 10. 5. 02:17

문제 해결을 하다 보면 함수에서 다른 함수를 호출해야 할 때가 있습니다.

이때 함수가 자기 자신을 호출할 수도 있는데, 이를 재귀라고 부릅니다.

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

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

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)

pow (x, n)를 호출하면 위와같이 두 갈래로 나누어 코드가 실행된다.
n==1 일때 : 명확한 결과값을 즉시 도출하므로 이를 재귀 베이스라고 한다.
n==1 이 아닐때 : pow(x, n)은 x * pow(x, n -1)으로 표현할 수 있다. 이를 재귀 단계라고 부른다.
재귀 단계는 n이 1이 될 때까지 계속 이어진다.
즉, pow는 n==1이 될 때까지 재귀적으로 자신을 호출한다.
이렇게 재귀를 이용하면 함수 호출의 결과가 명확해질 때까지 함수 호출을 더 간단한 함수 호출로 계속 줄일 수 있다.

function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

가장 처음 하는 호출을 포함한 중첩 호출의 최대 개수는 재귀 깊이라고 한다.

pow(x, n)의 재귀 깊이는 n이다.

자바스크립트 엔진은 최대 재귀 깊이를 제한하는데, 만개 정도까진 확실히 허용하고 엔진에 따라 이보다 더 많은 깊이를 허용하는 경우도 있다. 하지만 대다수의 엔진이 십만까지는 다루지 못한다.

재귀 깊이 제한 떄문에 재귀를 실제 적용하는데 제약이 있긴 하지만, 재귀는 여전히 광범위하게 사용되고 있다.

재귀를 사용하면, 간결하고 유지보수가 쉬운 코드를 만들 수 있기 때문이다.

실행 중인 함수의 실행 절차에 대한 정보는 해당 함수의 실행 컨텍스트에 저장된다.

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

제어 흐름의 현재 위치, 변수의 현재 값, this의 값등 상세 내부 정보가 실행 컨텍스트에 저장된다.

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

함수 내부에 중첩 호출이 있을 때는 아래와 같은 절차가 수행된다.

kiki-dev