재귀호출이란? (Recursive Call)

재귀 함수란?

---

특정 함수 내에서 자기 자신을 다시 호출하여 문제를 해결해나가는 함수

문제를 해결하기 위해 원래 범위의 문제에서 더 작은 범위의 하위 문제를 먼저 해결함으로써 원래 문제를 해결해 나갑니다.

⚠️ 종료지점을 제대로 생각하지 않고 구현을 하면 스택오버플로우가 발생할 수 있으니 항시 주의해서 구현을 해야 합니다.

 

---

예제문제

---

백준 1463

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class DP_1463 {
    static Integer[] dp;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int X = Integer.parseInt(br.readLine());

        dp = new Integer[X + 1];
        dp[0] = dp[1] = 0;

        System.out.println(recur(X));
    }

    static int recur(int N) {
        if (dp[N] == null) {

            // 6으로 나눠지는 경우
            if (N % 6 == 0) {
                dp[N] = Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 1;
            }
            // 3으로만 나눠지는 경우
            else if (N % 3 == 0) {
                dp[N] = Math.min(recur(N / 3), recur(N - 1)) + 1;
            }
            // 2로만 나눠지는 경우
            else if (N % 2 == 0) {
                dp[N] = Math.min(recur(N / 2), recur(N - 1)) + 1;
            }
            // 2와 3으로 나눠지지 않는 경우
            else {
                dp[N] = recur(N - 1) + 1;
            }
        }
        return dp[N];
    }
}