6.1 재귀와 스택

재귀(recursion)

📢 함수가 자기 자신을 호출하는 것

◾️ 큰 목표 작업 하나를 동일하면서 간단한 작업 여러 개로 나눌 수 있을 때 유용한 프로그래밍 패턴이다.

◾️ 목표 작업을 간단한 동작 하나와 목표 작업을 변형한 작업으로 단순화 시킬 때도 재귀를 사용

◾️ 특정 자료구조를 다뤄야 할 때도 재귀가 사용

 

두 가지 사고방식

◾️ x를 n 제곱해 주는 함수 pow(x, n)을 만들어 보자

// pow 예시

pow(2, 2) = 4
pow(2, 3) = 8
pos(2, 4) = 16

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);
  }
}

console.log(pow(2, 3)); // 8

 

◾️ 재귀를 사용 했을 때 실행 과정 : pow(x, n)을 호출

pow(x, n) = ┌ if n = 1  = x
            └ else      = x * pow(x, n - 1)

1. n == 1일 때 : 명확한 결과값을 즉시 도출하므로 재귀의 베이스(base)라고 한다. pow(x, 1)은 x이다. 

2. n == 1이 아닐 때 : pow(x, n)은 x * pow(x, n - 1)로 표현할 수 있다. (수학식으론 xⁿ = x * xⁿ-¹) ➡️ 재귀단계(recursive step)

    목표 작업 pow(x, n)을 간단한 동작(x를 곱하기)과 목표 작업을 변형한 작업(pow(x, n-1))으로 분할

3. pow는 n == 1이 될 때까지 재귀적으로 자신을 호출한다. 

⏩  pow(2, 4)의 재귀 단계

1. pow(2, 4) = 2 * pow(2, 3)
2. pow(2, 3) = 2 * pow(2, 2)
3. pow(2, 2) =2 * pow(2, 1)
4. pow(2, 1) = 2

💡 재귀를 이용하면 함수 호출의 결과가 명확해질 때까지 함수 호출을 더 간단한 함수 호출로 계속 줄일 수 있다. 

 

◾️ 재귀를 사용하면 코드를 짧게 줄일 수 있다. 

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

◾️ 재귀 깊이(recursion depth) : 가장 처음 하는 호출을 포함한 중첩 호출의 최대 개수( pow(x, n)의 재귀 깊이는 n)

◾️ 자바스크립트 엔진은 최대 재귀 깊이를 제한한다(~십만). 제한을 완화하려고 엔진 내부에서 자동으로 'tail calls optimization'라는 최적화를 수행하긴 하지만 간단한 경우에만 적용된다. 

 

실행 컨텍스트와 스택

📢 재귀 호출의 동작

 

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

◾️ 실행 컨텍스트(execution context) : 함수 실행에 대한 세부 정보를 담고 있는 내부 데이터 구조( 제어 흐름의 현재 위치, 변수의 현재 값, this의 값 등)

◾️ 함수 호출 1회당 하나의 실행 컨텍스트가 생성된다.

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

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

1️⃣ pow(2, 3)

 

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

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

◾️ n == 1의 조건에 만족하지 못하기 때문에 실행 흐름은 if의 두 번째 분기로 넘어간다. →  x * pow(x, n - 1)

function pow(x, n){
  if(n == 1){
    return x;
  } else { 
    return x * pow(x, n - 1); // 현재 실행 흐름 위치
  }
}

◾️ 변수는 동일하지만, 실행 흐름의 위치가 변경되면서 실행 컨텍스트도 변경된다. 

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

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

 

2️⃣ pow(2, 2)

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

     1. 스택 최상단에 현재 컨텍스트가 '기록'된다.

     2. 서브 호출을 위한 새로운 컨텍스트가 만들어진다.

     3. 서브 호출이 완료되면 기존 컨텍스를 스택에서 꺼내(pop) 실행을 이어나간다. 

◾️ 서브 호출 pow(2, 2)가 시작될 때의 실행 컨텍스트 스택

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

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

⚠️ 주의

◾️ 한 줄에는 복수의 서브 호출(pow(…) + pow(…) + somethingElse(…))이 있을 수 있다.
◾️ 실행이 '서브 호출 바로 직후'에 시작된다. 

3️⃣ pow(2, 2)

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

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

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

 

4️⃣ 실행 종료

◾️ 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:1, 첫 번째 줄} call: pow(2,1)
Context : { x: 2, n: 2, 다섯 번째 줄} call: pow(2,2)
Context : { x: 2, n: 3, 다섯 번째 줄} call: pow(2, 3)

◾️ pow(2, 2)의 실행이 다시 시작된다. 서브 호출 pow(2, 1)의 결과로 x * pow (x, n - 1)를 계산해 4를 반환한다.

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

◾️ 마지막 실행 컨텍스트까지 처리되면 pow(2, 3) = 8 이라는 결과가 나온다.

◾️ pow(2, 3)은 재귀 깊이가 3이다. 

◾️ 재귀 깊이는 스택에 들어가는 실행 컨텍스트 수의 최댓값과 같다. 

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

 

◾️ 반복문 기반 알고리즘을 사용하면 메모리가 절약된다. 

◾️ 함수 pow는 하나의 컨텍스트만 사용한다. (컨텍스트에서 i와 result가 변경된다.)

◾️ 실행 컨텍스트가 하나이기 때문에 n에 의존적이지 않고, 필요한 메모리가 적다. 사용 메모리 공간도 고정된다. 

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

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

  return result;
}

 

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

◾️ 재귀를 사용하면 코드가 짧아지고 코드 이해도가 높아지며 유지보수에도 이점이 있다. 모든 곳에서 메모리 최적화를 신경 써서 코드를 작성해야 하는 것은 아니다. 

 

재귀적 순회

📢 재귀는 재귀적 순회(recursive traversal)를 구현할 때 사용하면 좋다. 

 

◾️ 회사의 임직원들을 표현한 객체 

◾️ 부서(sales)에는 여러 명의 직원이 있는데, 이를 배열로 표현할 수 있다. 

◾️ 부서는 하위 부서를 가질 수 있다. (development 부서는 sites와 internals 두 개의 하위 부서를 갖고, 각 하위 부서에도 직원이 있다.)

◾️ 하위 부서가 커지면 더 작은 단위의 하위 부서(또는 팀)로 쪼개질 가능성도 있다. 

let company = {
  sales: [{
    name: 'John',
    salary: 1000
  }, {
    name: 'Alice',
    salary: 1600
  }],

  development: {
    sites: [{
      name: 'Peter',
      salary: 2000
    }, {
      name: 'Alex',
      salary: 1800
    }],

    internals: [{
      name: 'Jack',
      salary: 1300
    }]
  }
};

 

모든 임직원의 급여를 더한 값을 구해야 한다

◾️ 반복문을 이용하면 중첩 반복의 깊이가 깊어지고 코드가 지저분해진다. 💡 재귀를 이용해보자!

     1. 임직원 배열을 가진 '단순한'부서(sales) - 간단한 반복문으로 급여 합계를 구할 수 있다.

     2. N개의 하위 부서가 있는 객체(development) - 각 하위 부서에 속한 임직원의 급여 합계를 얻기 위해 N번의 재귀 호출을 하고, 최종적으로 모든 하위부서 임직원의 급여를 더한다. 

 

◾️ 배열을 사용하는 첫 번째 경우는 간단한 경우로, 재귀의 베이스가 된다. 

◾️ 객체를 사용하는 두 번째 경우는 재귀 단계가 된다. 복잡한 작업은 작은 작업(하위 부서에 대한 반복문)으로 쪼갤 수 있다. 부서의 깊이에 따라 더 작은 작업으로 쪼갤 수 있는데, 결국 마지막엔 첫 번째 경우가 된다. 

let company = { // 동일한 객체(간결성을 위해 약간 압축함)
  sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 1600 }],
  development: {
    sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
    internals: [{name: 'Jack', salary: 1300}]
  }
};

// 급여 합계를 구해주는 함수
function sumSalaries(department) {
  if(Array.isArray(department)){ // sales부서(하위부서 X)
  	return department.reduce((prev, current) => prev + current.salary, 0);
  } else { // development부서 (하위부서 O)
  	let sum = 0;
    for(let subdep of Object.values(department)){
      sum += sumSalaries(subdep); // 재귀 호출로 각 하위 부서 임직원의 급여 총합을 구한다. 
    }
    return sum;
  }
}

console.log(sumSalaries(company)); // 7700

◾️ 하위 부서의 깊이와 상관없이 원하는 값을 구할 수 있다. 

◾️ 객체 {...}를 만나면 서브 호출이 만들어지는 반면, 배열 [...]을 만나면 더 이상의 서브 호출이 만들어지지 않고 결과가 바로 계산된다.

ℹ️ arr.reduce는 배열의 합을 계산해준다. 
ℹ️ Object.values는 프로퍼티의 값이 담긴 배열을 반환한다. 

 

재귀적 구조

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

◾️ 회사의 부서 객체는 두 가지 종류로 나뉜다.

     1. 사람들로 구성된 배열

     2. 하위 부서로 이루어진 객체 

◾️ HTML, XML도 재귀적 자료 구조 형태를 띤다. (HTML 문서에서 HTML 태그는 다음과 같은 항목으로 구성되기 때문)

     1. 일반 텍스트

     2. HTML-주석

     3. 이 외의 태그 (이 아래에 일반 텍스트, HTML-주석, 다른 HTML 태그가 올 수 있다.)

 

연결리스트

◾️ 재귀적 자료구조. 배열 대신 연결리스트를 사용하면 더 좋은 경우가 있다. 

◾️ 객체를 정렬하여 배열에 저장

◾️ 배열은 요소 '삭제'와 '삽입'에 들어가는 비용이 많이 든다는 문제가 있다. (새로운 obj를 위한 공간을 만들기 위해 index 번호를 다시 지정해야하기 때문)

◾️ arr.push/pop은 배열 끝에 요소를 추가하기 때문에 index를 다시 지정하지 않아도 된다. 

let arr = [obj1, obj2, obj3];

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

◾️ 연결리스트의 요소는 객체와 value, next 프로퍼티들을 조합해 정의할 수 있다. 

◾️ 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;

◾️ 체인의 시작 객체는 변수 list에 저장되어 있다. 각 객체엔 value와 이웃 객체를 가리키는 프로퍼티인 next가 있다. 

◾️ 연결 리스트를 사용하면 전체 리스트를 여러 부분으로 쉽게 나눌 수 있고, 다시 합치는 것도 가능하다. 

나누기

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

합치기

list.next.next = secondList;

◾️ 요소를 추가하거나 삭제할 수 있다. 리스트의 처음 객체를 바꾸면 리스트 맨 앞에 새로운 값을 추가할 수 있다. 

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

// list에 새로운 value를 추가
list = { value: 'new item', next: list };

◾️ 중간 요소를 제거하려면 이전 요소의 next를 변경해주면 된다. 

list.next = list.next.next;

 

◾️ 연결 리스트의 큰 단점은 인덱스만 사용해 요소에 쉽게 접근할 수 없다. N번째 값을 얻기 위해 첫 번째 항목부터 시작해 N번 next로 이동해야한다. 

◾️ 중간에 요소를 삽입하거나 삭제하는 연산이 항상 필요한 것은 아니다. 이럴 땐 순서가 있는 자료형 중에 큐(queue)나 데크(deque)를 사용할 수 있다. 

◾️ 연결 리스트는 다음과 같은 기능을 더해 개선할 수 있다.

    ◾️ 이전 요소를 참조하는 프로퍼티 prev를 추가해 이전 요소로 쉽게 이동하게 할 수 있다.

    ◾️ 리스트의 마지막 요소를 참조하는 변수 tail을 추가할 수 있다. (리스트 마지막에 요소를 추가하거나 삭제할 때 tail도 갱신해줘야한다.)

️  ◾️ 이 외에도 요구사항에 따라 구조를 변경할 수 있다. 

 

 

📝 요약

◽️ 재귀(recursion) : 함수 내부에서 자기 자신을 호출하는 것을 나타내는 프로그래밍 용어
◽️ 재귀 단계(recursion step) : 함수가 자신을 호출하는 단계
◽️ 재귀 베이스(recursion base) : 작업을 아주 간단하게 만들어서 함수가 더 이상은 서브 호출을 만들지 않게 해주는 인수
◽️ 재귀적으로 정의된 자료 구조는 자기 자신을 이용해 자료 구조를 정의한다. 
◽️ 재귀적으로 정의된 자료 구조에 속하는 연결 리스트는 리스트 혹은 null을 참조하는 객체로 이루어진 데이터 구조를 사용해 정의한다. 
◽️ 모든 재귀함수는 반복문을 사용한 함수로 다시 작성할 수 있다. 
◽️ 재귀를 사용하면 구현과 유지보수가 쉽다. 

 

 

 

---

📝 오늘 새롭게 배운 내용 📝

 

✅ 재귀는 내가 나를 호출한다. 내속엔 내가 너무도 많은 그런 관계...

✅ 이론적으로는 이해 할 수 있으나... 직접 코딩하려면 못할 거 같다 ㅠㅠ 

✅ 반복문이 3번 쓰일 상황이 생긴다면 재귀를 고려해보자. 

✅ 실행 컨텍스트 스택은 먼저 실행된 함수가 가장 아래에 저장된다. 동전지갑을 생각하면 된다!

✅ 함수가 한줄 한줄 실행하는 것 까지 자세하게 알려주셔서 감사한 마음이다. 

✅ 연결리스트!! 배열은 중간에 데이터를 삽입,제거하는게 부담이 되는 작업이다.

장난감 기차 연결 같은...

✅ 뭐든 이게 제일이야는 없고 상황에 따라 적절한 판단을 해야한다

✅ 과제를 풀어보자!!!!!!!

 

 

📌 [JAVASCRIPT_INFO 재귀와 스택]

https://ko.javascript.info/recursion

재귀와 스택