파보나치 수열

문제

입력받은 정수 n길이의 파보나치 수열 출력

package inflearn.seven.피보나치수열;

import java.util.Arrays;

public class Main {


    public static void main(String[] args) {
        int num = 50;
        solution(num);
    }

    public static void solution(int num){
        int previous1 = 0;
        int previous2 = 1;
        for(int i = 1; i<= 10; i++){
            int temp = previous2;
            previous2 += previous1;
            previous1 = temp;
            System.out.print(previous1 + " ");
        }
    }
}

1. For문을 이용한 풀이
   이전 값을 기억하면 된다.

package inflearn.seven.피보나치수열;

import java.util.Arrays;

public class Main {


    public static void main(String[] args) {
        int num = 50;
        arr = new int[num];
        solution2(num);
        Arrays.stream(arr).forEach(i -> System.out.print(i + " "));
    }

    static int[] arr;
   
    public static int solution2(int num){
        if(num == 1 || num == 2) {
            arr[num-1] = 1;
            return 1;
        }
        if(arr[num-1] != 0 )return arr[num-1];
        arr[num-1] = solution2(num-1) + solution2(num-2);
        return arr[num-1];
    }
}

2. 재귀함수를 이용한 풀이

숫자를 기억할 배열을 먼저 선언하고 자기에게 맞는 index에 값을 집어넣되, 자신의 값은 다시 solution함수를 호출하여 찾는다.
예를 들어 n이 10인 경우 자신의 값은 solution(9) + solution(8)을 통해 찾는다.
num이 1과 2인 경우 값이 1 고정이므로 분기문을 추가하여 값을 할당한다.

주의 -> n이 1이 될 때까지 각 스택은 또 다른 스택을 쌓아가며 무수히 많은 스택이 쌓이게 된다.
예를 들어 num 이 10인 경우 num 9, 8에 대한 함수가 호출되고 그 아래로는 다시 num 6,7,8,9에 대한 함수가 호출되어 트리 형식으로 무수히 뻗어나가는데 이 때문에 성능이 크게 저하되므로 배열에서 값이 이미 있는 경우 함수를 호출하지 않고 값을 return하도록 하여 성능을 향상시킬 수 있다.