RecursiveFunction

재귀함수

재귀함수는 자기자신 호출하여 종료조건을 만날때까지 계속해서 반복하는 함수입니다.

재귀함수는 주로 반복적인 작업을 수행하거나 복잡한 문제를 해결하는데 유용하게 활용되고 있습니다.

구조

기본 케이스는 함수가 자기 자신을 호출하지 않고 바로 값을 반환하는 종료조건입니다.

이는 무한루프에서 빠지지 않도록 하는 역할을 하고 있습니다.

재귀 케이스는 함수가 자기 자신을 호출하여 문제를 더 작은 부분 문제로 나누고 해결하는 부분입니다.

이 단계에서 함수가 호출될 떄마다 입력값이 변경되어야 하며, 종료 조건에 수렴하도록 해야 합니다.

즉, 재귀함수는 자기자신을 지속적으로 호출하는 함수인데, 여기서 기본적으로 자기자신을 호출하는 반복문을 종료하는 조건문이 있어야 하고, 자기자신이 호출될때마다 입력값이 변동되어야 합니다.

예시 코드 [ 백준 11724 부분 코드 ]

static void DFS(int z) {
        if (visited[z]) {
            return;
        }
        visited[z] = true;
        System.out.println("visited = " + Arrays.toString(visited));
        for (int i : list[z]) {
            DFS(i-1);
        }
    }

위의 코드는 재귀함수의 예시입니다.

보이는 것처럼 기본케이스가 주어져있고, 재귀 케이스가 주어져 있습니다.

참고로 반드시 입력값이 변동되어야하고, 이에 따라 종료조건이 맞아 떨어져야 합니다.