Algorithm | 피보나치 수열

피보나치 수열

피보나치 수열이란 앞의 두 숭의 합이 바로 뒤의 수가 되는 수의 배열을 의미한다.

이탈리아의 수학자 피보나치가 발견을 하였다.

토끼의 번식에 대하여 이야기를 했는데 어떠한 농부가 토끼를 한쌍을 가지고 있었다.

한 쌍의 토끼가 두 번째 달부터 매달 토끼를 한 쌍씩 낳는다고 가정을 한다.

매달 생기는 토끼의 수는 1,1,2,3,5,8,13,21,34,55 ... 이 된다.

이 수의 배열은 앞의 두 수의 합이 바로 뒤의 수가 되는 것을 말한다.

Java 피보나치 수열

자바에서는 기존의 수학적식과는 다르게 뒤집어서 로직을 작성을 하였다.

아래와 같은 로직을 3 -> 2 + 1 , 3 -> 1 -> 1 과 같은 로직을 가지게 된다.

public class Fibonacci {

    public static void main(String[] args) {
        int i = 10;
        int ans = progress(i);
        System.out.println("결과:: " + ans);
    }

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

}

만약에 F(3) 이라고 하면은 F(2) + F(1) 이라고 생각하면 된다.

F(2) 는 F(1) + F(0) 의 값을 1

F(1) 는 function 의 조건의 n == 0 return 0 , n == 1 return 1 로 되기 떄문에 리턴 값은 1 이다

그럼으로 결과 값은 2 가 되는 것이다.