[2017.12.22] 24. Recursion 개념과 실습

도입

이번 포스팅에서는 Recursion의 개념과 중요한 조건을 알아보고 실습을 할 예정이다.

Recursion의 개념

(출처 - https://en.wikipedia.org/wiki/Recursion_(computer_science))

Recursion은 재귀 함수(자기 자신을 호출하는 함수)이다.

위의 설명과 같이 Recursion 함수는 자신을 다시 호출한다. 

여기서 알아야 할 점은

모든 Recursion은 반복문으로 표현 가능하고,

모든 반복문 또한 Recursion으로 표현 가능하다.

그렇다면 Recursion을 왜 사용 할까?!!

Recursion을 사용하는 이유 

Recursion을 사용하므로 복잡한 알고리즘을 단순하게 표현 할 수 있다.

예를 들어, "Binary Search"라는 탐색 방법을 구현 할 때 

1) for문이나 While을 사용 할 경우, 다중 반복문 때문에 코드를 이해하는 것이 쉽지 않다.

2) Recursion 함수를 사용할 경우, 상대적으로 단순하게 표현 할 수 있다.

그러나, Recursion의 단점으로는 함수 호출 시, 반복문보다 오버헤드가 크기 때문에 성능에 문제가 생길 수도 있다.

Recursion의 중요한 조건

Recursion은 자기 자신을 호출한다. 그렇기 때문에 아래와 같은 조건을 만족해야 무한 루프에 빠지지 않는다.

1) 적어도 1개 이상의 End Condition(종료 조건)이 필요

2) Recursion은 End Condition으로 수렴해야한다.

실습

간단하게 Recursion을 이용해 int 배열안의 합을 구하는 메소드를 만들어볼 예정이다. 

// int[] data = new int[] {1,2,3,4,5};
// System.out.println(getSum(0, data.length-1, data));
private static int getSum(int start, int end, int[] data) {
    // End condition
    if (start == end)
        return data[start];
    else {
        // Data안의 합은
        // 첫번째 값을 제외한 나머지 합에 첫번째 값을 더한 값이다.
        return data[start] + getSum(start + 1, end, data);
    }
}

결과

#Recursion #재귀 함수