[Recursion] 재귀함수

- 위키백과

재귀(再歸, Recursion)는 수학이나 컴퓨터 과학 등에서 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. 주로 이 방법은 함수에 적용한 재귀 함수(Recursion Function)의 형태로 많이 사용된다. 또 사진이나 그림 등에서 재귀의 형태를 사용하는 경우도 있다.

재귀함수는 다음과 같은 규칙이 있습니다.

1. 적어도 하나의 base case 를 가지도 있어야 합니다. (순환되지 않고 종료되는 case)

2. 모든 case 는 결국 base case 로 수렴해야 합니다.

예제

1. 팩토리얼 함수

int factorial(int n) {
    if(n == 0) {
        return 1;
    } else {
        return n * factorial(n-1);
    }
}

2. 피보나치 함수

int fibonacci(int n) {
    if(n < 2) return n;
    else return fibonacci(n-1) + fibonacci(n-2);
}

3. 최대공약수

int gcd(int p, int q) {
    if(q == 0) return p;
    else return gcd(q, p%q);
}

4. 순차탐색

int search(int[] data, int n, int target) {
    for(int i = 0; i < n; i++) {
        if(data[i] == target) {
            return i;
        }
    }
    return -1;
}

n 은 data의 갯수로 target 값이 data의 어느 포지션에 있는지를 구할 수 있습니다.

하지만 이를 더 좋은 재귀함수로 바꾸기 위해서는 다음과 같은 원칙이 있습니다.

1. 시작값과 끝값을 명시적으로 표시함

2. 모든 매개변수를 명시적으로 표시하는것이 기본 원칙

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);
    }
}

5. 최대값 찾기

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));
    }
}

6. 이진탐색

int binarySearch(String[] items, int begin, int end, String target) {
    if(begin > end) {
        return -1;
    } else {
        int middle = (begin + end) / 2;
        int compResult = target.compareTo(items[middle]);
        if(compResult == 0) {
             return middle;
        } else if(compResult < 0) {
            return binarySearch(items, begin, middle-1, target);
        } else {
            return binarySearch(items, middle+1, end, target);
        }
    }
}

compareTo 함수가 나온다.

이는 String 객체에 있는 함수로 두개의 값을 비교한다. 비교하는 값이 비교 대상과 같으면 0 을 리턴하며 비교하는 값이 더 작으면 -1 을 반대면 1을 리턴하는 함수이다. 이때 비교 대상과의 문자열의 크기를 비교한다.