자바 피보나치 수열 재귀,반복 함수 구현

피보나치 수열 재귀함수

public class Test {

	public static int fibonacci(int num) {
		if(num == 1) {
			return 1;
		}
		else if(num == 2) {
			return 1;
		}
		else {
			return fibonacci(num -1) + fibonacci(num -2);
		}
	}		
	public static void main(String[] args) {
		System.out.println("피보나치 수열의 10번째 원소는 " + fibonacci(10) + "입니다.");
	}
}

피보나치 수열 반복함수

public class Test {

	public static int fibonacci(int num) {
		int one = 1;
		int two = 1;
		int result = -1;
		if(num == 1) {
			return one;
		}
		else if(num == 2) {
			return two;
		}
		else {
			for(int i=2; i<num; i++) {
				result = one + two;
				one = two;
				two = result;
			}
		}
		return result;
	}		
	public static void main(String[] args) {
		System.out.println("피보나치 수열의 10번째 원소는 " + fibonacci(10) + "입니다.");
	}
}

출력 결과

재귀함수와 반복함수의 출력 결과는 같은 값을 가진다.

 

재귀함수는 반복함수에 비해서 간결한 코드로 코딩 할 수 있는 장점이 있지만

때에 따라 숫자가 커질 경우에 시간이 오래 걸리는 단점이 있으므로 후에 동적 프로그래밍을 다루어야한다.

 

동적프로그래밍은 대해서는 추후에 알아보도록 하자