Section 7. 재귀(Recursion)

HanSungUk·2022년 6월 3일

TIL 알고리즘

알고리즘

목록 보기

1/5

Section 7. 재귀(Recursion)

현재 유데미와 코드스테이츠 강의를 통해 알고리즘을 학습하고 있습니다.
본 포스트는 해당 강의에 대한 내용 정리를 목적으로 합니다.

학습목표

재귀의 의미에 대해서 이해한다.
JavaScript에서 재귀 호출을 할 수 있다.
재귀를 언제 사용해야 하는지 이해한다.
JSON 구조가 재귀 함수를 사용할 수 있는 트리 구조임을 이해할 수 있다.
- JSON.stringify와 JSON.parse가 serialize, deserialize라는 것을 이해할 수 있다.
- JSON.stringify와 JSON.parse를 사용하여 자바스크립트 값과 JSON을 넘나들 수 있다.
- JSON에 재귀 호출을 사용할 때, 어디에 사용해야 할지 이해할 수 있다.

1. 재귀 함수

함수가 자기 자신을 호출하는 것을 재귀 호출(recursive call)이라 합니다. 재귀 함수(recursive function)는 자기 자신을 호출하는 행위, 즉 재귀 호출을 수행하는 함수를 말합니다.

function factorial(n){
  // 탈출 조건: n이 1이하일 때 재귀 호출을 멈춘다.
	if (n <= 1) return 1;
  // 재귀 호출
 	return n * factorial(n-1);
}

재귀 함수는 자신을 무한 재귀 호출합니다. 따라서 재귀 함수 내에는 재귀 호출을 멈출 수 있는 탈출 조건을 반드시 만들어야 합니다.
탈출 조건이 없으면 함수가 무한 호출되어 스택 오버 플로(stack overflow) 에러가 발생합니다.

재귀로 문제 해결하기
문제: 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수 'arrSum'을 작성하세요

문제를 작게 쪼개기

arrSum([1,2,3,4,5]) === 1 + arrSum([2,3,4,5])
arrSum([2,3,4,5]) === 2 + arrSum([3,4,5])
...

문제를 가장 작은 단위로 쪼개기

...
arrSum([3,4,5]) === 3 + arrSum([4,5])
arrSum([4,5]) === 4 + arrSum([5])
arrSum([5]) === 5 + arrSum([])

문제 해결하기
문제가 더 쪼개지지 않게 되면, 가장 작은 단위의 문제를 해결합니다. 문제를 쪼갤 때 같은 방식으로 쪼갰기 때문에, 가장 작은 단위의 문제를 해결한 방식으로 문제 전체를 해결할 수 있게 되었습니다.

2번에서 도달한 가장 작은 문제는 arrSum([])이었습니다. 빈 배열의 합은 0이므로, 0을 리턴해주면 됩니다. 이렇게 가장 작은 문제를 해결하는 순간, 아래 코드처럼 쪼개졌던 문제가 거꾸로 거슬러 올라가면서 합쳐지게 됩니다.

arrSum([]) === 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용합니다.
arrSum([5]) === 5 + arrSum([]) === 5 + 0 === 5;
arrSum([4, 5]) === 4 + arrSum([5]) === 4 + 5 === 9;
arrSum([3, 4, 5]) === 3 + arrSum([4, 5]) === 3 + 9 === 12;
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5]) === 2 + 12 === 14;
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) === 1 + 14 === 15;

arrSum함수의 리턴값이 나오면서 연쇄적으로 문제가 해결되고, 최종적으로는 문제 전체가 해결되는 것을 볼 수 있습니다.

위 단계를 반영해서 arrSum 함수를 완성해보면 다음과 같습니다.

function arrSum(arr){
	// 빈 배열을 받았을 때 0을 리턴하는 조건문
  	// ==> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  if(arr.length === 0){
  	return 0
  }
  
  // 배열의 첫 요소 +  나머지 요소가 담긴 배열을 받는 arrSum 함수
  // ==> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개 나가는 코드
  	return arr.shift() + arrSum(arr)
}

arrSum([])는 조건문에 의해 더이상 자기 자신을 호출하지 않고, 숫자 0을 리턴하면서 종료됩니다.

재귀를 사용하는 상황
- 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
- 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우
- 반복문으로 작성된 코드를 더욱 간결하고 이해하기 쉽게 작성하고 싶은 경우

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
            for (let l = 0; l < n; l++) {
                for (let m = 0; m < n; m++) {
                    for (let n = 0; n < n; n++) {
                        for (let o = 0; o < n; o++) {
                            for (let p = 0; p < n; p++) {
                                // do something
                                someFunc(i, j, k, l, m, n, o, p);
                           }
                        }
                    }
                }
            }
        }
    }
 }

모든 재귀 함수는 반복문(while또는 for문)으로 표현할 수 있습니다. 그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 간결하고 이해하기 쉽습니다.

2. 재귀적으로 사고하기

재귀는 자연스러워질 때까지 연습해야 합니다.
1. 재귀 함수의 입력값과 출력값 정의하기
재귀적으로 사고하는 데에 가장 먼저 해야할 일은 가장 단순하게 정의하는 것입니다.
함수의 입출력값을 정의하는 것은 그 첫 출발점이자 재귀 함수를 통해 풀고자하는 문제를 정의하는 데 도움이 됩니다.

함수 arrSum의 경우 number타입을 요소로 갖는 배열을 입력으로 받고, number타입을 리턴합니다.

arrSum : [number] => number <-- 입출력값 정의

문제를 쪼개고 경우의 수를 나누기
다음으로는 주어진 문제를 어떻게 쪼갤 것인지 고민합니다.
일반적으로 입력값을 이 기준으로 정합니다. 이때 중요한 관점은 입력값이나 문제의 순서와 크기 입니다. 주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는 데 도움이 됩니다.
구분된 문제를 푸는 방식이 순서나 크기와 관계없이 모두 같다면 문제를 제대로 구분한 것입니다.

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

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

함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있습니다.
- arrSum: [number]=>number
- arrSum([ ]) <- 입력값이 빈 배열인 경우
- arrSum([요소1, 요소2, 요소3, ..., 요소n])<- 그렇지 않은 경우

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

함수 arrSum을 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열인 경우이고, 이때 arrSum()의 리턴값은 0입니다.
- arrSum: [number]=>number
- arrSum([ ]) === 0 <- 입력값이 빈 배열인 경우 : 해결!
- arrSum([요소1, 요소2, 요소3, ..., 요소n])<- 그렇지 않은 경우

복잡한 문제 해결하기
남아있는 복잡한 경우를 해결합니다.

길이가 1이상인 배열이 함수 arrSum에 입력된 경우, 입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 쪼개고, 둘을 더합니다.
- arrSum: [number]=>number
- arrSum([ ]) === 0 <- 입력값이 빈 배열인 경우 : 해결!
- arrSum([요소1, 요소2, 요소3, ..., 요소n]) === 요소1 + arrSum(요소2, ... , 요소 n)<- 그렇지 않은 경우: 해결!

코드 구현하기

function arrSum(arr) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0;
  }

  // recursive case : 그렇지 않은 경우
  return 요소1 + arrSum([요소2, ... , 요소n]);
}

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

3. 예제

Math.pow()메서드의 기능과 유사한 거듭제곱 함수 만들기

// power(2, 0) // 1
// power(2, 2) // 4
// power(2, 4) // 16

function power(base, exponent){
	if(exponent === 0) return 1
  	return base * power(base, exponent-1)
}

factorial 함수 만들기

// factorial(1) // 1
// factorial(2) // 2
// factorial(4) // 24
// factorial(7) // 5040

function factorial(x){
	if(x < 0) return 0
  	if(x <= 1) return 1
  
  return x * factorial(x-1)
}

productOfArray 함수 만들기

// productOfArray([1, 2, 3]) // 6
// productOfArray([1, 2, 3, 10]) // 60

function productOfArray(arr){
	if(arr.length === 0){
    	return 1
    }
  return arr[0]*productOfArray(arr.slice(1))
}

4. JSON.stringify

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

만일 네트워크를 통해 어떤 객체 내용을 다른 프로그램에 전송해야한다면 어떻게 해야될까요?

전송 가능한 조건(transferable condition)

수신자(receiver)과 발신자(sender)가 같은 프로그램을 사용한다.

또는 문자열처럼 범용적으로 읽을 수 있어야 한다.

객체를 전송 가능한 조건으로 만들기 위한 방법은 객체를 JSON의 형태로 변환하거나 JSON을 객체의 형태로 변환하는 방법입니다.

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

const message = {
	sender: "한프로",
  	receiver: "김프로"
	message: "프로젝트 하나 하실까요?"
  	createdAt: "2022-06-24 10:10:10"
}

let transferableMessage = JSON.stringify(message)

console.log(transferableMessage)
/* `{
	"sender": "한프로",
  	"receiver": "김프로"
	"message": "프로젝트 하나 하실까요?"
  	"createdAt": "2022-06-24 10:10:10"
}`
*/

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

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

JSON으로 변환된 객체의 타입은 문자열 입니다. 수신자가 이 문자열 메시지를 다시 객체의 형태로 만드는 방법은 JSON.parse 메서드를 사용합니다.

let packet = `{
	"sender": "한프로",
  	"receiver": "김프로"
	"message": "프로젝트 하나 하실까요?"
  	"createdAt": "2022-06-24 10:10:10"
}`
let obj = JSON.parse(packet)

console.log(obj)
/* {
	sender: "한프로",
  	receiver: "김프로"
	message: "프로젝트 하나 하실까요?"
  	createdAt: "2022-06-24 10:10:10"
}*/

console.log(typeof(obj))
// 'object'

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

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

JSON의 기본 규칙

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

HanSungUk

다음 포스트

Section 7. 재귀(Recursion)

알고리즘

Section 7. 재귀(Recursion)

현재 유데미와 코드스테이츠 강의를 통해 알고리즘을 학습하고 있습니다.
본 포스트는 해당 강의에 대한 내용 정리를 목적으로 합니다.

학습목표

1. 재귀 함수

2. 재귀적으로 사고하기

3. 예제

4. JSON.stringify

JSON의 기본 규칙

Section 11. 버블 정렬

0개의 댓글

Section 7. 재귀(Recursion)

알고리즘

Section 7. 재귀(Recursion)

현재 유데미와 코드스테이츠 강의를 통해 알고리즘을 학습하고 있습니다.본 포스트는 해당 강의에 대한 내용 정리를 목적으로 합니다.

학습목표

1. 재귀 함수

2. 재귀적으로 사고하기

3. 예제

4. JSON.stringify

JSON의 기본 규칙

Section 11. 버블 정렬

0개의 댓글

현재 유데미와 코드스테이츠 강의를 통해 알고리즘을 학습하고 있습니다.
본 포스트는 해당 강의에 대한 내용 정리를 목적으로 합니다.