[자바 /Java] 피보나치 구현 - 재귀 / 반복문

 

1. 재귀함수

1) 메모이제이션 x

public class Fibonacci {

    public static recursive(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return recursive(n - 1) + recursive(n - 2);
        }
    }

    public static void main(String[] args) {
        int n = 10;  // 원하는 피보나치 수열의 항 개수
        for (int i = 0; i < n; i++) {
            System.out.print(recursive(i) + " ");
        }
    }
}

 

2) 메모이제이션O

public class Fibonacci {
	static int[] memo;

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

    public static void main(String[] args) {
        int n = 10;  // 원하는 피보나치 수열의 항 개수
        memo = new int[n + 1];  // 메모이제이션을 위한 배열 초기화
        for (int i = 0; i < n; i++) {
            System.out.print(fibonacciMemo(i) + " ");
        }
    }
}

 

 

2. 반복문

public class Fibonacci {

    public static int fibonacciIterative(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            int fibPrev = 0;
            int fibCurr = 1;
            for (int i = 2; i <= n; i++) {
                int temp = fibCurr;
                fibCurr = fibPrev + fibCurr;
                fibPrev = temp;
            }
            return fibCurr;
        }
    }

    public static void main(String[] args) {
        int n = 10;  // 원하는 피보나치 수열의 항 개수
        for (int i = 0; i < n; i++) {
            System.out.print(fibonacciIterative(i) + " ");
        }
    }
}