[자료구조] 재귀 함수(Recursive Function)

1. 재귀 함수란?

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

---

2. 재귀 함수의 흐름

• 재귀 함수가 호출되면 복사본 생성 >> 복사본들이 실행

---

3. 재귀 함수의 탈출

• 재귀 함수는 탈출 조건이 필요하다. (∵한 번 호출되면, 계속 호출되어 무한 루프에 빠짐)
• Base Case 
  • 더이상 쪼개지지 않는 경우
  • 순환하지 않고 종료하는 case
  • 모든 case는 Base Case로 수렴

---

4.  재귀함수 예시

• 배열의 합 구하기 예시

// 배열의 합 예시

package Recursion;

import java.util.Arrays;

public class ExampleArrSum {
    public static void main(String[] args) {
        int arr[] = {-1,-3,1,4};
        System.out.println(arrSum(arr));
    }
    public static int arrSum(int[] arr){
    /*
    * 배열을 [-1,-3,1,4]이라 가정
    * 쪼개보기
    arr[0] + arr[1] + arr[2] + arr[3]
    == -1 + arrSum([-3,1,4])
            == 3 + arrSum([1,4])
                   == 1 + arrSum([4])
                          == 4
    
    * 결론 : arr[0] + arrSum(arr의 첫번째 요소(인덱스0)를 뺀 나머지 배열)
    */

        // Base Case : 더 이상 쪼갤 수 없는 경우
        if (arr.length == 0 ) return 0;

        // Recursive Case(자기 자신을 호출하는 함수를 포함하는 경우) : 작게 쪼갤 수 있는 경우
        // 첫번째 요소를 뺀 나머지 배열을 만들어주기 >> 배열 복사
        // Arrays.copyOfRange(복사할 배열, 복사를 시작할 인덱스(부터), 복사를 끝낼 인덱스(까지, 포함 안됨))
        int[] tail = Arrays.copyOfRange(arr, 1, arr.length);

        return arr[0] + arrSum(tail);
    }
}

/* 출력
1
*/

---

참고 한 것

1. 블로그

2. 블로그