재귀호출 - Recursive Call

재귀호출이란 무엇인가?

자신 자신을 호출하는 형태의 함수를 말한다.

어디에 쓰이는가?

같은 로직을 반복적으로 호출하는 작업에 많이 쓰인다. 정렬이나, 검색, 그래프의 종주에 보통 쓰인다.

재귀 함수는 어떻게 구성되는가?

재귀 호출은 자기 자신을 호출하여 하위 작업을 수행하게 되는데, 재귀 함수를 분석하고 설계하다보면 자기 자신을 호출하지 않고도 답이 나오는 하위 작업이 있다. 이를 base case라고 한다. 

쉽게 설명하자면 "Factorial에서 n이 1일 때는 1을 리턴해준다."

재귀 알고리즘에는 재귀 케이스(recursive)와 기본 케이스(base case)로 나뉜다. 이 두 개를 어떻게 잘 설계할 수 있는지 생각해보면 된다.

재귀 함수의 장점은 무엇인가?

재귀 함수는 보통 코드를 간결하게 만들어준다.

예를 들어 보겠다. 

팩토리얼을 구현하는  재귀적인 방법과  반복적인 방법이다.

// recursive하게 구현
    public static int Factorial(int n){
        if(n == 1)
            return 1;
        else
            return n * Factorial(n - 1);
    }
    
    // iterative하게 구현
    public static int Factorial_Iterative(int n){
        int result = 1;
        for(int i = 1;i<=n;i++){
            result *= i;
        }
        return result;
    }

재귀 함수의 단점은 무엇인가?

보통 팩토리얼과 같은 경우에 간단한 로직을 실행하는데 드는 비용보다 재귀함수를 스택에 쌓고 호출하는데 드는 시간적 비용이 더 많이 든다. 그래서 반복적인 루틴을 사용하는 코드보다 재귀적인 루틴을 사용하는 코드가 더 시간이 오래 걸린다.

보통 재귀함수로 실행 할 수 있는 로직은 반복적인 코드로도 만들 수 있다. 

재귀함수를 통해서 간결하게 코드를 만들 수 있는 예 - 이진 검색

예) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10이 있을 때 9를 몇 번만에 찾을 수 있을까?

public static int binary_search(int[] arr, int first, int last, int number, int target){
        int mid = (first + last) / 2;
        if(arr[mid] == target || arr[first] == target || arr[last] == target)
            return number;
        if(target < arr[mid]){
            return binary_search(arr, first, mid, number+1, target);
        }else{
            return binary_search(arr, mid + 1, last, number + 1, target);
        }
}

이진 검색을 위와 같이 구현해봤다.

특정 범위의 시작과 끝, 또는 중간 값이 해당하는 값이면 탐색을 끝낸다. 

매번 인자에 재귀함수의 수행 횟수를 인자로 넘기는데, 답이 나오면 이 값을 리턴해주면 몇 번만에 검색 되었는지를 알 수 있다.

*참고 : 이진탐색의 시간복잡도와 특징*

이진 탐색(검색) 시간 복잡도 : Log(n)

특징 : 탐색 리스트가 정렬되어 있어야 된다는 점