[Java] 재귀함수 (정보처리기사 25년 1회 실기)

16. 다음은 Java 코드에 대한 문제이다. 아래 코드를 확인하여 알맞는 출력값을 작성하시오.

public class Main {
 
    public static void main(String[] args) {
        int[] data = {3, 5, 8, 12, 17};
        System.out.println(func(data, 0, data.length - 1));
    }
 
    static int func(int[] a, int st, int end) {
        if (st >= end) return 0;
        int mid = (st + end) / 2;
        return a[mid] + Math.max(func(a, st, mid), func(a, mid + 1, end));
    } 
 
}
public class Main {
 
    public static void main(String[] args) {
        int[] data = {3, 5, 8, 12, 17};
        System.out.println(func(data, 0, data.length - 1));
    }
 
    static int func(int[] a, int st, int end) {
        if (st >= end) return 0;
        int mid = (st + end) / 2;
        return a[mid] + Math.max(func(a, st, mid), func(a, mid + 1, end));
    } 
 
}

정답: 20

재귀트리

func(0,4)
│
├── mid=2 → a[2]=8
│
├── func(0,2)
│   ├── mid=1 → a[1]=5
│   │
│   ├── func(0,1)
│   │   ├── mid=0 → a[0]=3
│   │   ├── func(0,0) = 0
│   │   └── func(1,1) = 0
│   │   └── result: 3 + max(0,0) = 3
│   │
│   ├── func(2,2) = 0
│   └── result: 5 + max(3,0) = 8
│
├── func(3,4)
│   ├── mid=3 → a[3]=12
│   ├── func(3,3) = 0
│   ├── func(4,4) = 0
│   └── result: 12 + max(0,0) = 12
│
└── 최종 result: 8 + max(8,12) = 8 + 12 = 20

문제를 복잡하게도 냈네...

변수도 mid가 다시 start 자리나 end 자리 매개변수로 들어가서 변수명도 헷갈리고 복잡하다

a는 반복적으로 들어가는 배열이므로 2,3번째 인자만으로 정리해서 반드시 재귀트리 그리면서 풀기