[Java] 피보나치(fibonacci) 수열을 반복 함수, 재귀 함수로 연산하기 + 재귀 함수의 단점

피보나치수열을 반복 함수와 재귀 함수 두 가지 방법으로 연산해보자.

 

 

 

피보나치수열이란

이전 두 수의 합이 다음 수가 되는 수열을 말한다.

 

1 + 1 + 2 + 3 + 5 + 8 + 13 + ...

 

 

 

반복 함수 사용

반복 함수는 for 문이나 while 문을 사용해서 함수를 구축하는 것이다.

 

public class Main {
	
	public static int fibonacci(int number) {
		int one = 1;
		int two = 1;
		int result = -1;
		
		if (number == 1) {
			return one;
		} else if (number == 2) {
			return two;
		} else {
			for(int i = 2; i < number; i++) {
				result = one + two;
				one = two;
				two = result;
			}
		}
		return result;
		 
	}

	public static void main(String[] args) {

		System.out.println(fibonacci(10)); // 55
		
	}

}

 

 

 

 

재귀 함수 사용

재귀 함수는 for 문과 while 문을 이용하지 않더라도 스스로 자기와 똑같은 형태의 함수를 호출함으로써 문제를 해결하는 방법이다.

 

public class Main {
	
	public static int fibonacci(int number) {
		if (number == 1) {
			return 1;
		} else if (number == 2) {
			return 2;
		} else {
			return fibonacci(number - 1) + fibonacci(number - 2);
		}
		 
	}

	public static void main(String[] args) {

		System.out.println(fibonacci(10));
		
	}

}

 

피보나치 연산의 경우 재귀 함수를 사용하면 코드가 더 간결해 보이지만 반복 연산이 훨씬 많아지므로 비효율적이다. 위 코드의 경우 대략적으로 2의 10승 정도의 연산이 필요하다. 

재귀 함수는 때에 따라서 간결한 코드를 제공하지만 연산하는 데에 더 많은 시간을 소비할 수 있기 때문에 주의해서 사용해야 한다.