재귀 호출

재귀 호출

• 함수 안에서 동일한 함수를 호출하는 형태
• 여러 알고리즘 작성시 사용된다.

예제

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

시간복잡도 : O(N) (n - 1번의 반복문을 호출하는 것 이기 때문에)

일반적인 형태

형태 1

fucntion(입력) {
    if (입력 > 일정값) {
        return function(입력 - 1);
    } else {
        return 특정값;
    }
}

형태 2

function(입력) {
    if (입력 <= 일정값) {
        return 특정값;
    }
    return function(입력 - 1);
}

재귀 호출은 스택의 전형적인 예

함수는 내부적으로 스택처럼 관리된다.

재귀호출 연습문제

숫자가 들어있는 배열이 주어졌을 때 배열의 합을 리턴하는 코드를 작성하시오.

    public int sum(List<Integer> list) {
        if (list.size() == 0) {
            return 0;
        }
        return list.get(0) + sum(new ArrayList<>(list.subList(1, list.size())));
    }