[Javascript] Recursive function

Suyeon·2020년 9월 2일

Javascript

목록 보기

13/31

Recursive function

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

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

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

// 예시: pow(x,n) 함수 구현하기
pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16

// (1) for loop 사용
function pow(x, n) {
  let result = 1;

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

  return result;
}

alert( pow(2, 3) ); // 8

// (2) 재귀적인 사고
function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

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

// 재귀 알고리즘 사용
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

Recursive data structure (재귀적 자료구조)

재귀적으로 정의된 자료구조인 재귀적 자료 구조는 자기 자신의 일부를 복제하는 형태의 자료 구조입니다.
HTML과 XML / Linked List (연결리스트) / 위에서 살펴본 회사구조 역시 재귀적 자료구조 형태임

Linked List

객체를 정렬하여 어딘가에 저장하고 싶다고 가정해 봅시다.
가장 먼저 떠오르는 자료 구조는 아마 배열일 겁니다.

let arr = [obj1, obj2, obj3];

하지만 이 경우, 배열 앞쪽에서 삭제와 삽입을 할 경우 속도가 느려집니다.
(unShift(), shift()를 사용할 경우 )

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

연결 리스트의 요소 는 객체와 아래 프로퍼티들을 조합해 정의할 수 있습니다.

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

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

// (2) 위와 동일
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;

예제

// 전체 리스트를 부분으로 나누기
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 };

// 리스트에 new item 추가
list = { value: "new item", next: list };

// 리스트에서 삭제
list.next = list.next.next;

Execution context and stack

실행 중인 함수의 실행 절차에 대한 정보는 해당 함수의 실행 컨텍스트(execution context) 에 저장됩니다. 실행 컨텍스트는 함수 실행에 대한 세부 정보를 담고 있는 내부 데이터 구조입니다. 함수 호출 일 회당 정확히 하나의 실행 컨텍스트가 생성됩니다.

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

현재 함수의 실행 일시 중지.
중지된 함수와 연관된 실행 컨텍스트는 실행 컨텍스트 스택(execution context stack) 이라는 특별한 자료 구조에 저장.
중첩 호출 실행.
중첩 호출 실행이 끝난 이후 실행 컨텍스트 스택에서 일시 중단한 함수의 실행 컨텍스트를 꺼내오고, 중단한 함수를 다시 실행.
함수가 종료되면 해당 실행 컨텍스트는 메모리에서 삭제.

Memory

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

반복문 기반 알고리즘(for loop)을 사용하면 메모리가 절약됩니다. 반복을 사용해 만든 함수는 컨텍스트를 하나만 사용합니다. 실행 컨텍스트가 하나이기 때문에 n에 의존적이지 않고, 필요한 메모리가 적습니다. 사용 메모리 공간도 고정됩니다. 재귀를 이용해 작성한 코드는 반복문을 사용한 코드로 다시 작성할 수 있습니다. (메모리 절약)

재귀(recurstion)를 사용하면 코드가 짧아지고 코드 이해도가 높아지며 유지보수에도 이점이 있습니다. 모든 곳에서 메모리 최적화를 신경 써서 코드를 작성해야 하는 것은 아닙니다. 우리가 필요한 것은 좋은 코드입니다. 이런 이유 때문에 재귀를 사용합니다.

Suyeon

Hello World.

이전 포스트

[Javascript] Object_Optional chaining

다음 포스트