자료구조 | 재귀

SURI·2021년 12월 18일

1. 개념

문제를 동일한 구조의 더 작은 문제로 나누고, 이 작은 문제를 해결함으로써 전체 문제를 해결하는 방법을 재귀(recursion)라고 한다.

1.1 문제를 쪼개어 생각하기

자연수로 이루어진 배열을 입력받고 리스트의 합을 리턴하는 함수를 작성해보려고 한다. 나는 기존에 배웠던 반복문과 reduce 메소드를 떠올렸다. 여기에 재귀를 적용해본다면?

arrSum([]) = 0; // what's the simplest input? 
arrSum([2]) = 2 + arrSum([]) = 2;
arrSum([6, 2]) = 6 + arrSum([2]) = 6 + 2 = 8;
arrSum([8, 6, 2]) = 8 + arrSum([6, 2]) = 8 + 8 = 16;
//...

arrSum(arr) = arr[0] + arrSum(arr.slice(1));

함수 arrSum은 실행과정 중에 자기 자신을 호출한다. 이러한 호출방식을 재귀호출이라고 한다.
- 기존의 문제에서 출발하여 더 작은 경우를 생각한다.
- 문제가 더는 쪼갤 수 없을 때까지 작은 경우를 생각한다.
- 문제가 간단해져서 바로 풀 수 있어지면, 앞서 생성한 문제를 해결해간다.

1.2 재귀는 언제 사용할까?

주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우
- 모든 재귀 함수는 반복문으로 표현할 수 있다. 하지만 재귀를 적용할 수 있는 대부분의 경우, 재귀로 작성한 코드가 더 간결하고 이해하기 쉽다.
- 재귀는 알고리즘 문제의 많은 부분을 차지한다. e.g. 코딩 테스트, 면접

1.3 재귀적 사고 연습 : base case와 recursive case

재귀 함수의 입력값과 출력값 정의하기
- 도달하고자 하는 목표를 정의하는 데 도움이 된다.
- 문제를 가장 추상적으로, 단순하게 정의한다.
- arrSum: [number] => number
문제를 쪼개고 경우의 수를 나누기
- 문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인한다. 일반적으로 입력값으로 기준을 정한다. (문제 상황의 순서와 크기?)
- 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우의 수로 나눈다.
단순한 문제 해결하기
- base case : 가장 해결하기 쉬운 재귀의 기초부터 해결한다. 이는 재귀 호출이 멈추는 조건을 구성한다. (재귀의 탈출 조건)
남은 복잡한 문제 해결하기
- arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ..., en])
- 배열을 head와 나머지 부분(tail)으로 구분한다.
코드로 구현하기

function arrSum(arr) {
  // base case
  if (arr.length === 0) {
    return 0;
  }
  
  // recursive case
  return arr[0] + arrSum(arr.slice(1));
  // head + arrSum(tail) 배열의 첫 요소와 첫 요소가 제거된 나머지 요소
}

  ===재귀 템플릿===

 function recursive(input1, input2, ...) {
    // base case
    if (문제를 더 이상 쪼갤 수 없을 경우) {
      return 단순한 문제의 해답;
    }
    
    // recursive case
    return 더 작은 문제로 새롭게 정의된 문제
  }

팩토리얼

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

1.4 재귀 함수의 활용

Tree 구조에 재귀 함수를 사용한다. e.g. JS 객체, JSON
깊이를 알 수 없는 Tree 구조에 재귀 함수를 활용하여 모두 순회(traverse)할 수 있다.
실생활에 사용되는 유용한 tree 구조 : 파일 디렉토리

JSON

JSON은 JavaScript Object Notation의 줄임말로, 서로 다른 프로그램에서 데이터 교환을 위해 만들어진 객체 형태의 포맷이다.

JSON이 왜 필요할까?

메세지 객체를 전달하고 싶다면, 수/발신자가 같은 프로그램을 사용하거나 범용적인 문자열로 처리되어야 한다. 하지만 문제가 있다. 사용자가 서로 다른 프로그램을 사용한다면? 혹은 문자열 처리를 하기 위해 toString()이나 형변환을 시도하면 객체의 내용이 포함되지 않는다.

그래서 JSON을 사용한다.

JSON.stringify(message) : 직렬화(serialize), 타입은 문자열
JSON.parse(packet) : 역직렬화(deserialize), 타입은 객체

=> 서로 정반대의 작업을 수행한다.

JSON과 자바스크립트 객체의 다른 점

키에 반드시 큰따옴표를 붙여야 한다.
문자열 값은 반드시 큰따옴표로 감싸야 한다.
키와 값 사이, 키-값 쌍 사이에 공백이 있어서는 안 된다.

let packet = `{"sender":"수리","receiver":"골똥","message":"러닝하자!","createdAt":"2021-12-12 10:10:10"}`

console.log(typeof(packet)) 
// 'string'

let obj = JSON.parse(packet)
console.log(obj)
/*
 * {
 * sender: "수리",
 * receiver: "골똥",
 * message: "러닝하자!",
 * createdAt: "2021-12-12 10:10:10"
 * }
 */
 console.log(typeof(obj))
 // `object`