[알고리즘] 피보나치 수열

재귀함수를 공부할 때 반드시 등장하는 수열입니다. 재귀함수의 기본적인 감을 잡는 데에 적절하다고 생각됩니다. 팩토리얼보다는 조금 더 고민해볼 거리가 있습니다. 피보나치 수열의 점화식은 a(n) = a(n-1) + a(n-2)입니다. 이를 그냥 코드로 구현하면 됩니다. 0번째와 1번째 값을 각각 0, 1로 줄 것입니다. 코드는 다음과 같습니다. 점화식은 재귀식이라고도 하는데 수열에서 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식입니다. 

// a(n) = a(n-1) + a(n-2)
int fibonacci(int n)
{
	if (n <= 1) return n;	
	return fibonacci(n - 1) + fibonacci(n - 2);
}

int main()
{
	cout << fibonacci(9) << endl;
}

fibonacci(9)을 호출하면 0부터 시작해서 9번째 항을 구하게 됩니다. return문마다 함수를 두 개씩 호출하는 것이 혼란스럽게 느껴질 수 있습니다. 손으로 직접 그려 보면 이해가 수월할 것입니다. 각 함수의 파라미터인 n은 값 자체가 아니라 n번째의 항을 의미한다는 점을 헷갈리면 안 됩니다. 모든 함수는 a(1) + a(0)을 리턴할 때까지 자신을 호출합니다. 탈출 조건을 만나고 나서야 a(2)을 구하게 되는 것이지요. 다음은 5를 기준해서 작성한 트리입니다. a(0)은 0이고 a(1)은 1이기 때문에 밑에서부터 차례로 올라오면서 각 항의 값을 구합니다. 손으로 직접 그려볼 때 이해가 잘 되는 경우가 있습니다.