[21일차] 자바 재귀 함수

유태형·2022년 5월 24일

Java 알고리즘 코드스테이츠

코드스테이츠

목록 보기

21/77

오늘의 목표

재귀함수란 어떤 것인가
재귀함수가 유리할 때
재귀함수의 템플릿

내용

재귀함수란 어떤 것인가

일반적인 반복문

예를 들어 배열에 있는 숫자들을 더해서 합을 구하는 메서드를 작성한다고 하면 일반적으로 합을 저장할 sum변수를 for문이나 while문등으로 반복적으로 배열의 요소들을 더할 것입니다.

public static int sumArr(int[] arr){
	int sum = 0; //합을 저장할 변수
    for(int num : arr) //배열 요소 마다
		sum += num; //값을 더함
    return sum; //합 반환
}

위와 같이 하나의 함수안에서 반복문으로 효율적으로 구할 수 있지만, 문제를 다른 관점에서 보면 하나의 문제는 더 작은 또 다른 문제로 나뉘어 질 수 있습니다.

문제를 더 작게 나누기

위의 문제를 예시를 들어 분석해 보겠습니다. 배열 [10,3,6,2]가 인자로 주어졌다고 가졍하면 합을 구할때 요소 하나를 빼서 구하게 됩니다.

[10, 3, 6, 2]를 한번에 모두 더하는것을 10 + [3,6,2] 와 같이 하나의 요소를 따로 뺀다음 각각 더해도 합은 같을 것입니다.
10 + [3,6,2]하나의 요소를 따로 뺀 다음 더하는 것을 10 + 3 + [6, 2]와 같이 두개의 요소를 따로 뺀다음 전부 더해도 합은 같을 것입니다.
10 + 3 + [6, 2]두개의 요소를 따로 뺀 다음 전부 더하는 것을 10 + 3 + 6 + [2]와 같이 세개의 요소를 뺀 다음 전부 더해도 합은 같을 것입니다.
10 + 3 + 6 + [2]세개의 요소를 따로 뺀다음 전부 더하는 것을 10 + 3 + 6 + 2 + []와 같이 네게의 요소를 뺀 다음 전부 더해도 합은 같을 것입니다.

반복문으로 합을 구하는 함수를 더 작은 문제로 나눈 재귀적 함수로 바꾸어 보겠습니다.

sumArr([10,3,6,2]) = 10 + sumArr([3,6,2]);
10 + sumArr([3,6,2]) = 10 + 3 + sumArr([6,2]);
10 + 3 + sumArr([6,2]) = 10 + 3 + 6 + sumArr([2]);
10 + 3 + 6 + sumArr([2]) = 10 + 3 + 6 + 2 + sumArr([]);

무한히 작게 나누어 질 수 없으므로 어디 까지 문제를 나눌지 기준을 정해야 합니다.

sumArr([])에서 배열에 더이상 더할 요소가 없으므로 단순히 0을 return

문제를 작게 나누어 각각 더하는 재귀적 함수의 실행 과정입니다.

sumArr([10,3,6,2]) = 10 + sumArr([3,6,2]);
10 + sumArr([3,6,2]) = 10 + 3 + sumArr([6,2]);
10 + 3 + sumArr([6,2]) = 10 + 3 + 6 + sumArr([2]);
10 + 3 + 6 + sumArr([2]) = 10 + 3 + 6 + 2 + sumArr([]);
//더이상 문제가 작아지지 않음

//이전의 합들이 return되며 더해짐
10 + 3 + 6 + 2 + sumArr([]) = 10 + 3 + 6 + 2 + 0;
10 + 3 + 6 + sumArr([2]) = 10 + 3 + 6 + 2;
10 + 3 + sumArr([6,2]) = 10 + 3 + 8;
10 + sumArr([3,6,2]) = 10 + 11;
sumArr([10,3,6,2]) = 21;

가능한 가장 작은 단위까지 문제가 나누어 지는 파트가 진행되다가 일정 기준까지 나누어 지면 다시 합쳐지는 파트가 진행됨을 확인할 수 있습니다.

재귀함수가 유리할 때

재귀함수는 모두 반복문으로 표현될 수 있습니다. 게다가 반복문은 단순히 자료구조를 반복해서 순회할 뿐이지만 재귀함수는 함수를 다시 호출해야 하므로 반복문보다 함수전환간 오버헤드가 훨씬 크기 때문에 효율도 좋지 않습니다.

하지만 재귀함수를 사용하는것이 더 적합할 때도 있습니다.

문제를 더 작은 문제를 나눌 수 있는 경우
반복문의 중첩이 많거나 중첩횟수를 예측하기 어려운 경우
변수사용을 줄임으로써 오류발생 가능성을 낮출 경우

재귀함수의 템플릿

배열의 합을 구하는 sumArr 함수를 재귀식으로 좀더 이해하기 쉽게 풀이해 보도록 하겠습니다.

sumArr : [int] -> int

배열의 요소들을 구해야 하므로 배열의 요소들을 표현하겠습니다.

sumArr : [int] -> sumArr(new int[] {e1,e2,e3,...,en})

재귀함수는 무한히 나누어질 수 없으므로 어디까지 나누어질지 탈출 조건을 정의해야 합니다.

sumArr : [int] -> sumArr(new int[]{}) = 0 / sumArr(new int[] {e1,e2,e3,...,en})

재귀 함수는 더 작은 문제로 나뉘어 질 수있습니다.

sumArr : [int] -> sumArr(new int[]{}) = 0 / sumArr(new int[] {e1,e2,e3,...,en}) = sumArr(new int[]{e1}) + sumArr(new int[]{e2,....,en})

코드와 주석

public int sumArr(int[] arr){
	if(arr.length==0) return 0; //종료 조건(더이상 문제가 나뉘어 질 수 없음)
    
    /*
    * 문제가 더 쪼개어 질 수 있을 경우
    * 현재 요소 + 나머지 배열
    */
    return arr[0] + sumArr(arr[1~arr.length)); 
    //배열을 나누는 방법은 Arrays.copyOfRange(), System.arraycopy(), 스트림등 다양한 방법이 존재
}