재귀

재귀함수의 정의

재귀함수란 정의 단계에서 자신을 재참조하는 함수를 뜻합니다.
즉, 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 함수를 말합니다.

문제가 간단해져서 바로 풀 수 있는 문제로 작아질 때까지 조금씩 조금씩 더 작은 경우를 해결하도록 하는 것이 포인트 입니다.

간단한 예시

public int factorial(int n) {
    if (n == 0) // base case
        return 1;
    return n * factorial(n-1); // recursive case
}

위는 팩토리얼($!n$)을 간단하게 재귀함수로 구현한 것입니다.
만약 factorial(3)를 호출한다면 어떻게 될까요?

$factorial(3)=3\times factorial(2)=3\times 2\times factorial(1)=3\times 2\times 1$

factorial메서드 내부에서 다시 자기 자신 factorial을 호출함으로써 for와 같은 반복문 없이 코드를 단순화하였습니다.

장점

이렇듯 재귀함수는 다음과 같은 장점을 지닙니다.

1. 변수 사용을 줄이며 코드가 단순해진다.
2. 점화식이나 피보나치 수열과 같이 알고리즘 자체가 재귀적인 표현이 자연스러운 경우에는 재귀 함수를 쓰는 것이 오히려 가독성도 좋고 구현이 간편해진다.

단점

1. 재귀함수가 끝나지 못하고 계속해서 재귀적으로 호출 될 경우, 스택 오버플로우가 발생할 위험이 있다.
2. 스택 프레임을 구성하고 해제하는 과정에서 반복문보다 오버헤드가 커서 상대적으로 성능도 낮다.
3. 오류를 추적하기 어렵다.

따라서 재귀함수는 적절히 사용해야 하며, 사용할 때에는 항상 함수가 더 이상 재귀 호출하지 않고 끝날 수 있는 조건을 설정해줘야 합니다. (base case)

base case & recursive case

• 기저 사례
• 탈출 조건
• 종료 조건

모두 'base case'를 이르는 말입니다.
base case라 함은 재귀함수에서 가장 작은 단계까지 가서 '더 이상 쪼개지지 않고' 종료되도록 하는 재귀 호출을 말합니다.

모든 재귀함수는 바로 이 base case를 가져야 하며, 기저 사례를 선택할 때는 존재하는 모든 입력이 항상 기저 사례의 답을 이용해 계산될 수 있도록 신경 써야 합니다.

위에서 작성된 factorial메서드의 base case는 n이 0인 경우입니다.

if (n == 0) // base case
    return 1;

factorial(n)은 n*factorial(n-1), n*(n-1)*factorial(n-2)로 쪼개지다가 결국 base case를 만나게 되고, 재귀호출이 종료되게 됩니다.

연습문제

https://www.acmicpc.net/step/19