[알고리즘/java] 재귀함수 - 피보나치 수열

이 글은 인프런 [자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 ] 강의를 수강하며 작성한 글입니다.

- https://inf.run/Azjw

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

 

 

 

먼저 재귀함수의 원리가 이해되지 않는다면 전 게시물을 참조해주세요

2021.12.10 - [알고리즘/자바 알고리즘 문제풀이: 코딩테스트 대비] - [알고리즘/java] 재귀함수

[알고리즘/java] 재귀함수

 

문제 :

피보나치 수열을 출력한다. 피보나치 수열은 앞의 2개의 수를 합한 것이 다음 숫자가 되는 수열이다.

 

ex) 1 1 2 3 5 8 13 21 34 55 89..

 

입력은 피보나치 수열의 총 항의 수이다.

 

 

---

피보나치 수열의 점화식은 아래와 같다.

F(0) = 0

F(1) = 1

F(n) = F(n-2) + F(n-1) (n>1, n은 정수)

 

 

-- 코드는 입력 n값을 10으로 가정하고 설명

 

< 재귀를 이용한 기본 피보나치 수열 >

public class Main {

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

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 10;
		for (int i = 1; i <= n; i++) {
			System.out.print(DFS(i) + " ");
		}
	}

}

 

위와 같은 방법으로 피보나치 수열을 구할 수 있지만 n이 커질 수록 속도가 현저히 느려진다.

왜냐하면 예를 들어 1~10까지의 수열을 구한다면, 9까지의 수열을 각각 재귀를 사용해 구하고, 10번째 수열 값 또한 재귀로 구해야 하기 때문이다.

 

즉, DFS(10)자체가 1~10까지의 이미 수열을 구하는 과정인데 모든 수열값을 각각 재귀로 구함으로써 시간이 많이 소요된다.

 

 

 

 

< 위의 방법에서 조금 더 개선시킨 피보나치 수열 >

public class Main {

	static int[] fibo;

	public static int DFS(int n) {
		if (n == 1)
			return fibo[n] = 1;
		else if (n == 2)
			return fibo[n] = 1;
		else {
			return fibo[n] = DFS(n - 2) + DFS(n - 1);
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 10;
		fibo = new int[n + 1];
		DFS(n);
		for (int i = 1; i <= n; i++) {
			System.out.print(fibo[i] + " ");
		}

	}

}

: int형 배열 fibo에 각 리턴값을 저장하여 (수열의 값), 그 fibo배열 값을 반복문을 이용해 출력하는 방법.

 

 

 

 

<위의 방법을 메모이제이션(Memoization)을 통해 더 개선시킨 방법>

public class Main {

	static int[] fibo;

	public static int DFS(int n) {
		if (fibo[n] > 0) //값을 구해놨다면
			return fibo[n];
		if (n == 1)
			return fibo[n] = 1;
		else if (n == 2)
			return fibo[n] = 1;
		else {
			return fibo[n] = DFS(n - 2) + DFS(n - 1);
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 10;
		fibo = new int[n + 1];
		DFS(n);
		for (int i = 1; i <= n; i++) {
			System.out.print(fibo[i] + " ");
		}

	}

}

:  재귀를 통해 fibo배열에 저장된 return값은 또 다시 재귀호출을 통해 구하지 않도록 한다.

 

 

 

밑의 그림 10은 DFS(10)을 의미한다고 생각한다. (D(9), D(8), D(7) ..)

 

즉 그림의 회색 DFS값은 재귀를 통해 구해진 fibo값으로 리턴되는 것이다.

 

 

 

결론적으로 피보나치 수열을 구하는 방법은

1. 재귀

2. 배열 for문 

이 두 가지 방법이 있지만 재귀는 스택프레임을 사용하기 때문에 메모리도 많이 쓰고 더 무겁다.

그래서 성능은 main에서 for문만 도는 배열이 훨씬 좋다.