모던 자바스크립트 #6.1 재귀와 스택

두 가지 사고방식

함수 내부에서 자기 자신을 호출하는 것을 나타내는 프로그래밍 용어이다. 재귀 함수는 우아하게 원하는 문제를 해결할 때 자주 쓰인다.

x를 n제곱해 주는 함수

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

n == 1: 모든 절차가 간단해진다. 명확한 결괏값을 즉시 도출하므로 이를 재귀의 베이스(base) 라고 한다. basis 라고도 불리는 재귀의 베이스(base)는 작업을 아주 간단하게 만들어서 함수가 더 이상은 서브 호출을 만들지 않게 해주는 인수이다.
n == 1이 아닐 때: pow(x, n)은 pow(x, n-1)으로 표현될 수 있다. 수학식으론 xn = x * xn-1로 표현할 수 있다. 이를 재귀 단계(recursive step)이라고 한다. 여기서는 목표 작업인 pow(x, n)을 간단한 동작(x를 곱하기)과 목표 작업을 변형한 작업 pow(x, n - 1)으로 분할했다. 재귀 단계는 n이 1이 될 때까지 계속 이어진다.
중첩 호출의 최대 개수는 재귀 깊이라고 한다. pow(x, n) 의 재귀 깊이는 n이다.

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

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

실행 컨텍스트와 스택

실행 중인 함수의 실행 절차에 대한 정보는 해당 함수의 실행 컨텍스트(execution context)에 저장된다. 실행 컨텍스트는 함수 실행에 대한 세부 정보를 담고 있는 데이터 구조이다. 제어 흐름의 현재 위치, 변수의 현재 값, this의 값 등 상세 내부 정보가 실행 컨텍스트에 저장된다. 함수 호출 일 회당 하나의 실행 컨텍스트가 생성된다.

함수 내부에 중첩 호출이 있을 때는 다음과 같은 절차가 수립된다.

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

예를 들어, pow(2,3)을 호출하면 다음과 같이 3개의 실행 컨텍스트가 최대로 쌓일 때는 다음과 같다.

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

재귀의 깊이는 3이다. 재귀 깊이는 스택에 들어가는 실행 컨텍스트 수의 최댓값과 같다. 실행 컨텍스트는 메모리를 차지하므로 재귀를 사용할 땐 메모리 요구사항에 유의해야 한다. 이때 반복문 기반 알고리즘을 사용하면 메모리가 절약된다.

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

반복을 사용해 만든 함수 pow 는 컨텍스트를 하나만 사용한다. 이 컨텍스트에서 i와 result가 변경된다. n에 의존적이지 않고, 필요한 메모리가 적다. 사용 메모리 공가도 고정된다. 모든 재귀 함수는 반복문을 사용한 함수로 다시 작성할 수 있다. 최적화를 위해 반복문으로 다시 작성해야 할 수도 있다. 그러나 상당수 작업은 재귀를 사용해도 만족할 만큼 빠르게 동작한다. 재귀를 사용하면 구현과 유지보수가 쉽다는 장점이 있다.

재귀적 순회(recursive traversal)

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

모든 임직원의 급여를 더한 값을 구하려면 어떻게 해야 할까? 구조가 단순하지 않기 때문에 반복문을 사용해서는 중첩의 깊이가 매우 깊어질 것이다.

임직원 급여 합계를 구할 때는 두 가지 경우로 나눠 생각할 수 있다.

임직원 배열을 가진 ‘단순한’ 부서 - 간단한 반복문으로 급여 합계를 구할 수 있다. => 재귀의 베이스
N 개의 하위 부서가 있는 객체 - 각 하위 부서에 속한 임직원의 급여 합계를 얻기 위해 N 번의 호출을 하고, 최종적으로 모든 하위부서 임직원의 급여를 더한다. => 재귀 단계

복잡한 작업은 작은 작업(하위 부서에 대한 반복문)으로 쪼갤 수 있다. 부서의 깊이에 따라 더 작은 작업으로 쪼갤 수 있는데, 결국 마지막엔 첫 번째 경우가 된다.

function sumSalaries(department) {
  if (Arrays.isArray(department)) {
    return department.reduce((prev, current) => prev + current.salary, 0); // 배열의 요소를 합함
  } else {
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep);
    }
  }
}

arr.reduce는 배열의 합을 계산해 준다. 첫번재 인수( accumulator)는 앞서 호출했던 함수들의 결과가 누적되어 저장되는 누산기라고 생각하면 된다. 마지막 함수까지 호출되면 이 값은 reduce의 반환값이 된다. 두 번째 인수(item)은 현재 배열 요소를 뜻한다.

department.reduce((prev, current) => prev + current.salary, 0)
함수 최초 호출 시, reduce의 마지막 인수인 0(초기값)이 prev에 할당된다. current엔 배열의 첫 번째 요소가 할당된다.
두 번재 호출 시, prev에 두 번째 요소가 더해진다.
세 번째 호출 시, prev에 세 번째 요소가 더해진다.

for(val of Object.values(obj))에서 쓰인 Object.values는 프로퍼티의 값이 담긴 배열을 반환한다.

재귀적 구조

재귀적으로 정의된 자료구조는 자기 자신을 이용해 자료 구조를 정의한다.

회사 구조도 재귀적 자료 구조이다. 회사의 부서 객체는 두 가지 종류로 나뉜다.

사람으로 구성된 배열
하위 부서로 이루어진 객체

HTML 문서의 HTML 요소 트리나 부서를 나타내는 트리 역시 재귀적인 자료 구조로 만들었다. HTML문서에서 HTML 태그는 다음과 같은 항목으로 구성되기 때문이다.

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

이렇게 재귀적인 자료구조를 사용하면 가지가 여러 개인데 각 가지가 여러 가지로 뻗쳐 나가는 형태로 자료 구조를 만들 수 있다.

예시에서 구현한 sumSalary 같은 재귀 함수를 사용하면 각 분기(가지)를 순회할 수 있다.

재귀적으로 정의된 자료구조에 속하는 연결 리스트는 리스트 혹은 null을 참조하는 객체로 이루어진 데이터 구조를 사용해 정의된다.

list = {value, next -> list};

연결 리스트

배열은 삭제와 삽입에 들어가는 비용이 많다.

arr.unshift(obj)를 수행하려면 새로운 obj를 위한 공간을 만들기 위해 모든 요소의 번호를 다시 매겨야 한다. 배열이 커지면 연산 수행 시간이 더 걸린다. 요소 전체의 번호를 다시 매기지 않아도 되는 조작은 배열 끝에 하는 연산인 arr.push/pop 뿐이다.

빠르게 삽입 혹은 삭제를 할 때 배열 대신 연결 리스트라는 자료구조를 사용한다. 연결 리스트의 요소는 객체 아래의 프로퍼티들을 조합해 정의할 수 있다.

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;

리스트의 처음 객체를 바꾸면 리스트 맨 앞에 새로운 값을 추가할 수 있다.

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

중간 요소를 제거하려면 이전 요소의 next를 변경해준다.

list.next = list.next.next;

그럼 이제 value 1은 체인에서 제외되고, 다른 곳에 따로 저장하지 않는다면 자동으로 메모리에서 제거된다.

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

위에서 구현한 연결 리스트는 다음과 같은 기능을 더해 개선할 수 있다.

이전 요소를 참조하는 프로퍼티 prev 를 추가해 이전 요소로 쉽게 이동할 수 있다.
리스트의 마지막 요소를 참조하는 변수 trai를 추가할 수 있다. 리스트 마지막에 요소를 추가하거나 삭제할 때 tail 갱신해 줘야 한다.
이 외에도 요구사항에 따라 구조를 변경할 수 있다.

과제

1. 주어진 숫자까지의 모든 숫자 더하기

숫자 1 + 2 + ... + n을 계산하는 함수 sumTo (n)을 만들어보세요.

for 반복문 사용하기

function sumTo(n) {
  let result = 0;
  for (let i = 1; i <= n; i++) {
    result += i;
  }
  return result;
}

재귀 사용하기

function sumTo(n) {
  if (n == 1) return 1;
  return n + sumTo(n-1);
}

등차수열 공식 사용하기

function sumTo(n) {
  return n * (n + 1) / 2;
}
  
alert( sumTo(100) );

세 가지 방법 중 어떤 방법이 가장 빠른가요? 어떤 방법이 가장 느린가요? 이유도 함께 제시해주세요.
등차수열 공식이 가장 빠르다. for 반복문과 재귀는 n번 반복된다. 즉 O(n)이다. 그러나 등차수열 공식을 사용하면 O(1)이다. 재귀를 사용하는 경우 중첩 호출과 실행 컨텍스트 스택 관리가 필요하기 때문에 더 많은 자원을 사용해서 가장 느리다.
재귀를 사용해 sumTo(100000)를 계산할 수 있을까?
자바스크립트 엔진은 최대 재귀 깊이를 지원한다. 만개 정도까지는 기본적으로 지원하지만, 대다수의 엔진이 십만까지는 지원하지 않는다. 이 제한을 완화하기 위해 tail calls optimization라는 최적화를 수행하긴 하지만, 모든 곳에 적용되는 것은 아니고 간단한 경우메나 적용된다.

답: 등차수열이 가장 빠르다. n에 관계 없이 오직 세 개의 연산만 수행하면 되기 때문이다. 반복을 사용하는 방법은 두 번째로 빠르다. 재귀를 사용하는 방법은 중첩 호출과 실행 스택 관리가 추가로 필요하기 때문에 더 많은 자원을 소비한다. 따라서 속도가 느리다.
몇몇 자바스크립트 엔진은 ‘tail call’ 최적화를 지원한다. sumTo처럼 함수가 가장 마지막으로 수행하는 연산이 재귀 호출이라면 외부 함수는 실행을 다시 시작할 필요가 없기 때문에 엔진은 실행 컨텍스트를 기억할 필요가 없다. 메모리 부담이 사라지는 것이다. 그렇기 때문에 sumTo(100000)같은 계산이 가능하다. 그런데 자바스크립트 엔진이 tail call 최적화를 지원하지 않는다면(대부분의 엔진이 이를 지원하지 않는다) 엔진에 설정된 스택 사이즈 제한을 넘었기 때문에 최대 스택 사이즈 초과 에러가 발생한다.
= Q. 질문

2. 팩토리얼 계산하기

재귀를 사용하여 n!을 계산하는 함수, factorial(n) 만들어 보시오.

function factorial(n) {
  if (n == 1) return n;
  return n * factorial(n - 1);
}

피보나치 수 계산하기

피보나치 수는 첫째와 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열로, Fn = Fn-1 + Fn-2라는 공식으로 표현할 수 있다.

처음 두 항은 1이고, 그 다음 항들은 2(1+1), 3(1+2), 5(2+3)이므로 전체 수열은 1, 1, 2, 3, 5, 8, 13, 21…의 형태를 띈다. n 번째 피보나치 수를 반환하는 함수 fib(n)을 작성하라.

function fib(n) {
  if (n <= 2) return 1; 
  return fib(n-1) + fib(n-2);
}

위와 같이 구현하였더니 연산 시간이 너무 오래 걸렸다.

해답에 의하면 fib(77)을 호출했을 때 CPU 리소스를 다 잡아먹어서 잠시 엔진이 멈출 수도 있다고 한다. 연산이 느려지는 이유는 함수 호출 중에 수많은 서브 호출이 일어나기 때문이다.

fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)

fib(3)은 fib(5)와 fib(4)를 계산할 때 모두 필요하다. 그러므로 fib(3)은 완전히 다른 두 곳에서 독립적으로 호출되고 평가된다.

Screen Shot 2021-03-28 at 5 50 21 PM

그림을 보면 fib(2)는 세 번이나 평가된다.

이런 단점은 이미 평가된 값을 어딘가에 저장해놓는 식으로 최적화할 수 있다. fib(3) 계산이 끝나면 이 겨로가를 어딘가에 저장해놓았다가 같은 값이 필요할 때 저장된 값을 불러오는 식이다.

또는 재귀가 아닌 반복문을 기반으로 알고리즘을 짤 수 있다. 1과 2로 시작하는 반복문으로 fib(3)을 구하고, 이를 기반으로 fib(4)를 구하고, 이를 기반으로 fib(5)를 구하는 식으로 알고리즘을 구현할 수 있다. 이렇게 구현하면 이전 두 항의 값만 저장하면 된다.

function fib(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}

이런 접근 방법을 bottom-up 다이나믹 프로그래밍(dynamic programming, 동적 계획법)이라고 부른다.

dynamic programming(기억하기 프로그래밍): 메모이제이션은 재귀 호출 시, 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법이다. 메모이제이션이 동적 프로그램 중에 하나이다.
알고리즘을 짤 때 분할정복 기법은 큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법이다. 작은 문제를 풀다보면 같은 문제들을 반복해서 푸는 경우가 생긴다. 그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법이 동적 프로그래밍이다.
출처: https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182

3. 단일 연결 리스트 출력하기

리스트 내 항목을 차례대로 하나씩 출력해주는 함수 printList(list)를 반복과 재귀를 사용한 답안을 각각 만들어보자. 그리고 어떤 것이 좋은 코드인지 생각해보자.

재귀

function printList (list) {
  console.log(list.value);
  if (list.next) return;
  printList(list.next);
}

반복

function printList (list) {
  while(list != null) { /*while(list)*/
    console.log(list.value);
    list = list.next;
  }
}

=> 나는 list를 바로 사용했는데, 해답에서는 tmp 변수에 저장하였다. 나처럼 하면 함수를 확장할 때 list를 가지고 뭔가를 할 때 문제가 생길 것이다. 또한 좋은 변수명이 무엇인가를 생각해 봤을 때도 리스트를 임시 변수 tmp에 저장하는 것이 좋다. list에는 리스트 그 자체가 저장되어 있는 것이 좋다.

function printList(list) {
  let tmp = list;
  while(tmp) {
    console.log(list.value);
    tmp = tmp.next;
  }
}

반복문을 사용하면 중첩 함수를 호출하는 데 추가적인 리소스를 사용하지 않아, 리소스를 좀 더 효율적으로 사용한다. 반면 재귀를 사용한 방법은 코드 길이가 짧고 이해하기가 쉽다는 장점이 있다.

단일 연결 리스트를 역순으로 출력하기

반복

function printListDesc(list) {
  let tmp = list;
  let arr = [];
  while(tmp) {
    arr.push(tmp.value);
    tmp = tmp.next;
  }
  for (let i = arr.length - 1; i >= 0; i--) {
    console.log(arr[i]);
  }
}

재귀

내가 푼 방법

function printListDesc(list) {
  if (!list) return;
  printListDesc(list.next);
  console.log(list.value);
}

해답

function printListDesc(list) {
  if (list.next) {
    printListDesc(list.next);
  }
  printListDesc(list.value);
}

모던 자바스크립트 #6.1 재귀와 스택

두 가지 사고방식

실행 컨텍스트와 스택

재귀적 순회(recursive traversal)

재귀적 구조

과제

Further Reading

모던 자바스크립트 #2.1. Hello, world!

모던 자바스크립트 #2.2. 코드 구조

모던 자바스크립트 #2.3. 엄격 모드

Trending Tags