[Algorithm] 재귀함수를 이용한 피보나치 수열 구현

문제

1) 피보나키 수열을 출력한다. 피보나치 수열이란 앞의 2개의 수를 합하여 다음 숫자가 되는 수열이다.

2) 입력은 피보나치 수열의 총 항의 수 이다. 만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다.

 

메모이제이션을 사용하지 않은 구현

import java.util.Scanner;

public class Section7_4_Ver1 {
    public static int DFS(int n) {
        if (n == 1 || n == 2)    return 1;
        else  return DFS(n - 2) + DFS(n - 1);
    }

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

반복문을 이용해 출력한다. 이렇게 되면 매 숫자를 출력할 때마다 1부터 다시 재귀를 시작해야하는 치명적인 단점이 있다. 한 45까지만 가도 굉장히 오랜 시간이 걸린다. 그래서 메모이제이션을 사용한 재귀함수 구현을 통해 이 문제를 해결할 수 있다.

 

메모이제이션을 사용한 구현

import java.util.Scanner;

public class Section7_4_Ver2 {
    static int[] memo;

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

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

중요한 포인트: memo[n]에 값이 있다면, memo[n]을 return 한다. 

위의 사진을 보면 DFS(3)에서 먼저 DFS(2)를 구했는데 또 DFS(4)에서 DFS(2)가 한 번 더 호출되어야한다. 

또, DFS(4)에서 DFS(3)이 먼저 호출 되었는데, 또 DFS(5)에서 DFS(3)을 호출한다. 이렇게 되면 3은 또 한 번 재귀를 반복해야한다.

먄약 수가 커진다면 정말 엄청난 시간이 걸릴것이기 때문에 이미 배열에 있는 값이라면 그 값을 return하도록 하는것이 매우 중요하다!