[재귀 함수]
1. 재귀의 개념
// 재귀 코드 예시
public void recursion() {
System.out.println("This is");
System.out.println("recursion");
recursion();
}
- 자기 자신을 호출하는 함수를 재귀 함수라고 지칭
- 장점
1) 반복적인 작업을 해야 하는 문제를 더 간결한 코드로 풀어낼 수 있으며 수정 용이
2) 변수를 여러 개 사용할 필요 X
3) 중첩된 반복문이 많거나, 반복문의 중첩 횟수 예측이 어려울 경우 용이
- 단점
1) 코드 흐름에 대한 직관적 파악이 제한됨
2) 지역변수/매개변수/반환값을 모두 process stack에 저장하기 때문에, 반복문에 비해 많은 메모리를 사용
3) 메서드가 종료된 이후 복귀를 위한 컨텍스트 스위칭 비용이 발생
- 컨텍스트 스위칭
: 한 개의 CPU는 하나의 프로세스를 처리할 수 있기 때문에, 여러 프로세스 간 참조를 이루기 위해 실행 중인 프로세스를 계속해서 변화시키는 과정
: 프로세스는 독립된 메모리 영역을 할당받았기 때문에 공유하는 메모리 존재 X, 따라서 컨텍스트 스위칭이 발생하는 경우 캐시 초기화/메모리 매핑 초기화/커널 모드로의 진입이라는 세 가지 비용이 항상 수반됨
- 재귀 함수 사용 조건
1) 문제의 크기를 점점 작은 단위로 쪼갤 수 있어야 함
2) 재귀 호출이 종료되는 시점이 존재해야 함
- 모든 재귀 함수는 반복문(while/for문)으로 표현 가능
2. 재귀 함수 설계 과정
- 문제를 작게 쪼개기
- 문제를 가장 작은 단위로 쪼개기
- 문제를 쪼개는 방식을 반복해 더 이상 쪼갤 수 없는 상태까지 쪼개기
- 가장 작은 단위의 문제부터 해결
3. 재귀적 사고
- 재귀 함수의 입력값과 출력값 정의
- 문제를 쪼개고 경우의 수 나누기
- 문제를 어떻게 쪼갤 것인지 기준을 정한 후, 정한 기준에 따라 문제를 큰 경우와 작은 경우로 나눌 수 있는지 확인
- 주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제 구분에 유용
- 단순한 문제 해결
- 가장 해결하기 쉬운 문제부터 해결(= base case)
- base case는 재귀 함수 구현 시, 재귀의 탈출 조건을 구성
- 복잡한 문제 해결
- 코드 구현
//재귀 함수 템플릿
public type recursive(input1, input2, ...) {
// Base Case : 문제를 더 이상 쪼갤 수 없는 경우
if (문제를 더 이상 쪼갤 수 없을 경우) {
return 단순한 문제의 해답;
}
// recursive Case
// 그렇지 않은 경우
return 더 작은 문제로 새롭게 정의된 문제
// 예1. someValue + recursive(input1Changed, input2Changed, ...)
// 예2. someValue * recursive(input1Changed, input2Changed, ...)
}
[JSON]
1. JSON
- JavaScript Object Nation의 줄임말로, 데이터 교환을 위해 만들어진 객체 형태의 포맷
- 메시지 데이터가 전송되려면, 발신자와 수신자가 같은 프로그램을 사용하거나 범용적으로 읽을 수 있는 형태여야 함
- String 타입으로 변환해 보낼 경우, 자바를 사용하지 않는 프로그램에서는 데이터를 정확하게 파악 불가
- 문제 해결을 위해 객체를 JSON 형태로 변환하거나, JSON을 객체로 변환
