Chapter1. 재귀의 이해
Chapter2. 재귀의 활용
JSON.strungify/parse
재귀(recursion) 함수
자기 자신을 호출하는 함수
반복적인 작업을 해야하는 문제를 좀 더 간결한 코드로 풀어낼 수 있다.
재귀 사용은 언제?
1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩횟수를 예측하기 어려운 경우
3. 반복문으로 작성된 코드를 더 간결하고 이해하기 쉽게 작성하고 싶을 때
문제: 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수 arrSum
을 작성하세요.
arrSum
함수로 [1,2,3,4,5]
의 합을 구하는 과정을 작게 쪼개보자.
[1,2,3,4,5]
보다 [2,3,4,5]
의 합을 구하는 게 더 작은 문제다. 같은 원리로 [2,3,4,5]
보다 [3,4,5]
의 합을 구하는 게 더 작은 문제.
위의 원리를 토대로 하면 이렇다.
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
함수를 완성한다.
function arrSum (arr) {
// 빈 배열을 받았을 때 0을 리턴하는 조건문
// --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
if (arr.length === 0) {
return 0
}
// 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
// --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
return arr.shift() + arrSum(arr)
}
💡정리
1. arrSum([])
는 조건문에 의해 더이상 자기자신을 호출하지 않고 숫자 0을 리턴하면서 종료됨.
2. 그 결과 중첩되어있던 함수들도 연쇄적으로 숫자를 리턴함
3. 최종적으로 배열의 모든 요소의 합을 리턴하면서 문제 해결
문제를 동일한 방식으로 쪼개기 -> 쪼개는 방식이 recursive case
더 이상 안 쪼개지면 그것이 base case -> 재귀함수의 탈출조건
base case 해결하기 -> 쪼개졌던 문제가 한번에 해결!
단순하게 함수의 입출력값을 정의. 재귀 함수를 통해 도달하고자 하는 목표를 정의하는 데 도움이 됨.
ex) arrSum
은 number
타입을 요소로 갖는 배열을 입력으로 받고, number
타입을 리턴한다.
문제를 어떻게 쪼갤 건가?
1) 문제를 쪼갤 기준을 정하고,
2) 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분한다. = 입력값의 기준. 입력값이나 문제의 순서와 크기 고려할 것.
3) 문제를 더 이상 쪼갤 수 없는 경우(base case)와 그렇지 않은 경우(recursive case)로 나눈다.
arrSum
은 입력값이 빈 배열인 경우 / 그렇지 않은 경우arrSum: [number] => number
arrSum([ ])
← 입력값이 빈 배열인 경우arrSum([요소1, 요소2, ... , 요소n])
← 그렇지 않은 경우1) 가장 해결하기 쉬운 문제부터 해결(재귀의 기초 base case)
남아있는 복잡한 경우를 해결함.
arrSum: [number] => number
arrSum([ ]) === 0
arrSum([요소1, 요소2, ... , 요소n]) === 요소1 + arrSum([요소2, ..., 요소n])
← 그렇지 않은 경우 : 해결!function recursive(input1, input2, ...) {
// base case : 문제를 더 이상 쪼갤 수 없는 경우
if (문제를 더 이상 쪼갤 수 없을 경우) {
return 단순한 문제의 해답;
}
// ex) if(arr.length === 0) return 0
// recursive case : 그렇지 않은 경우
return 더 작은 문제로 새롭게 정의된 문제
// ex) return 요소1 + arrSum([요소2, ... , 요소n]);
}
ex) 5! 계산
function fac(n) {
if(n ===1) { // 1!은 더이상 나눌 수 없으므로 n=1일 경우 1을 리턴
return 1;
}
return n * fac(n-1); // 1이 아닐 경우엔 하나를 뺀 수를 팩토리얼 계산을 해준다. 5 * 4! 식으로 계산됨.
}
JSON(JavaScript Object Notation)
데이터 교환을 위해 만들어진 객체 형태의 포맷
message.toString()
나 형변환(String(message)
)을 시도하면, [object Object]
라는 결과를 리턴한다. 이러한 문제를 해결하는 방법은 ? ⬇️
JSON.stringify
: 객체 → JSON 직렬화(serialize)let transferableMessage = JSON.stringify(message)
console.log(transferableMessage)
// `{"sender":"김코딩","receiver":"박해커","message":"해커야 오늘 저녁 같이 먹을래?","createdAt":"2021-01-12 10:10:10"}`
console.log(typeof(transferableMessage))
// `string`
// [코드] message 객체를 JSON으로 변환하는 메서드 JSON.stringify
JSON.parse
: JSON → 객체 역직렬화(deserialize)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에 메서드 JSON.parse를 적용하면 다시 객체의 형태로 변환할 수 있습니다.