재귀함수란 무엇인가?

자기 자신을 호출하는 함수

재귀함수를 사용하기 위한 조건

문제의 크기를 점점 작은 단위로 쪼갤 수 있어야 한다
재귀 호출이 종료되는 시점이 존재해야 한다

재귀함수의 구조

기본 케이스 (Base Case)

• 재귀 함수는 무한 루프를 방지하기 위해 하나 이상의 기본 케이스를 가져야 한다
• 재귀 호출을 멈추게 하는 조건이다
  ex) 팩토리얼을 계산하는 경우, 0 또는 1의 팩토리얼은 1이므로 0 또는 1이 기본 케이스가 된다

재귀 케이스 (Recursive Case)

• 재귀 함수는 자신을 호출하면서 문제를 더 작은 부분으로 나누는 재귀 케이스를 가져야 한다
  ex) n의 팩토리얼을 계산하기 위해 n! = n * (n-1)!의 형태로 자신을 호출하는 것

예시

public class RecursiveExample {
    public static int calculateSum(int n) {
        // 기본 케이스: n이 1 이하일 때 합은 그 자체이므로 n을 반환
        if (n <= 1) {
            return n;
        } else {
            // 재귀 케이스: n과 1부터 (n-1)까지의 합을 재귀적으로 계산
            return n + calculateSum(n - 1);
        }
    }

    public static void main(String[] args) {
        int n = 5;
        int sum = calculateSum(n);
        System.out.println("1부터 " + n + "까지의 합은 " + sum + "입니다.");
    }
}