재귀호출

재귀(Recursion)는 자신을 정의할 때 자기 자신을 재참조하는 방법이다

• 재귀함수는 전형적인 스택의 구조로 움직인다

대표적인 재귀호출의 예

팩토리얼 함수

• 메모이제이션 기법을 활용한 팩토리얼 재귀함수

private static int factorial(int num) {
    if (num > 1) {
        if (arr[num] == 0)
            arr[num] = num * factorial(num - 1);
        else
            return arr[num];
        return arr[num];
    }
    else
        arr[num] = num;
        return num;
}

주어진 리스트의 합을 구하는 재귀함수

private static int list_sum(List<Integer> list){
    if (list.size() == 1)
        return list.get(0);
    else if (list.size() > 1)
    {
        int last = list.get(list.indexOf(list.size() - 1));
        list.remove(list.indexOf(list.size() - 1));
        return last + list_sum(list);
    }
    else
        return 0;
}

회문 판별 재귀함수

private static boolean check_circle_str(String str){
    if (str.length() <= 1)
        return true;

    if (str.charAt(0) == str.charAt(str.length()- 1) )
        return check_circle_str(str.substring(1, str.length() - 1));
    else
        return false;
}

정수 n에 대해서 1,2,3의 조합으로 나타낼 수 있는 방법의 수를 구하는 재귀함수

• 각 케이스별로 결과값을 확인해서 규칙이나 점화식을 찾아서 구현해야한다

private static int by123(int n)
{
    // f(n) = f(n - 1) + f(n -2) + f(n - 3)
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    if (n == 3)
        return 4;
    else if (n >= 4)
        return by123(n-3) + by123(n-2) + by123(n-1);
    else
        return 0;
}