재귀함수

class Solution {
    // 주어진 구슬 개수 balls에서 share 개의 구슬을 선택하는 경우의 수를 구하는 함수
    public int solution(int balls, int share) {
        // combination 메서드 호출하여 조합의 수를 반환
        return combination(balls, share);
    }

    // 조합(combination)의 수를 계산하는 메서드
    public static int combination(int balls, int share) {
        // base case: share가 0이거나 balls와 share가 같으면 경우의 수는 1
        if (balls == share || share == 0)
            return 1;
        
        // 재귀적으로 combination 메서드를 호출하여 조합의 수를 구함
        // 현재 구슬을 선택하는 경우와 선택하지 않는 경우를 모두 고려하여 합산
        return combination((balls - 1), (share - 1)) + combination(balls - 1, share);
    }
}

1. solution 메서드: 이 메서드는 주어진 구슬 개수 balls와 선택할 구슬 개수 share를 인자로 받아서, 이를 combination 메서드에 전달하고, 조합의 수를 반환합니다.
2. combination 메서드: 이 메서드는 주어진 구슬 개수 balls와 선택할 구슬 개수 share를 인자로 받아서, 이를 기반으로 조합의 수를 재귀적으로 계산합니다.
   • 기저 사례(Base Case): balls와 share가 같거나 share가 0인 경우, 이는 선택할 구슬 개수와 주어진 구슬 개수가 같거나 하나도 선택하지 않는 경우입니다. 따라서 경우의 수는 항상 1을 반환합니다.
   • 재귀 호출(Recursive Call): 그 외의 경우에는 현재 구슬을 선택하는 경우와 선택하지 않는 경우를 모두 고려하여 재귀적으로 combination 메서드를 호출하고, 그 결과를 합산하여 반환합니다. 현재 구슬을 선택하는 경우는 balls - 1에서 share - 1개의 구슬을 선택하는 경우이며, 선택하지 않는 경우는 balls - 1에서 share개의 구슬을 선택하는 경우입니다.

이러한 방식으로 combination 메서드는 기저 사례에 도달할 때까지 재귀적으로 호출되며, 모든 경우의 수를 합산하여 최종적인 조합의 수를 반환합니다. 재귀 함수는 문제를 더 작은 부분으로 분할하여 해결할 수 있도록 도와주는 강력한 도구입니다.