재귀 함수 : 직접 또는 간접적으로 자신을 호출하는 프로세스를 말한다.
장점 : 여러 개의 반복문을 사용하지 않기 때문에 코드가 간결하고 수정이 용이하다.
단점 : 반복문과 달리 코드의 흐름을 직관적으로 파악하기 어렵다.
반복문에 비해 메모리를 더 많이 사용한다.
재귀로 문제를 해결하는 방법
1. 문제를 좀 더 작게 쪼갠다.
2. 1번과 같은 방식으로 가장 작은 단위 까지 문제를 쪼갠다.
3. 가장 작은 단위의 문제를 해결함으로써 전체 문제를 해결한다.
재귀함수 예제
자연수로 이루어진 배열을 입력받고, 리스트의 합을 리턴하는 메서드 'arrSum' 을 작성하라.
반복문
public int arrSum(int[] arr) {
int sum = 0;
for(int i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}재귀
public int arrSum (int[] arr) {
// 빈 배열을 받았을 때 0을 리턴하는 조건문
// --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
if (arr.length == 0) {
return 0;
}
int[] tail = Arrays.copyOfRange(arr, 1, arr.length);
// 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
// --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
return arr[0] + arrSum(tail);
}arrSum 메서드의 작동 과정
오늘 드디어 Section2 알고리즘 첫 관문인 재귀함수를 배웠다. 재귀함수의 알고리즘을 이해하는데 조금 오래 걸리긴 했지만 이해하고나니 뿌듯하고 후련한 기분까지 들었다. 이런 알고리즘 문제들이 코딩테스트에 나온다고 생각하니 벌써부터 두렵지만 쉬운 문제로 생각되게끔 반복과 연습을 하는 것이 중요한 것 같다.
