Java - 재귀

재귀는 함수의 정의 단계에서 다시 자기 자신을 재 참조하는 함수를 말한다. 즉 자신 안에서 자신을 다시 호출.

이게 말로는 쉬운데 막상 코드를 쳐보면?????????? 하는 반응이 나오는데 처음 접하는 입장에서는 정말 당연한 반응이라고 생각한다. 지금의 내가 그렇고 앞으로도 그럴듯하다. 

엄밀히 보면 반복문과 비슷하고 실제로 모든 재귀 함수를 반복문으로 표현할 수 있다. 하지만 반복문안의 반복 문안의 반복 문안의 반복문처럼 코드를 작성하면 정말 헷갈릴 수 있어 이런 상황이 온다면 재귀 알고리즘을 이용하는 것이 더 효율적이다. 

하지만 마냥 치트키는 아닌데, 피보나치 수열을 보면 가장 대표적인 재귀의 예제라고 볼 수 있지만 실상은 매우 효율이 나쁘다. 중복되는 부분이 반복적으로 일어나면서 스택의 자리를 채우다가 결국에 스택이 터지는 Stack Overflow가 발생할 수 있음. 

	재귀	반복문
장점	반복문에 비해 깔끔하고 간결한 코드	속도가 재귀에 비해 빠름
단점	메모리 소모 큼 반복문에 비해 속도 느림 변수 사용을 줄일 수 있음 (변경 가능 상태를 제거 - 오류 최소화)	반복문안의 반복문안의 반복문.... 헷갈리고 복잡하다.  더 많은 변수의 사용

 

재귀 알고리즘을 쓰려면 재귀에 대한 개념과 재귀적 사고를 할 줄 알아야 하는데 이게 정말 어색하게 다가온다. 

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

위는 배열의 모든 요소의 합을 반복문 for를 통해 구현한 것이다.

예를 들어 [1,2,3,4,5]의 배열이 주어졌을 때, 아래처럼 진행될 것이다. 

sum = 0 + 1
sum = 1 + 2
sum = 3 + 3
sum = 6 + 4
sum = 10 + 5
sum = 15

이것을 재귀로 표현하면 아래처럼 된다. 

public int arrSum(int[] arr) {
        if (arr.length == 0) return 0;

        int[] recurArr = Arrays.copyOfRange(arr, 1, arr.length);
        return arr[0] + arrSum(recurArr); //arrSum 메서드를 다시 호출하고 recurArr를 파라미터로
}

[1,2,3,4,5] 를 쪼개서 계산한다고 생각하면 된다. 

arr{1,2,3,4,5}
5 + arr{1,2,3,4}
4 + arr{1,2,3}
3 + arr{1,2}
2 + arr{1}
1 + arr{0}

 

재귀에서 중요한 부분은 base case를 만드는 것인데 이는 보통 문제를 더 이상 나눌 수 없는 경우 돌아가기 위한 조건 체크포인트라고 생각하면 될 것 같다. 

재귀 1 -> 재귀 2 -> 재귀 3 -> base case --return--> 재귀3 --return--> 재귀2 --return--> 재귀1 

 

---

오늘 풀었던 과제의 일부분을 예제로 보면 stringify라는 메서드가 정의되어 있고 그 안에 if문 여러 개가 있다. 

만약 파라미터로 Object 타입의 배열 ["a", 1] 이 들어갔다고 쳤을때, 배열로 입력을 받으니 가장 아래의 if문으로 들어가고 배열의 요소 타입을 확인해서 각각에 맞는 타입으로 변환시키기 위해 재귀를 하는 것을 볼 수 있다. 

public String stringify(Object data) {

        //입력된 값이 문자열일 경우
        if (data instanceof String) {
            return "\"" + data + "\"";  
        }
        //입력된 값이 Integer일 경우
        if (data instanceof Integer) {
            return String.valueOf(data); //Integer타입 data -> String타입 전환
        }
        //입력된 값이 Boolean일 경우
        if (data instanceof Boolean) {
            return String.valueOf(data); //Boolean타입 data -> String타입 전환
        }
}

if (data instanceof Object[]) {
            Object[] arr = (Object[]) data;
            for (int i = 0; i < arr.length; i++) {
                arr[i] = stringify(arr[i]); //여기서 재귀함수 
            }
            return Arrays.toString(arr).replaceAll(" ", "");
}