백준알고리즘_10870_재귀함수_피보나치수열 (C언어)

자바 공부하다가 머리가 아파서 잠시 머리도 식힐겸 알고리즘으로 돌아와서 C를.. 자바의 객체 개념은 정말 어렵네요. 외울 것도 많고..

​

재귀함수 버전 피보나치 수열은 재귀함수 입문용인데 의외로 인터넷 보면 어마어마한 성능을 요구하는 재귀함수를 정답이라고 올려두신 분들이 많은 듯 합니다..

 

 

 

---

 

기본적으로 피보나치 수열 공식이 "f(n) = f(n-1) + f(n-2)" 이라고 아래와 같이 그대로 재귀함수 코드를 짰다가는 컴퓨터한테 혼납니다. 컴퓨터 성능에 따라 다르겠지만 대략 제 컴퓨터에서는 35이상 넘어가면 연산 시간이 1초를 넘어가네요.

#include <stdio.h>
int pivo(int num);

int main()
{
	int num;
	scanf("%d", &num);
	printf("%d", pivo(num + 1));

	return 0;
}

/* 피보나치 수열 */
int pivo(int num)
{
	int result;
	if (num <= 1)
		return 0;
	
	else if (num == 2)
		return 1;

	return pivo(num - 1) + pivo(num - 2);
}

 

---

 

이유는 간단합니다. f(100)을 구하기 위해서는 f(99)와 f(98)을 구해야하는데 f(99)를 구하기 위해서는 f(98)과 f(97)을 구해야하고 f(98)을 구하기 위해서는 f(97)과 f(96)을 구해야합니다. 즉, f(99)를 구하기 위한 함수와 f(98)을 구하기 위한 함수가 또 다시 각각 실행됩니다. 메소드(함수) 하나를 실행할때마다 스택프레임이 새로 생성됩니다. 첫 번째 메소드에서 스택프레임 하나, 거기서 두 개가 또 실행되니 스택프레임 2개, 그 다음은 4개..... 로 2제곱으로 늘어납니다. 엄청난 중복 연산이 발생하게 되는거죠.

​

만약 f(n) = f(n-1) 이라는 공식이라면 별 문제가 없습니다. 1의 제곱으로 분화하면 더하기나 마찬가지니까요. 하지만 재귀함수가 두 개로 분화하게 된다면 처음에는 2개, 2개가 다시 4개로, 2의 제곱수만큼 분화하면서 뻗어나갑니다. 당연히 숫자가 커질 수록 연산 횟수가 기하급수적으로 늘어나게 됩니다.

 

---

 

이 경우 사용하는 방식이 다이나믹 프로그래밍 기법입니다. 한 번 연산한 값은 저장해두고 중복연산하지 않도록 설계한다는 의미입니다. f(n -2)의 값과 f(n - 1)의 값을 저장해두고 다음 함수에서 가져다 쓴다면 중복 연산을 피할 수 있습니다. 아래는 백준 알고리즘 문제 제출용 코드이며, num값이 그대로 쓰이지 않고 +1, -1이 되는 이유는 문제가 0번째부터 시작하는 피보나치 수열이기 때문입니다. 원래 1로 시작하는 피보나치 수열이면 굳이 저렇게 작성할 필요는 없습니다.

 

※Point
재귀 함수 사용 시에는 재귀 함수가 하나만 수행되도록 해야 한다. 2개 이상 재귀함수가 발생할 경우 계속 분화해 나가기 때문에 성능 상 이슈가 발생한다. 2개 이상의 재귀함수를 사용해야할 경우 적절한 탈출문을 사용해서 무한정 분화되지 않고 한 두 단계 실행 후 리턴될 수 있도록 해줘야 한다.

[ 잘못된 예시 - 2개 이상의 재귀함수가 동시에 사용됨 ]
함수(int n) {
     재귀함수사용(n-1)
     재귀함수사용(n-2)
}

[ 바른 예시 - 하나의 재귀함수만 사용됨 ]
함수(int n) {
     if (조건) 재귀함수사용(n-1)
     else 재귀함수사용(n+1)
}

 

#include <stdio.h>
int pivo(int num, int* temp);

int main()
{
	int temp[2] = { 0,1 };
	int num;
	scanf("%d", &num);

	// 제출용코드
	//if (num < 0 || num - 1 >= 20)
	//	return 1;

	printf("%d", pivo(num + 1, temp));

	return 0;
}

/* 피보나치 수열 */
int pivo(int num, int* temp)
{
	int result;
	if (num <= 1)
		return temp[0];

	else if (num == 2)
		return temp[1];

	else {
		pivo(num - 1, temp);
		result = temp[0] + temp[1];
		temp[0] = temp[1];
		temp[1] = result;
	}
	return result;
}