적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야함

모든 case는 결국 base case로 수렴해야 함

모든 순환함수는 반복문(iteration)으로 대체가 가능하다.

그역도 성립함. 즉 모든 반복문은 resursion으로 표현 가능함

순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 함

하지만 함수 호출에 따른 오버해드가 있음 (매개변수 전달, 액티베이션 프레임 생성 등)

Recursion

1~n 까지의 합을 구하라. (n >=1)

public static int func(int n) {
    if (n <= 0)
        return 0;
    else
        return n + func(n-1);
}

Factorial: n! ( n>0, n==0:n=1)

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

Fibonacci number: f=0, f1=1

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

Euclid method (최대공약수)

: m>=n 인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면, gcd(m,n)=n 이고, 그렇지 않으면 gcd(m, n) = gcd(n, m%n) 이다.

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

문자열의 길이 계산

public static int length(String str) {
    if (str.equals(""))
        return 0;
    else
        return 1 + length(str.substring(1));
}

Sequential search

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 search(int[] data, int begin, int end, int target) {
    if (begin > end)
        return -1;
    else {
        int middle = (begin+end) / 2;
        if (data[middle] == target)
            return middle;

        int index = search (data, begin, middle-1, target);

        if (index != -1)
            return index;
        else 
            return search(data, middle+1, end, target);
    }
}

Find Max

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

public static int findMax(int[] data, int begin, int end) {
    if (begin == end)
        return data[begin];
    else {
        int middle = (begin+end) / 2;
        int max1 = findMax(data, begin, middle);
        int max2 = findMax(data, middle+1, end);
        return Math.max(max1, max2);
    }
}

Binary search (데이터는 순차적으로 정렬되어 있어야 한다.)

public static int binarySearch(String[] items, String target, int begin, int end) {
    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(itmes, target, begin, middle-1);
        else
            return binarySearch(items, target, middle+1, end);
    }
}