재귀 함수의 이해
개념
- 재귀(recursive) : 원래의 상태로 돌아오는 것
장단점
- 여러 반복문 및 변수 사용 방지, 코드 간결, 수정 용이
- 코드 흐름 파악 어려움, 메모리 사용량 방대, 메서드 반복으로 context switching 비용 발생
사용 조건
- 문제를 비슷한 구조로 더 작은 단위로 쪼갤 수 있어야 함
- 재귀 함수의 종료 시점 존재
재귀 함수 접근법
- 문제 쪼개기 : 큰 문제에서 작은 부분 문제들로 쪼개기
- 가장 작은 문제로 쪼개기 : 가장 마지막 문제로 재귀 함수를 탈출할 조건
- 문제 해결
사용 케이스
- 문제를 더 작은 비슷한 구조의 문제로 쪼갤 수 있는 경우
- 반복문의 중첩 횟수를 측정하기 어렵거나 너무 많은 경우
- mutable state(변경 가능 상태)를 제거하기 위해 변수 사용을 줄이는 경우
재귀 함수 풀이 과정
- 함수의 입력값과 출력 값 정하기
- 문제를 쪼개고 경우의 수 나누기
- 가장 작은 문제(base case) 해결하기
- 더 큰 문제들(recursive case) 해결하기
템플릿
public [출력값] [함수명]([입력값]){
if([base case 조건]){
return [가장 작은 문제의 결과];
}
return [보다 큰 문제들 결과];
}
JSON(JavaScript Object Notation)
사용 배경
- 데이터를 전송하기 위해서는 같은 프로그램을 사용하거나 문자열 같은 범용적으로 읽을 수 있어야 함
- 다른 프로그램에 데이터를 전송하기 위해서 사용
용어
- 직렬화(serialize) : 객체를 JSON 파일로 변환하는 과정
- 역직렬화(deserialize) : JSON 파일을 객체로 변환하는 과정
사용 방법
ObjectMapper om = new ObjectMapper();
String jsonStr= om.writeValueAsString(message); //객체를 String 형태의 json으로 변환
Map<String, String> map=om.readValue(jsonStr,Map.class); // json 데이터를 map 객체로 변환
규칙
- 자바스크립트의 key는 따옴표 없이 사용 가능하고 문자열은 어떤 따옴표를 사용해도 됨
- JSON은 key, 문자열 모두 큰따옴표 사용
재귀 함수와 메모리 사용량 간의 관계
- 재귀 함수는 지속적으로 함수를 호출하여 매개변수, 지역변수, 리턴 값, 리턴 위치를 stack에 저장
- 콜 하는 재귀 함수가 많아질 때 stack에 함수를 호출할 때마다 생기는 데이터가 많아져 메모리 낭비
꼬리 재귀(tail recursion)
- 재귀 함수의 큰 오버헤드를 보안하기 위한 방법
- 재귀 함수를 호출 시 추가 연산을 하지 않도록 구현
- 컴파일러가 꼬리 재귀 최적화를 지원해야 한다
- 자바에서는 지원하지 않는데, 함수형 인터페이스와 람다식으로 구현이 가능하다
//일반 재귀
int factorial(int num){
if(num==1) return 1;
return num*factorial(num-1);
}
//꼬리 재귀
int tailRecursiveFactorial(int num, int result){
if(num==1) return result;
return factorial(num-1, num*result); // 재귀 함수 호출 후 연산이 존재하지 않는다.
}
int factorial(n,1);
//컴파일러 입장에서 반복문으로 변경되어 실행되고 스택도 한 번만 호출
하노이의 탑
- 조건
- 3개의 기둥이 존재하고 한쪽에서 다른 쪽으로 쌓여 있는 원반을 옮기는 게임
- 원반은 위로 갈수록 작은 원반만 쌓을 수 있다
- 원반의 개수(n), A, B, C의 기둥에서 A에서 C로 이동하는 최소 이동을 기술
- 구현
void hanoi(int n, String start, String mid, String end) {
if (n == 0) return;
hanoi(n - 1, start, end, start);
System.out.printf("%s기둥에서 %s기둥으로 %d번째 원판을 이동\\n", start, end, n);
hanoi(n - 1, mid, start, end);
}
hanoi(8, "A", "B", "C"); //A기둥에서 C기둥으로 8개의 원판을 옮기는 경로
System.out.println((int)Math.pow(2,8)-1); //총 이동횟수는 2^n-1
- 점화식 : T(N)=2T(N-1)+1
- T(N)+1=2(T(N-1)+1)
- 공비 2의 공비 수열
- 초항 T(1)+1=2
- T(N)+1=2^n
- T(N)=2^n-1
- O(2^n)
조합(Combination) 재귀 함수
- n개의 원소 중에 r개의 원소를 중복 없이 순서 상관없이 조합하는 경우의 수
- $nCr=n!/(n-r)! r!$
int comination(int n, int r){
if(n==r || r==0) return 1;
return comination(n-1,r-1) + combination(n-1, r);
} // n개의 원소 중 한개를 선택할 수도 있고 선택 안할 수도 있다.
최대공약수(GCD), 최소공배수(LCM)
- LCM=A*B/GCD : A=Ga, B=Gb, AB=GGa*b, LCM=Gab
int GCD(int A, int B){
return B==0 ? A : GCD(B, A%B);
}
//유클리드 호제법
//A=Bq+r
//GCD(A,B)=GCD(B, r)
//=GCD(B,(A%B))
//그런데 A%B 즉 A를 B로 나눈 나머지가 0이면 B가 GCD가 된다
//이것을 일반화하면 위의 식이 된다.