[JavaScript] 재귀와 스택 (recursion & stack)

1. 재귀(recursion)

재귀는 큰 목표 작업 하나를 동일하면서 간단한 작업 어려 개로 나눌 수 있을 때 유용한 프로그래밍 패턴이다.

• 목표 작업을 간단한 동작 하나와 목표 작업을 변형한 작업으로 단순화 시킬 때

• 특정 자료구조를다룰 때

사용됨.

문제 해결을 하다보면 함수에서 다른 함수를 호출해야 할 때가 있는데, 이 때 함수가 자기 자신을 호출할 때 이것을 "재귀"라고 부른다.

 

2. 재귀 예시

** x를 n제곱해주는 함수 pow(x,n)을 만들 때**

•for 문을 활용한 방법

function pow(x, n) {
	result = 1;
    
    for (let i=0; i < n; i++) {
    	result *= x;
    }
    
    return result;
}

•재귀를 활용한 방법

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

--> (n == 1) 일 때:결괏값을 즉시 도출하므로 이를 재귀의 베이스(base)라고 함.

--> (n == 1) 이 아닐 때: 재귀단계(recursive step)라고 부름. 여기선 목표작업 pow(x,n)을 간단한 동작 (x를 곱하기)과 목표작업을 변형한 작업 (pow(x,n-1))을 분할하여 n이 1이 될 때까지 반복하는 것.

이런식으로 n == 1이 될 때까지 자기 자신을 호출하는 것.

이렇게 재귀를 이용하면 함수 호출의 결과가 명확해질 때까지 함수 호출을 더 간단한 함수 호출로 계속 줄일 수 있다. ( for문을 활용한 코드보다 간결하고 짧기 때문에)

 ++ 가장 처음 호출을 포함한 중첩 호출의 최대 개수는 재귀깊이(recursion depth)라고 하는데, 자바스크립트 엔진을 최대 재귀 깊이를 제한한다. 10000개 정도까지는 확실히 허용하고, 엔진에 따라 이보다 더 많은 깊이를 허용하는 경우도 있지만, 대다수의 엔진이 십만까지는 다루지 못한다.

 

3. 실행 컨텍스트와 스택 (실제 재귀 호출이 어떻게 동작하나?)

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

(실행 컨텍스트란 함수 실행에 대한 세부 정보를 담고 있는 내부 데이터 구조이다. 함수 호출 1회당 1개의 실행 컨텍스트가 생성된다.)

 

**함수 내부에 중첩 호출이 있을 때**

• 현재 함수의 실행이 일시 중지됨.
• 중지된 함수와 연관된 실행 컨텍스트는 실행 컨텍스트 스택(execution context stack) 이라는 특별한 자료 구조에 저장됨.
• 중첩 호출이 실행됨.
• 중첩 호출 실행이 끝난 이후 실행 컨텍스트 스택에서 일시 중단한 함수의 실행 컨텍스트를 꺼내오고, 중단한 함수의 실행을 다시 이어감

2022.05.08 - [Front-end/JavaScript] - [JavaScript] 재귀함수 호출 예시

[JavaScript] 재귀함수 호출 예시

 

4. 재귀적 구조

재귀적으로 정의된 자료구조인 재귀적 자료구조는 자기 자신의 일부를 복제하는 형태의 자료구조이다.

이중 가장 대표적인 것이, 연결 리스트 이다.

 

객체를 정렬하여 어딘가에 저장하고 싶을 때, 가장 먼저 떠오르는 자료구조는 배열이다.

( let arr = [obj1, obj2, obj3] --> 이런 식으로)

하지만 배열은 요소 '삭제'와 '삽입'에 시간이 걸린다. arr.unshift() 혹은 arr.shift()와 같이 배열 맨 앞에 요소를 삭제하거나 삽입하는 연산을 할 때에는 새로운 공간을 만들고 삭제하기 위해 모든 요소의 번호를 다시 메겨야 하기 때문이다. (pop / push는 시간이 들지 않음)

따라서 빠르게 삽입 혹은 삭제를 해야 할 때는 배열 대힌 연결 리스트( linked list)라 불리는 자료구조를 사용한다.

 

연결리스트의 구성요소

• value
• next: 다음 연결 리스트 요소를 참조하는 프로퍼티. 다음 요소가 없을 땐 null이 됩니다.

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

//동일코드

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

위 연결리스트를 그림으로 표현하면

--> 연결리스트 안에는 객체가 여러개 있고, 각 객체엔 value와 이웃 객체를 가리키는 프로퍼티인 next가 있다. 체인의 시작 객체는 변수 list에 저장되어 있고, list의 next 프로퍼티를 가리키면서 이어지는 객체 어디든 도달할 수 있다. 

 

연결리스트를 사용하면 전체 리스트를 여러 부분으로 쉽게 나누고 합치는게 가능하다.

// 분할

let secondList = list.next.next;
list.next.next = null;

//합치기

list.next.next = secondList;

또한 쉽게 요소를 추가하거나 삭제할 수 있다.

// 처음 객체를 바꿔 리스트 맨 앞에 새로운 값을 추가

list = { value: "new item", next: list };

//이전 요소의 next를 변경해여 중간요소 제거

list.next = list.next.next;