[Javascript] 재귀, 스택

pow(x, n)

1. 반복을 통한 방법 : for loop

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

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

 

2. 재귀를 통한 방법 : 작업을 단순화하고 자기 자신을 호출함

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

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

- n == 1 일 때, 재귀의 base, 명확한 결괏값을 즉시 도출

- n == 1 이 아닐 때, 재귀 작업

 

Execution Context

- 함수 실행에 대한 세부 정보를 담고 있는 내부 데이터 구조

- 제어 흐름의 현재 위치, 변수의 현재 값, this의 값 등

- 재귀 호출 발생 시, 현재 함수의 실행이 일시 중지 -> 현재 함수의 Execution Context는 Stack에 저장됨 -> 서브 함수 실행을 위한 새로운 Execution Context 생성 -> 서브 함수 완료 시, Stack에서 일시 중지된 함수의 Execution Context를 꺼내와서(pop) 다시 이어서 실행

=> 서브 함수 호출이 계속될 수록 Stack에 쌓이는 Execution Context가 늘어남

 

Linked List

- 재귀적으로 정의된 자료 구조

- 배열에 비해 삽입과 삭제에 들어가는 비용이 적게 듬

- index를 통해 요소에 접근할 수 없음 (배열에 비해 탐색에 비용이 더 많이 듬)

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

 

 

 

출처

https://ko.javascript.info/recursion