Java 재귀 함수(Recursion) 개념과 재귀 함수를 사용하는 이유

'재귀 함수(Recursion)의 개념'

 

'재귀적 호출(Recursive call)'은 일정 조건을 만족할 경우 자신을 호출하는 것을 말하며, 이러한 방식으로 구현한 함수를 '재귀 함수'라고 합니다.

재귀 함수는 잘못된 구조로 코드를 짠 경우 무한루프에 빠질 수도 있는데요. 입력값의 변화가 없거나 입력값의 변화가 특정 패턴을 반복하게 되면 그 재귀 함수는 영원히 반복되다가 콜 스택 초과로 프로그램이 종료되어 버립니다. 따라서 재귀 함수를 설계할 때는 적절한 구조를 통해 무한루프에서 빠져나오도록 해야 합니다.

 

여기에서 적절한 구조란 'Base case'라고 하는 적어도 하나의 재귀(Recursion)에 빠지지 않는 경우가 존재해야 하며, 또 한 가지 'Recursive case'가 필요한데 'Recursive case'는 재귀(Recursion)를 반복하다 보면 결국 'Base case'로 수렴해야 한다는 조건입니다.

 

// 피보나치 수열
public static int fibonacci(int n) {
    if (n<2) {
        return n;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

// 팩토리얼
public static int factorial(int n) {
    if (n==0) {
        return 1;
    } else {
        return n * factorial(n-1);
    }
}

(재귀 함수로 구현할 수 있는 대표적인 알고리즘으로는 피보나치수열, 팩토리얼, 거듭제곱, 최대 공약수 등이 있습니다.)

 

 

---

 

 

'재귀 함수를 사용하는 이유'

 

재귀 함수는 for, while을 사용한 반복문(iteration)으로 변경할 수 있고, 반대로 for, while을 사용한 반복문을 재귀 함수로 표현할 수 도 있는데요. 

재귀 함수는 위에서 언급한 것처럼 잘못 사용하면 무한루프에 빠져 스택오버플로우를 발생시킬 수도 있고, 무한루프에 빠지지 않더라도 함수가 계속 호출되면서 함수의 매개변수, 지역변수, 리턴 값 함수 종료 후 돌아가는 위치가 스택 메모리에 저장되면서 stack이 쌓여 결국 마찬가지로 스택오버플로우를 발생시킬 수도 있습니다.

(메모리를 많이 차지하며, 성능이 반복문에 비해서 느리다고 하는 이유입니다.)

 

 

'이러한 단점을 가진 재귀 함수를 구현해서 사용한다면 그 이유는 무엇일까요?'

 

'첫 번째'로 재귀 함수의 장점은 경우에 따라 가독성을 높일 수 있다는 것입니다.

알고리즘 자체가 재귀적인 표현이 자연스러운 경우에는 재귀 함수를 쓰는 것이 가독성이 높습니다. 위에서 예로 든 피보나치 수열이나 팩토리얼 같은 경우 알고리즘을 기술한 그대로를 가지고 코드로 표현할 수 있기 때문에 for문보다 더 직관적으로 코드를 이해할 수 있습니다.

 

'두 번째'는 변수의 사용을 줄여준다는 것입니다.

변수의 사용을 줄여준다는 것은 변수가 저장되는 메모리에 대한 이야기가 아니라 'mutable state(변경 가능한 상태)'를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄여준다는 이야기이며, 이는 변수의 수를 줄이는 것뿐만 아니라 변수가 가질 수 있는 값의 종류 또는 범위도 제한하게 되어 함수를 단순하게 만들고, 불변적으로 유지될 수 있도록 합니다.

 

 

 

---

 

 

'재귀 함수의 단점을 해결하기 위한 조건, 꼬리 재귀 최적화(TCO)'

 

'꼬리 재귀 최적화(TCO, tail call optimization)' 방식으로 구현된 재귀 함수는 위에서 언급된 재귀 함수의 스택오버플로우 문제를 해결할 수 있고, 반복문과 성능 차이도 발생시키지 않습니다.

꼬리 재귀로 구현된 재귀 함수는 컴파일 시 컴파일러가 꼬리 재귀를 인식하고 최적화하면서 반복문으로 바꿔주기 때문입니다.

(꼬리 재귀 요청이 스택에 걸리는 대신 이전 실행 지점으로 점프해서 작동됩니다.)

 

이러한 꼬리 재귀 최적화에는 프로그래머가 재귀 함수를 꼬리 재귀 방식으로 구현해야 한다는 조건과 컴파일러가 꼬리 재귀  최적화를 지원해야 한다는 두 가지 조건이 있습니다.

 

// 꼬리 재귀 최적화가 되지 않은 재귀 함수
int recursive(int n) 
{
 if(n==1) return 1;
 return n + recursive(n-1);
}

// 꼬리 재귀 최적화된 재귀 함수
int tailRecursive(int n, int acc)
{
 if(n==1) return acc;
 return tailRecursive(n-1, n + acc );
}

꼬리 재귀 최적화가 되지 않은 재귀 함수의 경우 return에서 'n + 함수(n-1)'이라는 연산이 필요한데, 이러한 연산으로 인해 함수가 호출될 때마다 호출 스택 메모리를 잡아먹게 되는 것입니다.

 

반면 꼬리 최적화된 재귀 함수를 보면 매개변수로 필요한 연산을 전달하기 때문에 return에서 따로 '연산이 필요하지 않습니다.'

 

 

---

 

 

'재귀 함수 설계 시 고려해야 하는 부분'

 

재귀 함수 설계 시에는 앞에서 이야기한 것처럼 적어도 하나의 Base case 즉, 순환되지 않고 종료되는 case가 있어야 하며, 모든 case는 결국 Base case로 수렴하는 Recursive case가 있어야 합니다.

거기에 추가적으로 암시적(implicit) 매개변수가 아닌 명시적(explicit) 매개변수를 사용해야 한다는 조건이 있는데요. 아래 for문으로 구현된 일반적인 순차 탐색 알고리즘을 재귀 함수로 바꾸는 과정을 통해 살펴보겠습니다.

 

    // 일반적인 순차 탐색
    public static int search(int[] data, int n, int target) {
        for (int i=0; i<n; i++) {
            if (data[i]==target) {
                return i;
            }
        }
        return -1;
    }

일반적인 순차 탐색 알고리즘입니다.

이 함수의 미션은 data[0]에서 data[n-1] 사이에서 target을 검색하는 것입니다. 하지만 함수의 매개변수에서 검색 구간의 시작 인덱스인 0은 보통 생략하게 됩니다. 이것을 암시적 매개변수라고 합니다.

 

다시 이야기하면 [0, n-1] 배열 인덱스에서 'n-1'은 n이라는 매개변수에 의해서 명시된 표현이지만 '0'은 배열의 데이터가 n 개니까 인덱스는 당연히 0부터 시작하겠지라는 생각으로 암시적으로 적용된 것입니다.

즉, 시작 지점이 명시적으로 함수의 매개변수에 표시되어 있지 않다는 것입니다.

 

 

 

    // 순차 탐색(매개변수의 명시화)
    // search(data, 0, n-1, target)으로 호출한다면 위 함수와 완전히 동일한 기능을 수행한다.
    public static int search(int[] data, int begin, int end, int target) {
        if (begin>end) {
            return -1;
        } else if (target==data[begin]) {
            return begin;
        } else {
            return search(data, begin+1, end, target);
        }
    }

    // 최대값 찾기(매개변수의 명시화)
    public static int findMax(int[] data, int begin, int end) {
        if (begin==end) {
            return data[begin];
        } else {
            return Math.max(data[begin], findMax(data, begin+1, end));
        }
    }

같은 기능을 재귀 함수로 구현한 코드입니다.

이 함수의 미션은 data[begin]에서 시작하여 data[end] 사이에서 target을 검색합니다. 즉, 검색 구간의 시작점을 명시적(explicit)으로 지정합니다.

 

시작 지점이 명시적으로 지정되어야 하는 이유는 재귀적 호출(Recursive call)로 부르는 함수의 시작 지점이 'begin+1'이라는 것을 통해 알 수 있는데요. 시작 구간을 명시적으로 하지 않으면 재귀적 호출에서 부르는 함수에서 시작 구간이 달라지는 것을 표현할 수 있는 방법이 없기 때문입니다.

따라서 재귀 함수는 맨 처음 호출될 때의 상황만 생각하고 설계하는 게 아니라 재귀적 호출로 자기 자신을 호출할 때 필요한 매개변수까지 표현할 수 있는 좀 더 일반적인 함수로 구현되어야 합니다.

 

 

 

 

< 참고 자료 >

재귀 함수는 언제 써야 할까?

 

재귀함수를 쓰는 이유

자바 프로그래머에게 재귀는 왜 어려운가?