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

문도연·2022년 6월 23일
알고리즘자료구조재귀코드스테이츠
0

코드스테이츠 부트캠프 - FE

목록 보기
24/44

Chapter1. 재귀의 이해
Chapter2. 재귀의 활용
과제1 JSON.stringify
과제2 tree UI

Chapter1. 재귀의 이해

  • 재귀의 의미에 대해서 이해한다.
  • JavaScript에서 재귀 호출을 할 수 있다.
  • 재귀를 언제 사용해야 하는지 이해한다.

재귀의 개념

재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.

  • 재귀 함수: 자기 자신을 호출하는 함수
    • 재귀 함수를 잘 활용하면 반복적인 작업을 해야하는 문제를 좀 더 간결한 코드로 풀어낼 수 있음

재귀 코드 예시

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

recursion 함수의 호출 결과

재귀는 언제 사용하는 게 좋은가?

  1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
  2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우
  • 모든 재귀 함수는 반복문(while 문 또는 for 문)으로 표현할 수 있다. 그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다.
  • 또한, 재귀는 알고리즘 문제의 많은 부분을 차지하므로 익숙해지자!

Chapter2. 재귀의 활용

  • 재귀로 문제를 해결하는 방법을 이해한다.
  • 재귀의 기초(base case)와 탈출 조건에 대해 이해한다.
  • 재귀 함수를 base case와 recursive case로 나눠서 작성할 수 있다.

재귀적으로 사고하기

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

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

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

  • 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나누기
  • 함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있음. 각각의 경우는 다른 방식으로 처리해야 함.
    • arrSum: [number] => number
    • arrSum([ ]) ← 입력값이 빈 배열인 경우
    • arrSum([요소1, 요소2, ... , 요소n]) ← 그렇지 않은 경우

3. 단순한 문제 해결하기

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

  • 함수 arrSum 을 더이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때 arrSum([]) 의 리턴값은 0임.
    • arrSum: [number] => number
    • arrSum([ ]) === 0 ← 입력값이 빈 배열인 경우 : 해결!
    • arrSum([요소1, 요소2, ... , 요소n])

4. 복잡한 문제 해결하기

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

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

5. 코드 구현하기

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

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

과제 JSON.stringify - 재귀 실사용 예시

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

JSON의 탄생 배경

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

네트워크를 통해 어떤 객체 내용을 다른 프로그램에게 전송하고자 한다면 메시지를 보내는 발신자와 메시지를 받는 수신자가 같은 프로그램을 사용하거나, 문자열처럼 범용적으로 읽을 수 있는 형태여야 함

전송 가능한 조건 (transferable condition)

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

JavaScript에서 객체를 String으로 변환할 경우 객체 내용을 포함하지 않는다고 함. JavaScript에서 객체를 문자열로 변환하기위해 메서드(message.toString())나 형변환(String(message))을 시도하면, [object Object] 라는 결과를 리턴한다.

💡 이 문제를 해결하는 방법은 객체를 JSON의 형태로 변환하거나 JSON을 객체의 형태로 변환하는 방법임
-> JSON 탄생
-> 객체를 JSON의 형태로 변환하거나 JSON을 객체의 형태로 변환하면 됨

JSON 메서드

  • JSON.stringify : 객체를 JSON으로 변환
  • JSON.parse : JSON을 객체로 변환
const msg = {
    sender: "도욘",
    receiver: "윤하",
    message: "윤하야 너는 어쩜 존재가 귀엽닝?",
    createdAt: "2022-06-24 10:39:11"
}
let transferedMsg = JSON.stringify(msg)

console.log(transferedMsg)
// `{"sender":"도욘","receiver":"윤하","message":"윤하야 너는 어쩜 존재가 귀엽닝?","createdAt":"2022-06-24 10:39:11"}`

console.log(typeof(transferedMsg))
// string
// JSON으로 변환된 객체의 타입은 문자열

💡 stringify하는 이 과정을 직렬화(serialize)한다고 표현함


let obj= JSON.parse(transferedMsg)

console.log(obj); // {sender: '도욘', receiver: '윤하', message: '윤하야 너는 어쩜 존재가 귀엽닝?', createdAt: '2022-06-24 10:39:11'}

console.log(typeof obj); // object

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

JSON의 기본 규칙

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

JSON 과 재귀

자바스크립트 객체와 JSON은 대표적인 트리 구조를 가지고 있으므로, 전형적인 재귀 탐색이 가능한 구조(객체의 값으로 객체를 포함하는 구조)이기 때문에 재귀 사용을 적극 권장함

과제: JSON.stringfy 함수 직접 구현하기

function stringifyJSON(obj) {
  if (typeof obj === 'number' || typeof obj === 'boolean' || obj === null) {
    return `${obj}`
  }
  if (typeof obj === 'string') {
    return `"${obj}"`
  }
  
  
  if (Array.isArray(obj)) {
    // [1,2,3,4,5] 라면  1,2,3,4,5, -> 1,2,3,4,5 -> '[1,2,3,4,5]'
    let result = ""
    for (let el of obj) {
      result += stringifyJSON(el) + ',' //재귀!
    }
    result = result.slice(0, -1) //반점 제거
    return `[${result}]`  // 마지막에 대괄호 씌어줌
  }

  if (typeof obj === 'object') {
    // { a : "a", b : 123 } 라면 "a":"a","b":123, -> "a":"a","b":123-> '{"a":"a","b":123}'
    let result = ""
    for (let key in obj) {
      if (typeof obj[key] === 'function' || obj[key] === undefined) {
        continue
      }
      result +=`${stringifyJSON(key)}:${stringifyJSON(obj[key])},`
    }
    result = result.slice(0, -1)
    return `{${result}}` //마지막에 중괄호 씌어줌
  }
};

콘솔창에서 JSON.stringify 함수에 인자 넣어보기

과제2 tree UI

Tree UI는 화면을 구성할 때 재귀를 사용하는 가장 대표적인 예시임

const root = document.getElementById('root');

function createTreeView(menu, currentNode) {

  for(let ele of menu) {
  // base case
  // 객체 내에 key로 children이 없는 경우(완전히 작게 쪼갠 경우)
    if(!ele.children) {
      const li = document.createElement('li');
      li.textContent = ele.name;
      currentNode.append(li); // currentNode === ul
    }
    else {   
      // recursive case
      const li = document.createElement('li');
      const input = document.createElement('input');
      input.type = 'checkbox'; 
      const span = document.createElement('span');
      span.textContent = ele.name;
      const ul = document.createElement('ul');

      li.append(input, span, ul)
      currentNode.append(li) // currentNode === ul -> ul.root
      createTreeView(ele.children, ul) // 재귀
    }
  }



}

createTreeView(menu, root);
profile
문도연
중요한건 꺾이지 않는 마음이 맞는 것 같습니다
이전 포스트

22. [Section2 마무리] -기술면접, 회고

다음 포스트

24. [사용자 친화 웹] UI/UX

0개의 댓글