[TIL] [자료구조/알고리즘] 재귀

재귀

재귀란 원래의 자리로 되돌아가거나 되돌아온다는 의미이다.

아래 예시를 보면 recursion 함수는 자기 자신을 무한히 반복한다.

function recursion () {
  console.log("This is")
  console.log("recursion!")
  recursion()
}

// This is
// recursion
// This is
// recursion
// This is
// recursion
// ... 반복

recursion 은 재귀함수로 자기 자신을 무한히 반복한다. 단순히 무한 반복한다면 재귀의 개념을 왜 사용할까?
보통의 재귀함수는 위 예시와 같이 무한하게 작동하지 않는다.
꼭, 탈출 조건이 되는 base case와 반복하여 문제를 해결할 recursion case를 구분해야 한다.

재귀함수는 다음과 같은 상황에서 사용할 수 있다.

• 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
• 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우
• 반복문으로 작성된 코드를 더욱 간결하고 이해하기 쉽게 작성하고 싶은 경우

해결해야 할 문제가 잘게 쪼개어 반복해 해결할 수 있을 경우 재귀를 사용할 수 있다.

---

재귀적으로 잘 작성하기 위한 가이드가 있다.

피보나치 수열의 n번째 값을 구하기 위하기 위해 재귀함수를 작성한다고 가정한다.
피보나치 수열의 요소는 앞 두 번째 요소들의 합이 그 수가 된다.

1. 입출력 값을 정의한다.

"입력을 통해 어떠한 출력을 정의할 것인가"는 재귀함수를 통해 해결하려는 목표를 정의하는데 도움을 준다.

fibonacci: number => number

n번째 라는 입력을 number로 들어오면 n번째 값을 number로 출력한다.

2. 문제를 쪼개고 경우의 수를 나누기

문제를 어떻게 쪼갤 것인지 고민한다. 일반적으로 입력 값을 기준으로 한다. 문제를 쪼갤 기준을 정하고 문제가 더 큰 경우와 작은 경우로 구분할 수 있는지 확인한다.

fibonacci(5)와 fibonacci(6) 을 구하는 방법은 똑같을 것이다.
fibonacci(5)는 fibonacci(4)와 fibonacci(3)을 더한 값을 출력할 것이다.
fibonacci(6) 역시 fibonacci(5)와 fibonacci(4)을 더한 값을 출력할 것이다.

이렇게 문제를 어떻게 쪼개야 할지 정의했다. 이제 입력 값에 따라 경우의 수를 나눠야 한다.
fibonacci(0) 또는 fibonacci(1)은 앞에 두 요소가 없다.
그렇기 때문에 입력을 그대로 출력해주면 될 것이다.

fibonacci()는 입력이 0 또는 1일 경우와 그 이상일 경우로 구분할 수 있다.

fibonacci: number => number
fibonacci(0) 또는 fibonacci(1)
fibonacci(n > 1)

3. 단순한 문제 해결하기

문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결한다. 이를 재귀의 기초(base case)라고 한다. 이는 재귀함수의 탈출 조건이 될 것이다.

탈출 조건이 없는 경우 재귀 함수는 끝없이 자기 자신을 호출한다. 최대한 쪼갤 만큼 쪼갠 후 출력해 온전히 원하는 출력을 얻도록 2번의 설정을 잘 해야한다.

fibonacci()을 더이상 쪼갤 수 없는 경우는 입력값이 0 또는 1일 경우이고, 이때 fibonacci()의 리턴값은 0이다.

fibonacci: number => number
fibonacci(0) 또는 fibonacci(1) base case, return 0
fibonacci(n > 1)

4. 복잡한 문제 해결하기

이제 남아있는 복잡한 경우를 해결한다.

길이가 2 이상인 수가 입력된 경우, 수와 앞 두 요소의 수를 더할 수 있도록 한다.

fibonacci: number => number
fibonacci(0) 또는 fibonacci(1) base case, return 0 or 1
fibonacci(n > 1) recursion case, return fibonacci(n - 1) + fibonacci(n - 2)

함수 작성하기

위 가이드를 통해 재귀함수를 작성하면 다음과 같다.

function fibonacci(num) {
  // base case
  if (num <= 1) return num

  // recursive case
  return fibonacci(num-1) + fibonacci(num-2)
}

---

JSON

JSON(JavaScript Object Notation) 데이터 교환을 위해 만들어진 객체 형태의 포맷이다.

메시지 객체가 전송 가능하려면, 메시지를 보내는 발신자와 메시지를 받는 수신자가 같은 프로그램을 사용하거나, 문자열처럼 범용적으로 읽을 수 있는 형태여야 한다.

이 문제를 해결하는 방법은 객체를 JSON의 형태로 변환하거나 JSON을 객체의 형태로 변환한다.

JSON.stringify : 객체를 JSON으로 변환합니다.
JSON.parse : JSON을 객체로 변환합니다.

stringify하는 이 과정을 직렬화(serialize라고 한다.

JSON으로 변환된 객체의 타입은 문자열입니다. 발신자는 객체를 직렬화한 문자열을 누군가에게 객체의 내용을 보낼 수 있다. 그렇다면 수신자는 JSON.stringify와 정반대의 작업을 수행을 하는 메서드 JSON.parse 를 사용해 수신한 JSON을 객체로 변환한다.

JSON.parse를 적용하는 이 과정을 역직렬화(deserialize)라고 한다.

JSON은 서로 다른 프로그램 사이에서 데이터를 교환하기 위한 포맷이다. 그리고 JSON 포맷은 자바스크립트를 포함한 많은 언어에서 범용적으로 사용하는 유명한 포맷이다.

규칙

JSON은 얼핏 보기에 자바스크립트의 객체와 별반 다를 바가 없어 보이지만, 자바스크립트의 객체와는 미묘하게 다른 규칙이 있다.

	자바스크립트 객체	JSON
키	작은따옴표도 사용 가능 { "key" : 'property' }	반드시 쌍따옴표를 붙여야 함 '{"key":"property"}'
문자열 값	작은따옴표도 사용 가능 { "key" : 'property' }	반드시 큰따옴표로 감싸야 함 '{"key":"property"}'
키와 값 사이 공백	사용 가능 {"key" : 'property'}	사용 불가능 '{"key":"property"}'
키-값 쌍 사이 공백 사용	사용 가능{ "key":'property', num:1 }	사용 불가능 '{"key":"property","num":1}'