재귀함수란?
함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식이다.
그렇기에 특정 분기까지 자기 자신을 계획해서 호출하는데 주로 반복문을 구현할 때 사용한다.
그렇기에 반복문으로 구현 가능한 로직은 모두 재귀함수로 구현 가능하며,
재귀함수 또한 반복문으로 구현 가능하다.
반복문의 대표적인 예시
public int factorial(int n){
// 탈출 조건
if(n<1){
return 1;
}
retrun n*factorial(n-1); // n=5 return 5*4*3*2*1 = 120
}
이를 좀 더 이해하기 쉽도록 콜스택을 살펴보자
factorial(5)를 호출하게 되면 return에서 5*actorial(5-1)이 수행되면서 factorial(4)호출되고 반환을 기다린다.
그럼 그 다음에는 factorial(4)에 대한 지역변수, 매개변수, 반환주소값 등이 콜스택에 쌓이게 되고 이런식으로 factorial(4~1)까지 차곡 차곡 쌓인 후 factorial(1)에서 if(n<1)을 만나 해당 콜스택이 하나씩 수행되며 사라질 것이다.
Stack overflow
이러한 재귀 함수 사용에는 스택 오버플로우를 주의해야 한다.
예를 들어 위 코드에서 if(n<1) 을 뺀다고 가정하면 어떻게 될까?
n=-1, -2, -3, ... n 까지 무한대로 실행될 것이고, 컴퓨터 메모리의 한계가 오게 되니 콘솔창에 StackOverflowError를 마주하게 될 것이다.
재귀함수의 장단점
장점
- 변수를 여럿 만들 필요가 없음
- while문, for문을 사용하지 않아도 되니 코드가 간결해진다.
단점
- 지속적인 함수를 호출하세 되면서 콜스택에 값이 쌓이게 되고 메모리 사용이 많이 되면서 속도저하로 이어질 수 있음
해결책 : 꼬리 재귀(tail call recursion)
재귀 호출이 끝나는 시점에서 바로 결과를 반환하도록 만든다.
그렇기 위해서 return 값에 연산이 없어야 한다!
// Basic recursion
public int factorial(int n){
// 탈출 조건
if(n<1){
return 1;
}
return n*factorial(n-1); // n=5 return 5*4*3*2*1 = 120
}
// Tail recursion
public int factorial(int n, int prev){
// 탈출 조건
if(n<1){
return 1;
}
return factorial(n-1, n*prev); // n=5 return 5*4*3*2*1 = 120
}
차이점을 잘 보면 반환부분 코드가 달라졌다. 꼬리 재귀의 핵심은 반환부에 연산이 없어야 한다는 점이다.
이렇게 반환부에 연산이 없도록 구현을 한다면 컴파일러는 꼬리 재귀 최적화를 지원하여 자체적으로 재귀함수를 해석해서 반복문으로 변경해서 실행한다.
재귀의 관점
- 점화식 관점 :
- 반복 순차 방식 :
(재귀호출 방식이 아닌 하나의 반복문으로도 해결 가능) - 분할 병합 방식 : 하나의 반복문으로 해결이 어려운 문제들
- 점화식으로 표현할 수 있는 것은 실행 흐름을 따라가는 것 보다 점화식 그 자체를 코드로 옮기는 데에 익숙해질 필요가 있다
- 분할 관점 = (분할 정복 알고리즘)
- 배열 : 중앙값(앞 인덱스 + 마지막 인덱스) / 2
좌/우의 합계
좌측 : (앞 인덱스, 중앙값)
우측 : 중앙값 + 1, 마지막 인덱스
- 백트래킹 관점
- 퇴각검색, 재귀호출 시 스택프레임이 쌓이고 pop되는 스택의 특징을 이용하여
- 탐색 가능한 이전의 경우로 돌아가 다시 탐색하는 것.
- 조건을 만족하는 한 모든 경우의 수를 탐색
예제문제
(1)
// 재귀함수 이해하기 : 농구공 16m 에서 던졌을 때 한번 튕길 때 마다 높이 1/2씩 감소할 때 공의 이동거리 구하기
public static int recur(int h, int prev){
//재귀탈출조건
if(1>h){
return prev;
}
int an = (prev == 0) ? h : h*2;
int sum = prev + an;
return recur(h/2, sum);
}
public static void main(String[] args){
// 초기 높이 : 16
System.out.println(recur(16,0));
}(2) 피보나치 수열
규칙을 생각하며 풀어보자.
피보나치 수열에서 n=5일 때 의 값을 구해보자.
public static int fivo(int n, int twoprev, int oneprev){
if(n>5){
return oneprev;
}
int sum = (n==1||n==2) ? 1 : twoprev+oneprev;
return fivo(n+1, oneprev, sum);
}
public static void main(String[] args){
System.out.println(pivona(1,1,1));
}
(3) 피보나치 수열 : 재귀 + 분할정복 알고리즘으로 풀어보기
public static int fivo(int n){
if(n==1||n==2) {
return 1;
}
return fivo(n-2) + fivo(n-1)
}
분할정복 알고리즘(divide and conquer) 이란?
그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법
(4) 분할 정복 알고리즘 : 배열의 합 구하기
public static int sum(int[] arr, startIdx, endIdx){
if(startIdx==endIdx){
return arr[startIdx]
}
midIdx = (startIdx + endIdx)/2
return sum(arr, strtIdx, midIdx) + sum(arr, midIdx+1, endIdx)
}
