자바 피보나치 수열 완벽 가이드: 반복문과 재귀 알고리즘 구현하기

자바 피보나치 알고리즘 가이드

피보나치 수열(Fibonacci Sequence)은 바로 앞에 있는 두 수를 더하여 다음 수를 계산해 나가는 수열입니다.

이 수열은 수학 분야에서 유명할 뿐만 아니라 자연 속에서도 쉽게 찾아볼 수 있습니다. 대표적인 예로, 대부분의 꽃잎은 피보나치 수열과 같은 패턴으로 배열되어 있습니다.

이번 가이드에서는 자바(Java)를 사용해 피보나치 수열을 계산하는 방법을 살펴보겠습니다. 초보자도 쉽게 따라올 수 있도록 두 가지 피보나치 알고리즘을 단계별로 설명합니다.

피보나치 수열이란?

피보나치 수열은 고등학교 수학 시간에서 한 번쯤 들어본 개념일 것입니다.

수열의 첫 번째와 두 번째 숫자는 각각 0과 1입니다. 그 이후의 숫자들은 앞의 두 수를 더한 값으로 계산됩니다. 실제 수열을 나열하면 다음과 같습니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

이 수열은 원하는 만큼 무한히 이어질 수 있습니다.

피보나치 수열을 프로그래밍으로 구현하는 방법은 크게 두 가지가 있습니다.

• 반복문(iteration)을 사용하는 방식
• 재귀(recursion) 알고리즘을 사용하는 방식

지금부터 두 가지 방법을 하나씩 자세히 알아보겠습니다.

반복문으로 구현하는 피보나치 자바 프로그램

먼저 소개할 방법은 반복문(iterative) 방식입니다. 반복 프로그래밍이란 for 문과 같은 루프를 사용해 목록을 순회하며 작업을 수행하는 기법을 말합니다.

반복 프로그래밍을 활용하면 반복적인 절차를 자동화할 수 있습니다. 피보나치 수열에는 다음 숫자를 계산하는 명확한 공식이 존재하기 때문에, 반복문 방식으로 알고리즘을 손쉽게 구현할 수 있습니다.

먼저 클래스와 메서드를 선언하고, 프로그램에서 사용할 세 개의 변수를 정의하겠습니다.

public class FibonacciSequence {
	public static void main(String[] args) {
		int number = 5, firstTerm = 0, secondTerm = 1;
	}
}

여기서 각 변수의 역할은 다음과 같습니다.

• number: 계산할 항의 개수를 추적합니다.
• firstTerm: 수열의 첫 번째 값을 저장합니다.
• secondTerm: 수열의 두 번째 값을 저장합니다.

프로그램이 진행됨에 따라 firstTerm과 secondTerm은 방금 계산한 값의 앞 두 항을 저장하도록 갱신됩니다.

이제 for 루프를 작성해 수열의 다음 피보나치 숫자들을 계산해 보겠습니다.

for (int i = 0; i < number; ++i) {
	System.out.println(firstTerm);

	int nextNumber = firstTerm + secondTerm;
	firstTerm = secondTerm;
	secondTerm = nextNumber;
}

이 루프는 먼저 firstTerm의 값을 출력합니다. 첫 번째 반복에서 출력되는 값은 0입니다. 그다음 루프는 firstTerm과 secondTerm을 더해 다음 숫자를 계산합니다.

이후 코드는 firstTerm에 secondTerm의 값을 대입하고, secondTerm에는 새로 계산된 nextNumber를 대입합니다. 이렇게 하면 매 반복마다 앞의 두 항이 올바르게 갱신됩니다.

코드를 실행하면 결과는 다음과 같습니다.

0
1
1
2
3

코드가 성공적으로 수열의 첫 다섯 개 값을 계산했습니다.

재귀로 구현하는 피보나치 자바 프로그램

피보나치 수열은 재귀(recursive) 알고리즘으로도 계산할 수 있습니다. 재귀 함수란 문제를 해결하기 위해 스스로를 다시 호출하는 함수를 의미합니다. 피보나치 수열은 일관된 계산 공식이 있기 때문에 재귀 알고리즘을 적용하기에 적합합니다.

먼저 클래스를 초기화하겠습니다.

class FibonacciSequence {
}

다음으로, 재귀를 사용해 수열의 다음 값을 계산하는 함수를 작성합니다.

static void getNextValue(int number, int firstTerm, int secondTerm) {
	if (number > 0) {
		System.out.println(firstTerm);

		int nextNumber = firstTerm + secondTerm;
		firstTerm = secondTerm;
		secondTerm = nextNumber;
		getNextValue(number - 1, firstTerm, secondTerm);
	}
}

이 메서드는 firstTerm과 secondTerm의 값을 더해 다음 값을 계산합니다. 이 과정은 number 값이 0보다 클 때까지 반복됩니다. 여기서 number는 아직 계산해야 할 남은 항의 개수를 추적하는 역할을 합니다.

다음 값이 계산되면 getNextValue() 함수가 재귀적으로 호출됩니다. 이때 number 값이 1씩 감소하는데, 그 이유는 함수가 실행될 때마다 새로운 숫자 하나가 계산되기 때문입니다.

이제 재귀 함수를 사용하는 main 프로그램을 작성하고 필요한 변수를 선언하겠습니다.

public static void main(String args[]) {
	int number = 5, firstTerm = 0, secondTerm = 1;
	getNextValue(number, firstTerm, secondTerm);
}

number는 계산하고자 하는 값의 개수를 나타내며, firstTerm은 수열의 첫 번째 항, secondTerm은 두 번째 항입니다.

getNextValue 메서드를 호출하면 계산이 시작됩니다. 코드를 실행해 피보나치 수열을 출력해 보겠습니다.

0
1
1
2
3

피보나치 수열의 첫 다섯 개 값이 성공적으로 계산되었습니다!

마무리

피보나치 수열은 수학, 컴퓨팅, 그리고 자연 곳곳에서 흔히 발견되는 개념입니다. 수열의 다음 숫자는 앞의 두 수를 더해 계산되며, 수열은 0과 1에서 시작합니다.

이 수열은 반복문 방식 또는 재귀 방식 중 어느 쪽으로든 구현할 수 있습니다. 이제 여러분도 자바로 피보나치 수열을 직접 계산할 준비가 되었습니다. 두 방식의 장단점을 비교해 보면서 자신에게 맞는 구현 방식을 선택해 보세요.