Recursive, Tree, Graph(DFS, BFS 기초) - 피보나치 재귀(메모이제이션)

public class Main {
    static int[] fibo;

    public static int DFS(int n) {
        if (fibo[n] > 0) return fibo[n];
        if (n == 1) return fibo[n] = 1;
        else if (n == 2) return fibo[n] = 1;
        else return fibo[n] = DFS(n - 2) + DFS(n - 1);
    }

    public static void main(String[] args) {
        int n = 45;
        fibo = new int[n + 1];
        DFS(n);
        for (int i = 1; i <= n; i++) {
            System.out.print(fibo[i] + " ");
        }
    }
}

- 더 빨리 구하기 위해 fibo 배열에 이미 구한 값은 저장을 해놓는다.