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

play·2022년 6월 25일
0

Chapter1. 재귀의 이해

Chapter2. 재귀의 활용

JSON.strungify/parse

Chapter1. 재귀의 이해

재귀(recursion) 함수

자기 자신을 호출하는 함수
반복적인 작업을 해야하는 문제를 좀 더 간결한 코드로 풀어낼 수 있다.

재귀 사용은 언제?
1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩횟수를 예측하기 어려운 경우
3. 반복문으로 작성된 코드를 더 간결하고 이해하기 쉽게 작성하고 싶을 때

재귀로 문제 해결

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

1. 문제를 작게 쪼갠다

arrSum 함수로 [1,2,3,4,5]의 합을 구하는 과정을 작게 쪼개보자.
[1,2,3,4,5]보다 [2,3,4,5]의 합을 구하는 게 더 작은 문제다. 같은 원리로 [2,3,4,5] 보다 [3,4,5]의 합을 구하는 게 더 작은 문제.

2. 문제가 더 작아지지 않을 때까지 쪼갠다

위의 원리를 토대로 하면 이렇다.

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([])

3. 가장 작은 단위의 문제를 풀어 전체 문제를 해결한다

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 해결하기 -> 쪼개졌던 문제가 한번에 해결!


Chapter2. 재귀의 활용

재귀적으로 사고하기

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

단순하게 함수의 입출력값을 정의. 재귀 함수를 통해 도달하고자 하는 목표를 정의하는 데 도움이 됨.

ex) arrSumnumber 타입을 요소로 갖는 배열을 입력으로 받고, number 타입을 리턴한다.

  • arrSum: [number] => number ← 입출력값 정의

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

문제를 어떻게 쪼갤 건가?
1) 문제를 쪼갤 기준을 정하고,
2) 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분한다. = 입력값의 기준. 입력값이나 문제의 순서와 크기 고려할 것.
3) 문제를 더 이상 쪼갤 수 없는 경우(base case)와 그렇지 않은 경우(recursive case)로 나눈다.

  • 함수 arrSum은 입력값이 빈 배열인 경우 / 그렇지 않은 경우
  • 각각의 경우는 다른 방식으로 처리한다.
    • arrSum: [number] => number
      arrSum([ ]) ← 입력값이 빈 배열인 경우
      arrSum([요소1, 요소2, ... , 요소n]) ← 그렇지 않은 경우

3. 단순한 문제 해결하기

1) 가장 해결하기 쉬운 문제부터 해결(재귀의 기초 base case)

  • 재귀의 기초는 나중에 재귀함수를 구현할 때, 재귀의 탈출조건(재귀 호출이 멈추는 조건)을 구성한다.

4. 복잡한 문제 해결하기

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

  • 길이가 1 이상인 배열이 함수 arrSum 에 입력된 경우
    • 입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 쪼개고, 둘을 더합니다.
  • 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.strungify/parse

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

전송 가능한 조건 (transferable condition)

  • 수신자(reciever)와 발신자(sender)가 같은 프로그램을 사용한다.
  • 또는, 문자열처럼 범용적으로 읽을 수 있어야 한다.

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

  • js에서 객체를 문자열로 변환하기 위해 메서드message.toString()나 형변환(String(message))을 시도하면, [object Object] 라는 결과를 리턴한다.

이러한 문제를 해결하는 방법은 ? ⬇️

1. 객체를 JSON 형태로 변환

  • JSON.stringify : 객체 → JSON 직렬화(serialize)
    JSON으로 변환된 객체의 타입은 문자열이다. 발신자는 객체를 직렬화한 문자열을 누군가에게 객체의 내용을 보낼 수 있다.
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

2. JSON을 객체 형태로 변환

  • 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를 적용하면 다시 객체의 형태로 변환할 수 있습니다.

JSON의 기본 규칙

profile
블로그 이사했습니다 🧳

0개의 댓글