[Week 4] 재귀함수

시작하기 앞서

어떤 문제가 있다고 가정할 때 이 문제를 동일한 구조의 더 작은 문제로 나눌 수 있고, 이 작은 문제를 해결함으로써 전체 문제를 해결하는 방법을 재귀(recursion)라고 한다. 재귀를 사용한 코드는 대부분의 경우 더욱 간결하고, 이해하기 쉽다. 그 밖에도 재귀는 알고리즘 문제의 많은 부분을 차지한다.

재귀

• 재귀적으로 사고하는 법
  • 잘게 쪼개어 사고하는 법
  • 재귀적 사고
  • 함수 자신의 재귀적 호출
  • 탈출 조건
• 재귀 함수의 활용 (트리 구조)
  • 트리 구조에 재귀 함수를 활용
  • JSON 구조에 재귀 함수를 활용
  • DOM 구조에 재귀 함수를 활용

Achievement Goals

Lesson - 재귀 함수

• 재귀의 의미에 대해서 이해하고, 자바스크립트에서 재귀 호출을 할 수 있다.
• 재귀를 언제 사용해야 하는지 알고 있다.
• 재귀적 사고 연습을 통해 재귀 함수를 base case와 recursive case로 나눠서 작성할 수 있다.
• 자료 구조 중 Tree 구조에 재귀 함수를 사용하는 이유를 이해할 수 있다.
  • 실생활에 사용되는 유용한 Tree 구조를 알고 있다.
  • 깊이를 알 수 없는 Tree 구조에 재귀 함수를 활용하여 모두 순회(traverse)할 수 있다.

 

다음과 같은 문제를 푼다고 가정해보자.

문제. 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수 `arrSum` 을 작성하세요.

여기서 주어진 배열은 [10, 3, 6, 2]라고 가정한다. 

 

문제를 쪼개어 생각한다면

1. 기존의 문제에서 출발하여 더 작은 경우를 생각한다.

arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]);

2. 같은 방식으로, 문제가 더는 작아지지 않을 때까지 더 작은 경우를 생각한다.

arrSum([3, 6, 2]) = 3 + arrSum([6, 2]);
arrSum([6, 2]) = 6 + arrSum([2]);
arrSum([2]) = 2 + arrSum([]);

문제가 간단해져서 바로 풀 수 있게 되는 순간부터 앞서 생성한 문제를 차근차근 해결한다.

arrSum([]) = 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용한다.
arrSum([2]) = 2 + arrSum([]) = 2;
arrSum([6, 2]) = 6 + arrSum([2]) = 6 + 2 = 8;
arrSum([3, 6, 2]) = 3 + arrSum([6, 2]) = 3 + 8 = 11;
arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]) = 10 + 11 = 21;

다음과 같이 보다 엄밀하게(formally) 정의할 수 있다.

/*
 * 1. arr이 빈 배열인 경우 = 0
 * 2. 그 외의 경우 = arr[0] + arrSum(arr2)
 *   (arr2는 arr의 첫 요소를 제외한 나머지 배열)
 */
arrSum(arr);

만약 함수 arrSum을 JS 코드로 구현할 경우 함수 arrSum은 실행과정 중에 자기 자신을 호출한다. 이러한 호출 방식을 재귀 호출이라고 한다.

 

재귀는 다음과 같은 상황에서 매우 적합하다.

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

 

Guide : 재귀적으로 사고하기

1. 재귀 함수의 입력값과 출력값 정의하기

재귀적으로 사고하는 데에 가장 먼저 해야 할 일은 문제를 가장 추상적으로 또는, 가장 단순하게 정의하는 것이다.

함수 arrSum의 경우 number 타입을 요소로 갖는 배열을 입력으로 받고, number타입을 리턴한다. 이를 좀 더 간단하게 표현하면 다음과 같다.

• arrSum: [number] => number

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

문제를 쪼갤 때 중요한 관점은 입력값이나 문제의 순서와 크기이다.

• 함수 arrSum 의 경우 입력값인 리스트(배열)의 크기에 따라, 더 작은 문제로 나눌 수 있다. 그리고 arrSum([1, 2, 3, 4]) 를 구하는 방법과 arrSum([2, 3, 4]) 을 구하는 방법은 동일하므로, 이 구분은 적절하다고 판단할 수 있다.

이제 문제에서 주어진 입력값에 따라, 경우의 수를 나눈다. 일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눈다.

• 함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있다. 각각의 경우는 다른 방식으로 처리해야 한다.
• arrSum: [number] => number
  arrSum([ ])
  arrSum([e1, e2, ... , en])

3. 단순한 문제 해결하기

문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결한다. 이를 재귀의 기초(base case)이라고 부른다. 재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.

• 함수 arrSum 을 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때 arrSum([]) 의 리턴값은 0이다.
• arrSum: [number] => number
  arrSum([ ]) = 0
  arrSum([e1, e2, ... , en])

4. 복잡한 문제 해결하기

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

• 길이가 1 이상인 배열이 함수 arrSum 에 입력된 경우, 맨 앞의 요소에 대한 결과를 따로 구하고(배열의 맨 앞의 요소이기 때문에 head라고 명명), 나머지 요소를 새로운 입력값으로 갖는 문제로 구분하고, 이를 해결하여 얻은 결과를 head에 더한다.
• arrSum: [number] => number
  arrSum([ ]) = 0
  arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ..., en])
• 배열을 head와 나머지 부분(tail)으로 구분하는 방법만 안다면, 함수 arrSum을 재귀적으로 구현할 수 있다.

5. 코드 구현하기

function arrSum(arr) {
  //Base Case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0;
  }
  /*
  * Recursive Case : 그렇지 않은 경우
  * 문제를 더 이상 쪼갤 수 없는 경우
  * head: 배열의 첫 요소
  * tail: 배열의 첫 요소만 제거된 배열
  */
  return head + arrSum(tail);
}

아래는 일반적인 재귀 함수의 템플릿이다.

function recursive(input1, input2, ...) {
  // Base Case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

 

코플릿 업로드

 

## StringifyJSON

Achievement Goals

• JSON 구조가 재귀 함수를 사용할 수 있는 Tree 구조임을 이해할 수 있다. (stringifyJSON)
  • JSON.stringify 와 JSON.parse 가 serialize, deserialize라는 것을 이해할 수 있다.
  • JSON.stringify 와 JSON.parse 를 사용하여 자바스크립트 값과 JSON을 넘나들 수 있다.
  • JSON에 재귀 호출을 사용할 때, 어디에 사용해야 할지 이해할 수 있다.

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

 

객체는 타입 변환을 이용해 String으로 변환할 경우 객체 내용을 포함하지 않는다.

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

이를 위한 메소드는 다음과 같다.

 

• JSON.stringify : Object type을 JSON으로 변환합니다.
• JSON.parse : JSON을 Object type으로 변환합니다.
• 자세한 내용은 JSON 공식 문서를 참고하세요

let transferableMessage = JSON.stringify(message)
console.log(transferableMessage)  // `{"sender":"김코딩","receiver":"박해커","message":"해커야 오늘 저녁 같이 먹을래?","createdAt":"2021-01-12 10:10:10"}`
console.log(typeof(transferableMessage)) // `string`

 

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

 

JSON으로 변환된 객체의 타입은 문자열이다. 발신자는 객체를 직렬화한 문자열을 누군가에게 객체의 내용을 보낼 수 있다. 그렇다면 수신자는 이 문자열 메시지를 어떻게 다시 객체의 형태로 만들 수 있을까? JSON.stringify와 정반대의 작업을 수행을 하는 메소드 JSON.parse 를 사용할 수 있다.

 

let packet = `{"sender":"김코딩","receiver":"박해커","message":"해커야 오늘 저녁 같이 먹을래?","createdAt":"2021-01-12 10:10:10"}`

let obj = JSON.parse(packet)
console.log(obj)
/*
 * {
 * sender: "김코딩",
 * receiver: "박해커",
 * message: "해커야 오늘 저녁 같이 먹을래?",
 * createdAt: "2021-01-12 10:10:10"
 * }
 */
 console.log(typeof(obj))
 // `object`

 

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

 

직렬화와 역직렬화 모식도

JSON의 기본 규칙

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

또한 JSON은 키와 값 사이, 그리고 키-값 쌍 사이에는 공백이 있어서는 안된다.

 

+

• 재귀 함수와 메모리 사용량 간의 관계 (javascript recursion memory leak)
• 꼬리 재귀 (tail recursion in js)
• 하노이의 탑 재귀 (js tower of hanoi in recursion)
• 조합 재귀 함수 (js combination in recursion)

해당 내용을 찾아서 더 공부해보자.