C Data Structure - 재귀를 통한 피보나찌 수열 구하기

재귀란 무엇인가?

피보나찌 수열 구하기이다. 재귀로 구해볼 것이다. 재귀는 매우 특이한 방법이 아닐 수 없다.

A라는 함수가 있을 때, A를 열심히 실행하는 도중에! 그것도 A가 미처 다 끝나지도 않은 채로 다시 A를 실행한다. 

이렇게 되면 와 진짜 너무 복잡한데, 또 두 번째 실행된 A안에서 또 A가 호출하면 와 진짜 머리 터진다.

극혐이다.

윤성우 선생님? 강사님? 교수님? 의 자료 구조에서 공부한 파트를 정리하게 되었다.

그냥 재귀를 하면 심심하니까 피보나찌 수열을 통해서 재귀 함수를 작성해보았다. 복잡할 수 있으므로 시간의 흐름에 따라 스텝을 밟을 것이다.

피보나찌 수열의 재귀적 구현

먼저, 다음은 피보나찌 수열이다.

0,   1,   1,   2,   3,   5,   8,   13,   ...

0번째 항과 1번째 항은 무조건, 지구가 멸망하지 않는 이상 0과 1로 각각 주어진다.(멸망하면 수학을 풀 필요가 없다) 그렇다면 2번째 항부터는 어떻구 구하는가?

• 2번째 항을 구하는 방법 : 0번째 항의 값과 1번째 항의 값을 더한다.
• 3번째 항을 구하는 방법 : 1번째 항의 값과 2번째 항의 값을 더한다.
• 4번째 항을 구하는 방법 : 2번째 항의 값과 3번째 항의 값을 더한다. (ㄱ)
• n번째 항을 구하는 방법 : n-2 번째 항의 값과 n-1 번째 항의 값을 더한다. ( 일반화 ) (ㄴ)

일단, (ㄱ) 까지의 상황을 코드로 정리해보겠다.

그렇다. 무식하다. 근데 이게 좀 쩌는 것이 무어냐면 ㅋㅋ,

• Fibonacci(4); 의 결과 : 3
• Fibonacci(3); 의 결과 : 2 
• Fibonacci(2); 의 결과 : 1

함수의 결과가 중요하지 않다. Fibonacci 함수의 본질을 알려준다. Fibonacci 함수의 본질은 다음과 같다.

Fibonacci 함수에 원하는 항의 인덱스 값을 넣으면 해당 인덱스 항의 값을 구해줘요!

이게 진짜 개중요하다. 우리는 앞으로 만들 우리의 Fibonacci 함수를 믿어야 한다. 우리는 Fibonacci 함수의 인자로 원하는 항의 인덱스 값을 넣으면 해당 인덱스 항의 값을 내어준다는 사실을 믿어야한다. 믿음이다. 재귀 함수 루틴이 들어간다고 해서 이러한 사실이 부정인가? 아니다. 

위의 믿음을 가지고 특정 항을 생각해보자. 특정 항은 예를 들어 5번째 항의 값을 구한다고 생각하자.

Fibonacci(5) = Fibonacci(4) + Fibonacci(3);

재귀를 생각하지 말라. 믿음이 있어야한다.
Fibonacci(4)는 4번째 항의 값을 리턴할 것이라는 믿음.
Fibonacci(3)은 3번째 항의 값을 리턴할 것이라는 믿음.

이런 믿음을 바탕으로 (ㄴ)까지의 상황으로 아래와 같이 구현해보았다.

그렇다면, 실제로 어떻게 동작을 해보는지 재귀의 경우를 그려볼까?

 

피보나치 수열의 재귀적 구현의 동작 원리

그만 알아보자