자바 재귀함수를 이용하여 피보나치 수열 구하기

자바 재귀함수를 이용하여 피보나치 수열을 구하겠습니다.

피보나치 수열은 토끼 문제로 잘 알려져 있는데,

첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열입니다.

이를 숫자로 나열하면 1, 1, 2, 3, 5, 8... 이 됩니다.

이번에는 10번째 수까지 구하겠습니다.

 

public class TestObject {
    public static void main(String[] args)    {
        for(int i=1; i<10; ++i)    {
            System.out.print(fibonachi(i) +" , ");
        }
        System.out.println(fibonachi(10));
    }
    public static int fibonachi(int n) {
        if(n<=2) return 1;
        return fibonachi(n-2) + fibonachi(n-1);
    }
}

 

---

		for(int i=1; i<10; ++i)	{
			System.out.print(fibonachi(i) +" , ");
		}
		System.out.println(fibonachi(10));
	}

마지막 숫자를 제외하고 피보나치 숫자+,(콤마) 형식으로 출력하는 코드를 작성합니다.

 

 

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

피보나치 숫자는 위에 기입한 대로 앞의 숫자와 두번째 숫자를 더한 값이 세번째 숫자이므로,

 1, (0)+1=1, 1+1=2, 1+2=3 .... 의 흐름입니다.

따라서 3번째 있는 숫자는 첫번째와 두번째 숫자의 합 = (3-2)번째 숫자와 (3-1)번째의 숫자의 합입니다.

 첫번째와 두번째는 1, 1이므로 고정값으로 두기 위해 if조건으로 넣고, 나머지 숫자의 조건을 작성합니다.

 

10번째 숫자까지 계산하는 식을 만들었지만, 손계산은 5번째까지만 하겠습니다 ㅎㅎ

fibonachi(1) 과 fibonachi(2)는 각각 1

n에 3을 넣었을 때 : fibonachi(3-2)+fibonachi(3-1) = fibonachi(1)+fibonachi(2)= 1 + 1 = 2

n=4  : fibonachi(2)+fibonachi(3)= 1 + 2= 3

n=5 : fibonachi(3) +fibonachi(4) = 2 + 3 = 5

 

 

잘 출력되었습니다.