자료구조/알고리즘 재귀

재귀

• 재귀(再歸) : 원래 자리로 되돌아오거나 되돌아옴

• 재귀 코드 예시

  public void recursion() {
    System.out.println("This is");
    System.out.println("RECURSION!!!!");
    recursion();
  }
  
  > 출력
  > This is
  > RECURSION!!!!
  > This is
  > RECURSION!!!!
  > This is
  > RECURSION!!!!
  > This is
  > ...

• 재귀 함수 : 자기 자신을 호출하는 함수

• 재귀 함수 장점

  • 불필요하게 여러 반복문 사용 방지
  • 코드 단순화
  • 변수 많은 사용 X

• 재귀 함수 단점

  • 코드의 흐름을 직관적으로 파악하기 어려움
  • 반복문과 달리 메서드를 호출하며 지역변수, 매개변수, 반환값을 모두 process stack에 저장
    • 반복문보다 더 많은 메모리 사용
  • 메서드 호출 ~ 종료 이후 복귀를 위한 컨텍스트 스위칭 비용 발생
    • 컨텍스트 스위칭 : 대기 ↔ 실행을 번갈아 하는 것
    • 컨텍스트 스위칭 비용 : 스케쥴러가 기존 실행 프로세스를 우선 순위에서 미루고, 새 프로세스로 교체해야 할 때 프로세스 상태값을 교체 하는 작업

• 재귀함수 사용 조건

  • 문제의 크기를 점점 작은 단위로 쪼갤 수 있어야함
  • 재귀 호출이 종료되는 시점이 존재해야함
    • 종료시점이 없을 시 무한루프

• 재귀적 사고 연습

  1. 재귀 함수의 입력값과 출력값 정의하기
  2. 문제를 쪼개고 경우의 수를 나누기
  3. 단순한 문제 해결하기
  4. 복잡한 문제 해결하기
  5. 코드 구현하기

JSON

• JSON 탄생 배경

  • JSON(JavaScript Object Notation)은 데이터 교환을 위해 만들어진 객체 형태의 포맷
  • Java 를 사용하지 않는 프로그램에서는 데이터를 정확하게 파악하기 어려움
  • 이 문제를 해결하는 방법은 객체를 JSON형태로 변환하거나 JSON을 객체의 형태로 변환하는 방법
  • 여러 방법 존재

• jackson 라이브러리에서 제공하는 ObjectMapper 클래스를 사용한 JSON형태로 변경하는 방법

  ObjectMapper mapper = new ObjectMapper();
  String json = mapper.writeValueAsString(message); // 직렬화(serialize)
  
  System.out.println(json);
  
  /*
  출력
  {"createdAt":"2022-09-01,10:10:10","receiver":"이자바","sender":"박스프링","message":"같이 코딩공부할래?"}
  */

  • writeValueAsString 과정을 직렬화(serialize)한다고 함
  • 위와 같이 JSON으로 변환된 객체를 다시 객체의 형태로 만들 수 있음

  ObjectMapper mapper = new ObjectMapper();
  String json = "{\"createdAt\":\"2022-09-01,10:10:10\",\"receiver\":\"이자바\",\"sender\":\"박스프링\",\"message\":\"같이 코딩공부할래?\"}";
  
  Map<String, String> deserializedData = mapper.readValue(json, Map.class); // 역직렬화(deserialize)
  System.out.println(deserializedData);
  
  /*
  출력
  {createdAt=2022-09-01,10:10:10, receiver=이자바, sender=박스프링, message=같이 코딩공부할래?}
  */

• readValue를 적용하는 과정을 역직렬화(deserialize)한다고함

• JSON은 키와 값 사이, 키-값 쌍 사이에 공백이 존재해서는 안됨

• JSON