2024년 7월 9일

재귀와 스택

함수에 대해 좀 더 깊이 알아보도록 하겠습니다.

함수 심화학습, 첫 번째 주제는 재귀(recursion) 입니다.

프로그래밍을 새롭게 학습하는 초심자가 아니라 이 주제에 익숙하시다면, 본 챕터를 건너뛰어도 괜찮습니다.

재귀는 큰 목표 작업 하나를 동일하면서 간단한 작업 여러 개로 나눌 수 있을 때 유용한 프로그래밍 패턴입니다. 목표 작업을 간단한 동작 하나와 목표 작업을 변형한 작업으로 단순화시킬 수 있을 때도 재귀를 사용할 수 있습니다. 곧 살펴보겠지만, 특정 자료구조를 다뤄야 할 때도 재귀가 사용됩니다.

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

두 가지 사고방식

간단한 예시를 시작으로 재귀에 대해 알아보겠습니다. xn 제곱해 주는 함수 pow(x, n)를 만들어봅시다. pow(x, n)xn번 곱해주기 때문에 아래 결과를 만족해야 합니다.

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

구현하는 방법은 두 가지가 있습니다.

  1. 반복적인 사고를 통한 방법: for 루프

    function pow(x, n) {
      let result = 1;
    
      // 반복문을 돌면서 x를 n번 곱함
      for (let i = 0; i < n; i++) {
        result *= x;
      }
    
      return result;
    }
    
    alert( pow(2, 3) ); // 8
  2. 재귀적인 사고를 통한 방법: 작업을 단순화하고 자기 자신을 호출함

    function pow(x, n) {
      if (n == 1) {
        return x;
      } else {
        return x * pow(x, n - 1);
      }
    }
    
    alert( pow(2, 3) ); // 8

재귀를 이용한 예시가 반복문을 사용한 예시와 어떤 부분에서 근본적인 차이가 있는지 유심히 살펴보시기 바랍니다.

pow (x, n)을 호출하면 아래와 같이 두 갈래로 나뉘어 코드가 실행됩니다.

              if n==1  = x
             /
pow(x, n) =
             \
              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)으로 표현할 수 있습니다. 수학식으론 xn = x * xn-1로 표현할 수 있겠죠. 이를 재귀 단계(recursive step) 라고 부릅니다. 여기선 목표 작업 pow(x, n)을 간단한 동작(x를 곱하기)과 목표 작업을 변형한 작업(pow(x, n - 1))으로 분할하였습니다. 재귀 단계는 n1이 될 때까지 계속 이어집니다.

즉, pown == 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

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

재귀를 사용한 코드는 짧습니다.

재귀를 사용한 코드는 반복적 사고에 근거하여 작성한 코드보다 대개 짧습니다.

if 대신 조건부 연산자 ?를 사용하면 pow (x, n)를 더 간결하고 읽기 쉽게 만들 수도 있습니다.

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

가장 처음 하는 호출을 포함한 중첩 호출의 최대 개수는 재귀 깊이(recursion depth) 라고 합니다. pow(x, n)의 재귀 깊이는 n입니다.

자바스크립트 엔진은 최대 재귀 깊이를 제한합니다. 만개 정도까진 확실히 허용하고, 엔진에 따라 이보다 더 많은 깊이를 허용하는 경우도 있습니다. 하지만 대다수의 엔진이 십만까지는 다루지 못합니다. 이런 제한을 완화하려고 엔진 내부에서 자동으로 'tail calls optimization’라는 최적화를 수행하긴 하지만, 모든 곳에 적용되는 것은 아니고 간단한 경우에만 적용됩니다.

재귀 깊이 제한 때문에 재귀를 실제 적용하는데 제약이 있긴 하지만, 재귀는 여전히 광범위하게 사용되고 있습니다. 재귀를 사용하면, 간결하고 유지보수가 쉬운 코드를 만들 수 있기 때문입니다.

실행 컨텍스트와 스택

실제 재귀 호출이 어떻게 동작하는지 알아봅시다. 이를 위해서 함수의 내부 동작에 대해 살펴보도록 하겠습니다.

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

실행 컨텍스트는 함수 실행에 대한 세부 정보를 담고 있는 내부 데이터 구조입니다. 제어 흐름의 현재 위치, 변수의 현재 값, this의 값(여기선 다루지 않음) 등 상세 내부 정보가 실행 컨텍스트에 저장됩니다.

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

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

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

이제 pow (2, 3)가 호출되면 실행 컨텍스트에서 무슨 일이 일어나는지 살펴봅시다.

pow(2, 3)

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

이를 도식화하면 다음과 같습니다.

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

위 그림은 함수 실행이 시작되는 순간을 나타낸 것입니다. 지금 상태론 조건 n == 1을 만족하지 못하므로 실행 흐름은 if의 두 번째 분기로 넘어갑니다.

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

alert( pow(2, 3) );

변수는 동일하지만, 실행 흐름의 위치가 변경되면서 실행 컨텍스트도 다음과 같이 변경됩니다.

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

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

pow(2, 2)

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

지금 보고 있는 예시에선 실행 컨텍스트 스택에 동일한 함수 pow를 호출하였는데, 이는 중요치 않습니다. 모든 함수에 대해 아래 프로세스가 똑같이 적용됩니다.

  1. 스택 최상단에 현재 컨텍스트가 '기록’됩니다.
  2. 서브 호출을 위한 새로운 컨텍스트가 만들어집니다.
  3. 서브 호출이 완료되면. 기존 컨텍스트를 스택에서 꺼내(pop) 실행을 이어나갑니다.

다음은 서브 호출 pow (2, 2)이 시작될 때의 실행 컨텍스트 스택입니다.

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

굵은 테두리로 표시한 새 실행 컨텍스트는 상단에, 기존 컨텍스트는 하단에 있네요.

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

주의:

예시엔 한 줄에 서브 호출 하나만 있기 때문에, 그림에서 '줄’이라는 단어를 사용했습니다. 하지만 한 줄에는 pow(…) + pow(…) + somethingElse(…) 같이 복수의 서브 호출이 있을 수 있습니다.

따라서 좀 더 정확히는 실행이 '서브 호출 바로 직후’에 시작된다고 이야기 할 수 있습니다.

pow(2, 1)

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

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

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

기존 컨텍스트 두 개가 밑에, pow (2, 1)에 상응하는 컨텍스트가 맨 위에 있는 것을 확인할 수 있습니다.

실행 종료

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

pow (2, 2)의 실행이 다시 시작됩니다. 서브 호출 pow (2, 1)의 결과를 알고 있으므로, 쉽게 x * pow (x, n - 1)를 계산해 4를 반환합니다.

그리고 다시 이전 컨텍스트가 스택 최상단에 위치하게 됩니다.

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

마지막 실행 컨텍스트까지 처리되면 pow (2, 3) = 8이라는 결과가 도출됩니다.

지금 보신 예시의 재귀 깊이는 3 입니다.

도식을 통해 살펴보았듯이, 재귀 깊이는 스택에 들어가는 실행 컨텍스트 수의 최댓값과 같습니다.

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

한편, 반복문 기반 알고리즘을 사용하면 메모리가 절약됩니다.

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

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

  return result;
}

반복을 사용해 만든 함수 pow는 컨텍스트를 하나만 사용합니다. 이 컨텍스트에서 iresult가 변경됩니다. 실행 컨텍스트가 하나이기 때문에 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
    }]
  }
};

회사엔 부서가 있습니다.

  • 부서에는 여러 명의 직원이 있는데, 이를 배열로 표현할 수 있습니다. sales 부서의 John과 Alice라는 2명의 직원을 배열 요소로 표현해 보았습니다.

  • 부서는 하위 부서를 가질 수 있습니다. development 부서는 sitesinternals라는 두 개의 하위 부서를 갖습니다. 각 하위부서에도 직원이 있습니다.

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

    sites 부서는 미래에 siteAsiteB로 나뉠 수 있습니다. 이렇게 나눠진 부서가 미래에 더 세분화될 수도 있죠. 미래에 벌어질 일까진 나타내지 않았지만, 이러한 가능성도 있다는 걸 염두에 두어야 합니다.

자, 이제 모든 임직원의 급여를 더한 값을 구해야 한다고 해봅시다. 어떻게 할 수 있을까요?

구조가 단순하지 않기 때문에 반복문을 사용해선 구하기 쉽지 않아 보입니다. 가장 먼저 떠오르는 생각은 company를 대상으로 동작하는 for 반복문을 만들고 한 단계 아래의 부서에 중첩 반복문를 돌리는 것일 겁니다. 그런데 이렇게 하면 sites 같은 두 단계 아래의 부서에 속한 임직원의 급여를 뽑아낼 때 또 다른 중첩 반복문이 필요합니다. 세 단계 아래의 부서가 미래에 만들어진다고 가정하면 또 다른 중첩 반복문이 필요하겠죠. 얼마만큼의 깊이까지 중첩 반복문을 만들 수 있을까요? 객체를 순회하는 중첩 반복문의 깊이가 3~4개가 되는 순간 코드는 정말 지저분해질 겁니다.

재귀를 이용한 풀이법을 시도해 봅시다.

앞서 본 바와 같이 임직원 급여 합계를 구할 때는 두 가지 경우로 나누어 생각할 수 있습니다.

  1. 임직원 배열 을 가진 ‘단순한’ 부서 – 간단한 반복문으로 급여 합계를 구할 수 있습니다.
  2. N개의 하위 부서가 있는 객체 – 각 하위 부서에 속한 임직원의 급여 합계를 얻기 위해 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)) { // 첫 번째 경우
    return department.reduce((prev, current) => prev + current.salary, 0); // 배열의 요소를 합함
  } else { // 두 번째 경우
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // 재귀 호출로 각 하위 부서 임직원의 급여 총합을 구함
    }
    return sum;
  }
}

alert(sumSalaries(company)); // 7700

짧고 이해하기 쉬운 코드로 원하는 기능을 구현하였습니다. 재귀의 강력함은 여기에 있습니다. 하위 부서의 깊이와 상관없이 원하는 값을 구할 수 있게 되었네요.

아래는 호출이 어떻게 일어나는지를 나타낸 그림입니다.

그림을 보면 규칙을 쉽게 확인할 수 있습니다. 객체 {...}를 만나면 서브 호출이 만들어지는 반면, 배열 [...]을 만나면 더 이상의 서브 호출이 만들어지지 않고 결과가 바로 계산됩니다.

함수 내부에선 앞서 학습한 두 문법을 사용하고 있는 것도 눈여겨보시기 바랍니다.

  • 배열과 메서드 챕터에서 학습한 메서드 arr.reduce는 배열의 합을 계산해 줍니다.
  • for(val of Object.values (obj))에서 쓰인 Object.values는 프로퍼티의 값이 담긴 배열을 반환합니다.

재귀적 구조

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

위에서 살펴본 회사 구조 역시 재귀적 자료 구조 형태입니다.

회사의 부서 객체는 두 가지 종류로 나뉩니다.

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

웹 개발자에게 익숙한 HTML과 XML도 재귀적 자료 구조 형태를 띱니다.

HTML 문서에서 HTML 태그는 아래와 같은 항목으로 구성되기 때문입니다.

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

이렇게 다양한 곳에서 재귀적으로 정의된 자료구조가 쓰입니다.

다음은 '연결 리스트’라는 재귀적 자료 구조를 살펴보면서 재귀적 구조에 대해 더 알아보도록 하겠습니다. 몇몇 상황에서 배열 대신 연결 리스트를 사용하면 더 좋은 경우가 있습니다.

연결 리스트

객체를 정렬하여 어딘가에 저장하고 싶다고 가정해 봅시다.

가장 먼저 떠오르는 자료 구조는 아마 배열일 겁니다.

let arr = [obj1, obj2, obj3];

하지만 배열은 요소 '삭제’와 '삽입’에 들어가는 비용이 많이 든다는 문제가 있습니다. arr.unshift(obj) 연산을 수행하려면 새로운 obj를 위한 공간을 만들기 위해 모든 요소의 번호를 다시 매겨야 하죠. 배열이 커지면 연산 수행 시간이 더 걸리게 됩니다. arr.shift()를 사용할 때도 마찬가지입니다.

요소 전체의 번호를 다시 매기지 않아도 되는 조작은 배열 끝에 하는 연산인 arr.push/pop 뿐이죠. 앞쪽 요소에 무언가를 할 때 배열은 이처럼 꽤 느립니다.

빠르게 삽입 혹은 삭제를 해야 할 때는 배열 대신 연결 리스트(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에 저장되어 있습니다. 우리는 listnext 프로퍼티를 이용해 이어지는 객체 어디든 도달할 수 있습니다.

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

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;

list.next1이 아닌 2value로 갖는 객체를 가리키게 만들어보았습니다. 이제 value 1은 체인에서 제외됩니다. 이 객체는 다른 곳에 따로 저장하지 않으면 자동으로 메모리에서 제거됩니다.

지금까지 살펴본 바와 같이 연결 리스트는 배열과는 달리 대량으로 요소 번호를 재할당하지 않으므로 요소를 쉽게 재배열할 수 있다는 장점이 있습니다.

물론 연결 리스트가 항상 배열보다 우월하지는 않습니다. 그렇지 않았다면 모든 사람들이 연결 리스트만 사용했겠죠.

연결 리스트의 가장 큰 단점은 번호(인덱스)만 사용해 요소에 쉽게 접근할 수 없다는 점입니다. 배열을 사용하면 arr[n]처럼 번호 n만으로도 원하는 요소에 바로 접근할 수 있습니다. 그러나 연결 리스트에선 N번째 값을 얻기 위해 첫 번째 항목부터 시작해 Nnext로 이동해야 합니다.

그런데 중간에 요소를 삽입하거나 삭제하는 연산이 항상 필요한 것은 아닙니다. 이럴 땐 순서가 있는 자료형 중에 큐(queue)나 데크(deque)를 사용할 수 있습니다. 데크를 사용하면 양 끝에서 삽입과 삭제를 빠르게 수행할 수 있습니다.

위에서 구현한 연결 리스트는 아래와 같은 기능을 더해 개선할 수 있습니다.

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

요약

지금까지 나온 용어를 정리해봅시다.

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

    함수가 자신을 호출하는 단계를 재귀 단계(recursion step) 라고 부릅니다. basis라고도 불리는 재귀의 베이스(base) 는 작업을 아주 간단하게 만들어서 함수가 더 이상은 서브 호출을 만들지 않게 해주는 인수입니다.

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

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

    list = {value, next -> list}

    HTML 문서의 HTML 요소 트리나 위에서 다룬 부서를 나타내는 트리 역시 재귀적인 자료 구조로 만들었습니다. 이렇게 재귀적인 자료 구조를 사용하면 가지가 여러 개인데 각 가지가 여러 가지로 뻗쳐 나가는 형태로 자료 구조를 만들 수 있습니다.

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

모든 재귀 함수는 반복문을 사용한 함수로 다시 작성할 수 있습니다. 최적화를 위해 반복문으로 다시 작성해야 할 수도 있죠. 그러나 상당수 작업은 재귀를 사용해도 만족할 만큼 빠르게 동작합니다. 재귀를 사용하면 구현과 유지보수가 쉽다는 장점도 있습니다.

과제

중요도: 5

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

예시:

sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
sumTo(4) = 4 + 3 + 2 + 1 = 10
...
sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050

아래 방법을 사용해 세 가지 답안을 만들어보세요.

  1. for 반복문 사용하기
  2. 재귀 사용하기(n > 1일 때 sumTo(n) = n + sumTo(n-1))
  3. 등차수열 공식 사용하기

예시:

function sumTo(n) { /*... 답안은 여기에 작성 ... */ }

alert( sumTo(100) ); // 5050

더 생각해보기 1: 세 가지 방법 중 어떤 방법이 가장 빠른가요? 어떤 방법이 가장 느린가요? 이유도 함께 제시해주세요.

더 생각해보기 2: 재귀를 사용해 sumTo (100000)를 계산할 수 있을까요?

반복문 사용하기:

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

alert( sumTo(100) );

재귀 사용하기:

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

alert( sumTo(100) );

등차수열의 합공식 sumTo(n) = n*(n+1)/2 사용하기:

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

alert( sumTo(100) );

더 생각해보기 1: 등차수열의 합공식을 사용하는 방법이 가장 빠릅니다. n에 관계없이 오직 세 개의 연산만 수행하면 되니까요. 수학은 항상 뭔가에 도움을 줍니다!

반복을 사용하는 방법은 두 번째로 빠릅니다. 재귀를 사용하는 방법과 반복문을 사용하는 방법 모두 같은 수의 숫자를 더하는 것에서 같지만, 재귀를 사용하는 방법은 중첩 호출과 실행 스택 관리가 추가로 필요하기 때문에 더 많은 자원을 소비합니다. 따라서 속도가 더 느리죠.

더 생각해보기 2: 몇몇 자바스크립트 엔진은 ‘tail call’ 최적화를 지원합니다. 위 함수 sumTo처럼 함수가 가장 마지막으로 수행하는 연산이 재귀 호출이라면 외부 함수는 실행을 다시 시작할 필요가 없기 때문에 엔진은 실행 컨텍스트를 기억할 필요가 없어집니다. 메모리 부담이 사라지는 거죠. 그렇기 때문에 sumTo(100000)같은 계산이 가능한 것입니다. 그런데 자바스크립트 엔진이 tail call 최적화를 지원하지 않는다면(대부분의 엔진이 이를 지원하지 않습니다) 엔진에 설정된 스택 사이즈 제한을 넘었기 때문에 최대 스택 사이즈 초과 에러가 발생합니다.

중요도: 4

팩토리얼(factorial)은 n이 자연수일 때, 1부터 n까지의 모든 자연수의 곱을 의미합니다. n 팩토리얼은 n!으로 표시합니다.

팩토리얼은 아래와 같이 정의할 수도 있습니다.

n! = n * (n - 1) * (n - 2) * ...*1

자연수 n에 대한 n 팩토리얼:

1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120

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

alert( factorial(5) ); // 120

힌트: n!n * (n-1)!입니다. 3! = 3 * 2! = 3 * 2 * 1! = 6같이 말이죠.

팩토리얼은 그 정의에 따라 n!n * (n-1)!로 바꿔쓸 수 있습니다.

따라서 factorial(n)의 결과는 nfactorial(n-1)의 결과를 곱한 값이 되겠죠. 함수의 인수는 n-1에서 1이 될 때까지 점점 줄어들 겁니다.

function factorial(n) {
  return (n != 1) ? n * factorial(n - 1) : 1;
}

alert( factorial(5) ); // 120

재귀의 베이스는 1로 잡았는데, 0이어도 상관은 없습니다. 0일 경우 재귀 단계가 하나 더 늘어난다는 것만 다릅니다.

function factorial(n) {
  return n ? n * factorial(n - 1) : 1;
}

alert( factorial(5) ); // 120
중요도: 5

피보나치 수는 첫째와 둘째 항이 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) { /* 답안은 여기에 작성 */ }

alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757

주의: fib (77)를 호출했을 때 연산 시간이 1초 이상 되면 안 됩니다.

가장 먼저 떠오르는 방법은 재귀입니다.

정의 자체에서 유추할 수 있듯이 피보나치 수열은 재귀를 사용해 구현할 수 있습니다.

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

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // 연산에 너무 많은 시간이 걸립니다!

그런데 이렇게 재귀를 사용해 구현하면 n이 커질 경우 속도가 느려집니다. fib(77)을 호출하면 CPU 리소스를 다 잡아먹어서 잠시 엔진이 멈출 수도 있습니다.

연산 속도가 느려지는 이유는 함수 호출 도중에 수많은 서브 호출이 일어나기 때문입니다. 같은 값들이 여러 번 평가되면서 이런 일이 발생하죠.

fib(5)의 계산 과정을 살펴봅시다.

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

fib(3)fib(5)fib(4)를 계산할 때 모두 필요합니다. 그렇기 때문에 fib(3)은 완전히 다른 두 곳에서 독립적으로 호출되고 평가되죠.

재귀 트리를 직접 살펴봅시다.

그림을 보니 fib(3)은 두 번 평가된다는 것이 좀 더 명확히 보이네요. fib(2)는 세 번이나 평가됩니다. 이렇게 재귀를 사용해 피보나치 수열을 구현하면 n이 증가하는 속도보다 전체 연산 횟수가 더 빨리 증가합니다. 77 자체는 그리 큰 숫자가 아니지만, 피보나치 수열에서 n=77일 경우엔 엄청난 수의 연산이 일어나죠.

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

또 다른 최적화 방법은 재귀가 아닌 반복문을 기반으로 하는 알고리즘을 짜는 것입니다.

n부터 시작해 숫자를 하나씩 줄이며 원하는 값을 구하는 대신 12로 시작하는 반복문으로 fib(3)을 구하고, 이를 기반으로 fib(4)를 구하고, 또 이를 기반으로 fib(5)를 구하는 식으로 알고리즘을 구현할 수 있습니다. 이렇게 구현하면 이전 두 항의 값만 저장하면 되죠.

반복문을 기반으로 하는 알고리즘을 좀 더 자세히 살펴보겠습니다.

시작은 다음과 같습니다.

// a = fib(1), b = fib(2), 처음 두 항은 1이라는 정의에 의해 이렇게 값을 할당하였습니다.
let a = 1, b = 1;

// c = fib(3), 세 번째 항은 첫 번째 항과 두 번째 항의 합입니다.
let c = a + b;

/* fib(1), fib(2), fib(3)을 구했습니다.
a  b  c
1, 1, 2
*/

이제 fib(2)fib(3)을 더해 fib(4)를 구해봅시다.

a에 기존 b를, b에 기존 c를 할당하고, cab의 합이 되도록 합시다.

a = b; // a = fib(2)
b = c; // b = fib(3)
c = a + b; // c = fib(4)

/* 다음과 같은 수열을 얻을 수 있습니다.
   a  b  c
1, 1, 2, 3
*/

같은 과정을 반복해 다음 수를 얻어봅시다.

a = b; // now a = fib(3)
b = c; // now b = fib(4)
c = a + b; // c = fib(5)

/* 다음과 같은 수열을 얻을 수 있습니다.
      a  b  c
1, 1, 2, 3, 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;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

반복문 내 i3부터 시작합니다. 피보나치 수열의 첫 번째 항과 두 번째 항은 a=1, b=1로 하드코딩 했기 때문입니다.

이런 접근 방법은 bottom-up 다이내믹 프로그래밍(dynamic programming, 동적 계획법)이라 부릅니다.

중요도: 5

재귀와 스택에서 설명한 바 있는, 단일 연결 리스트(single-linked list)가 있다고 가정해 봅시다.

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

리스트 내 항목을 차례대로 하나씩 출력해주는 함수 printList(list)를 만들어보세요.

반복문과 재귀를 사용한 답안을 각각 만들어봅시다.

그리고 재귀를 사용한 것과 재귀를 사용하지 않은 것 중 어떤 게 더 좋은 코드인지 생각해봅시다.

반복문을 기반으로 하는 방법

반복문을 사용한 답안은 다음과 같습니다.

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

function printList(list) {
  let tmp = list;

  while (tmp) {
    alert(tmp.value);
    tmp = tmp.next;
  }

}

printList(list);

여기서 주목해야 할 점은 리스트를 임시 변수 tmp에 저장하고 사용했다는 것입니다. 아래처럼 매개변수 list를 그대로 사용해도 되는데 말이죠.

function printList(list) {

  while(list) {
    alert(list.value);
    list = list.next;
  }

}

그런데 매개변수 list를 바로 사용하는 건 그다지 현명한 선택은 아닙니다. 나중에 함수를 확장할 때 list를 가지고 뭔가 해야 하는 경우가 생길 수 있기 때문이죠. 어떤 일 때문인지는 몰라도 while문 앞에서 list가 변경되면 우리가 짠 코드는 제대로 동작하지 않을 겁니다.

좋은 변수명이 무엇인가를 생각해 봤을 때도 리스트를 임시 변수 tmp에 저장하는 게 좋습니다. list에는 리스트 그 자체가 저장되어있는 게 좋죠.

tmp는 리스트를 순회하기 위한 용도로 쓰였기 때문에 tmp라고 명명하는 게 좋습니다. for문의 i처럼 말이죠.

재귀를 기반으로 하는 방법

재귀를 사용해 만든 printList(list)는 아주 간단한 로직을 기반으로 합니다. "리스트를 출력할 때는 현재 요소 list를 출력하고, 같은 방법을 사용해 list.next를 출력한다."라는 로직이죠.

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

function printList(list) {

  alert(list.value); // 현재 요소를 출력합니다.

  if (list.next) {
    printList(list.next); // 같은 방법을 사용해 나머지 요소를 출력합니다.
  }

}

printList(list);

이제 두 방법을 비교해봅시다.

반복문을 사용하면 리소스를 좀 더 효율적으로 사용합니다. 두 방법의 반환 값은 같지만, 반복문을 사용한 방법에선 중첩 함수를 호출하는데 추가적인 리소스를 쓰지 않기 때문입니다.

반면 재귀를 사용한 방법은 코드 길이가 짧고 이해하기 쉽다는 장점이 있습니다.

중요도: 5

위 문제(단일 연결 리스트 출력하기)에 있는 단일 연결 리스트의 항목을 역순으로 출력해주는 함수를 만들어봅시다.

반복문과 재귀를 사용한 답안을 각각 만들어보세요.

재귀를 기반으로 하는 방법

재귀를 사용한 방법은 조금 까다롭습니다.

리스트의 나머지 요소들을 출력한 다음에 현재 요소를 출력해야 하죠.

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

function printReverseList(list) {

  if (list.next) {
    printReverseList(list.next);
  }

  alert(list.value);
}

printReverseList(list);

반복문을 기반으로 하는 방법

리스트를 원래 순서대로 출력하는 방법보다 역시 까다롭습니다.

list의 마지막 값을 바로 구할 수 있는 방법이 없기 때문입니다. 마지막 값을 시작으로 '역행’할 수 없는 상황이죠.

따라서 우리는 원래 순서대로 요소들을 하나씩 거슬러 올라가면서 각 요소를 배열에 저장해 놓고, 마지막 요소에 도달했을 때 배열에 저장된 요소들을 거꾸로 출력하는 방법을 사용할 수 있을 겁니다.

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

function printReverseList(list) {
  let arr = [];
  let tmp = list;

  while (tmp) {
    arr.push(tmp.value);
    tmp = tmp.next;
  }

  for (let i = arr.length - 1; i >= 0; i--) {
    alert( arr[i] );
  }
}

printReverseList(list);

여기서 주목할 점은 재귀를 사용한 방법과 반복문을 사용한 방법이 완전히 동일한 접근 방식을 취했다는 것입니다. 리스트를 앞에서부터 따라가면서 각 요소를 실행 컨텍스트 스택에 저장해 놓았다가 스택 맨 위에서부터 요소를 차례대로 출력하였습니다.

튜토리얼 지도