1. 재귀(Recursion) 이란?

재귀 함수란 어떤 함수에서 자기 자신을 다시 호출하여 반복적인 작업을 수행하는 방식의 함수를 의미한다.

이에 재귀 함수는 반복문으로 변환할 수 있고, 반복문 또한 재귀함수로 변환할 수 있어야 한다.
재귀 함수의 필수적인 조건은 종료 조건인데, 종료 조건이 없는 재귀함수는 'RecursionError'를 발생시키기 때문이다.
이는 재귀 깊이에 대한 메모리 제한을 걸어두었기 때문이다.

2. 재귀의 기본 형태

public static void main(String[] args) {
    String returnString = recursive(5); // 재귀함수(메서드) 호출부

    System.out.println(returnString); // "12345"
}

/* 재귀함수(메서드) */
public static String recursive(int i) {
    if (i == 1) { /* base case */
        return "" + i; // "1"
    }

    return recursive(i - 1) + i; /* 재귀적 호출 */
}

3. 재귀의 특징

1. 내부에서 스스로를 호출하는 부분이 있어야 한다.
   위 코드에서 '재귀적 호출'이라고 주석한 부분에서 볼 수 있듯이 메서드 자신을 호출하고 있다. 이렇듯 반복적으로 자기 자신을 호출해야한다.

2. base case가 있다.
   반복문에는 조건식이 있어서 조건식이 true를 나타낼 동안 루프를 돈다. 다시 말해 반복문의 조건식은 수행될 조건을 명시하는 식이다.
   위 코드에서 base case라고 주석처리된 if문이 재귀함수의 조건식입니다. 보통은 베이스케이스(base case)라고 부른다. 반복문의 조건식과 다른 점은, 재귀함수의 조건식은 대개 탈출 조건이 명시된다는 점이다.
   재귀함수는 내부에서 자기 자신을 호출하기 때문에, 탈출 조건이 없으면 무한히 자기 자신을 호출하게 된다.

3. 재귀함수는 호출될 수록 base case에 수렴해야 한다.
   위 코드에서는 i == 1이면 재귀호출을 멈추고 리턴하도록 강제하고 있다. 최초로 호출하는 메인 메서드에서는 i값으로 10을 넘겨주고 있다.
   그런데 만약에, 최초로 넘겨준 10이란 값이 점점 줄어들지 않고, 재귀를 거칠수록 1씩 커진다고 해보면
   recursive(10)... recursive(11)... recursive(12)...... recursive(100)............ recursive(1000000)... 이렇게 재귀호출은 끝나지 않고 호출될 것이다. 스택오버플로우가 발생하기 전까지 말이다.
   그래서 위 코드의 '재귀적 호출' 주석 부분의 코드를 보면, i값이 매번 1씩 감소되도록 하고 있다. i == 1이라는 base case에 가까워지도록 말이다.

4. 재귀 예시

• 팩토리얼(factorial)
  자연수 n에 대해서 1부터 n까지의 모든 자연수를 곱한 값을 의미한다.

public class Main {
    public static void main(String[] args) {
        System.out.println(factorial(5)); // 5! = 5 * 4 * 3 * 2 * 1 = 120
    }

    public static int factorial(int n) {
        if (n == 0) { // 기본 케이스
            return 1;
        } else { // 재귀 케이스
            return n * factorial(n - 1);
        }
    }
}