재귀 함수의 이해

재귀 함수란

재귀의 개념

• 재귀: 원래의 자리로 되돌아가거나 되돌아옴

public void recursion() {
	System.out.println("This is");
    System.out.println("recursion!");
    recursion();
}

recursion 메서드처럼 자기 자신을 호출하는 함수를 재귀 함수라고 함

• 재귀 함수의 장점
  - 불필요하게 여러 개의 반복문을 사용하지 않기 때문에 코드가 간결해지고 수정이 용이함
  - 변수를 여러개 사용할 필요가 없음
• 재귀 함수이 단점
  - 반복문과 달리 코드의 흐름을 직관적으로 파악하기 어려움
  - 반복하여 메서드를 호출하며 지역변수, 매개변수, 반환값을 모두 process stack에 저장하게 됨. 이러한 과정은 반복문에 비하여 메모리를 더 많이 사용하게 됨.
  • 메서드를 호출하고 메서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생함
• 재귀 함수를 사용하기 위한 조건
  - 문제의 크기를 점점 작은 단위로 쪼갤 수 있어야 함
  - 재귀 호출이 종료되는 시점이 존재해야 함

다르게 생각하기

문제 해결하기

문제: 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴한는 메서드 'arrSum'을 작성하세요.

정답

자연수로 이루어진 리스트(배열)의 합을 구하는 알고리즘

1. 보조변수 sum을 0으로 초기화한다.
2. 순차적으로 리스트(배열)의 구성 요소에 접근하면서 sum에 더한다.

public int arrSum(int[] arr) {
	int sum = 0;
    for(int i=0; i < arr.length; i++){
    	sum += arr[i];
    }
    return sum;
}

재귀로 문제를 해결하는 방법
1. 문제를 좀 더 작게 쪼개기
2. 1번과 같은 방식으로 문제가 더는 작아지지 않을 때까지 가장 작은 단위로 문제르 쪼갬
3. 가장 작은 단위의 문제를 해결함으로써 전체 문제를 해결함

1. 문제를 작게 쪼개기

arrSum([1, 2, 3, 4, 5]) == 1 + arrSum([2, 3, 4, 5])
arrSum([2, 3, 4, 5]) == 2 + arrSum([3, 4, 5])
...

2. 문제를 가장 작은 단위로 쪼개기

...
arrSum([3, 4, 5]) == 3 + arrSum([4, 5])
arrSum([4, 5]) == 4 + arrSum([5])
arrSum([5]) == 5 + arrSum([])

3. 문제 해결하기

arrSum([]) == 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용함
arrSum([5]) = 5 + arrSum([]) == 5 + 0 == 5;
arrSum([4, 5]) == 4 + arrSum([5]) == 4 + 5 == 9;
arrSum([3, 4, 5]) == 3 + arrSum([4, 5]) == 3 + 9 == 12;
arrSum([2, 3, 4, 5]) == 2 + arrSum([3, 4, 5]) == 2 + 12 == 14;
arrSum([1, 2, 3, 4, 5]) == 1 + arrSum([2, 3, 4, 5]) == 1 + 14 == 15;

arrSum 메서드의 리턴값이 나오면서 연쇄적으로 문제가 해결되고, 최종적으로 문제 전체가 해결됨

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 메서드가 내부에서 arrSum 메서드를 호출하면서 문제가 쪼개어져 나가고 결국은 더 이상 쪼갤 수 없는 arrSum([]) 까지 메서드가 호출됨.
arrSum([])는 조건문에 의해 더 이상 자기 자신을 호출하지 않고 숫자 0을 리턴하면서 종료됨. 그 결과 중첩되어있던 메서드들도 연쇄적으로 숫자를 리턴하고 최종적으로는 배열의 모든 요소의 합을 리턴함녀서 문제가 해결됨.