알고리즘/이론

Recursion - Basic, Permutation and Combinations

문괜 2024. 8. 14. 12:00
반응형

재귀 함수라고도 하는 Recursion은 함수에서 같은 함수를 다시 호출한다. 

 

대표적인 예시는 아래의 링크에 들어가보면 알 수 있다.

아래의 링크

 

이렇듯 아래의 링크를 무한정 누르게 되면 같은 함수가 수없이 반복이 되기 때문에 재귀 함수의 기본은 base case를 작성하여 더이상의 재귀가 발생하지 않도록 하는 점에 있다.

 

그래서 기본적인 Recursion의 구조는 아래와 같다.

    public static void perm(int depth) {
        if (M == depth) {
            for (int num : output) sb.append(num).append(" ");
            sb.append("\n");
            return;
        }
        for (int i = 0; i < N; i++) {
            if (!checks[i]) {
                checks[i] = true;
                output[depth] = givenNums[i];
                perm(depth + 1);
                checks[i] = false;
            }
        }
    }

 

기본적인 recursion 구조로써 특정 Depth까지의 경우의 수를 파악하는 방법이다.

 

여기서 볼 수 있듯이 총 3개의 중요한 부분을 유념하여야 한다. 

  1. Base Case 재귀가 멈춰야 하는 조건을 명시해 준다.
  2. checks 주어진 배열의 방문 여부를 확인할 수 있다.
  3. 재귀함수 호출 부분: 현재의 함수와 다른 값으로 진행 되어야 한다.

특히, Java에서의 재귀함수의 경우 Local Variables과 Static을 잘 활용해야한다. 

반응형

'알고리즘 > 이론' 카테고리의 다른 글

Two Pointers  (0) 2024.08.06