알고리즘) 재귀 함수와 메모이제이션(Memoization)으로 피보나치 수열 구하기

 재귀 함수란, 자기 자신을 호출하는 함수를 말한다. 흔히 연속적인 규칙이 있는 수들을 나열할 때 유용하다. 가장 대표적으로 재귀를 이용해 해결할 수 있는 문제는 피보나치 수열 출력이다. 피보나치 수열이란 1, 1, 2, 3, 5, 8, 13, ...와 같이 앞의 두 요소를 더한 값이 다음 요소가 되는 수열을 말한다. 재귀함수로 피보나치 수열의 N번째 수를 구하는 방법은 아래와 같다. recurse(n)의 값을 출력하면 그만인 것이다.

import java.util.Scanner;

public class Main {
    static int recurse(int n) {
        if (n == 1 || n == 2) return 1;
        return recurse(n - 2) + recurse(n - 1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        System.out.print(recurse(i));
    }
}

 

 위의 코드를 수정해 피보나치 수열을 출력해보자. 피보나치 수열의 길이 N 만큼 출력하기 위해선 recurse(n)가 반환한 값을 출력하는 main 메서드의 부분을 수정하면 된다.

import java.util.Scanner;

public class Main {
    static int recurse(int n) {
        if (n == 1 || n == 2) return 1;

        return recurse(n - 2) + recurse(n - 1);
    }

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

 

 위에 작성한 코드의 단점은 피보나치 수열의 길이인 N이 커질 수록 시간효율성이 매우 떨어진다. 이를 해결하는 방법으로 메모이제이션이라는 방법이 있다. 메모이제이션(Memoization)이란, 이미 계산했던 값을 메모리에 올려두고, 하위 문제에 대한 정답을 계산했는지 확인해가며 하향식으로 문제를 풀어나가는 방식이다. 쉽게 말해 캐싱한다라고 표현할 수도 있겠다.

import java.util.Scanner;

public class Main {
    static int[] result;
    static int recurse(int n) {
        if (n == 1 || n == 2) return result[n] = 1;
        else return result[n] = recurse(n - 2) + recurse(n - 1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        result = new int[num + 1];
        recurse(num); // 배열에 수열의 모든 값을 담기 위해 한번은 전체 재귀 실행
        for (int i = 1; i <= num; i++) System.out.print(result[i] + " ");
    }
}

 

 위와 같이 메모이제이션을 해도  재귀가 들어가게 되면 재귀 횟수가 늘어남에 따라 걸리는 시간이 극명하게 차이가 난다. 하지만 입력값이 작다면 메모이제이션을 하는게 조금이라도 더 빠르게 문제를 해결할 수 있는 방법이 된다.