콘텐츠로 건너뛰기
Home » 피보나치 수열

피보나치 수열

꼬리재귀와 트램폴린

꼬리 재귀(tail recursion)는 함수가 내부에서 자신을 재귀 호출할 때, 재귀 호출한 결과를 그대로 리턴하는 모양을 만드는 것이다. 이는 return 구문의 모양에 의해서 쉽게 판별할 수 있고, 재귀 호출의 결과 값에 대해서 추가적인 처리를 하지 않기 때문에 컴파일러가 쉽게 최적화할 후 있다. 재귀 호출의 결과를 그대로 사용한다는 것은, 재귀 호출을 수행하는 시점에 함수 내부의 지역 변수를 더 이상 사용하지 않는 것을 의미하므로 함수 호출에 의한 새로운 스택 프레임을 생성하는 대신, 현재 스택 프레임을 재활용할 수 있다. 따라서 꼬리 재귀는 반복 연산의 모양으로 변환이 가능하며, 이 과정은 기계적으로 처리될 수 있다.

꼬리 재귀는 컴파일러가 꼬리재귀 최적화를 지원하지 않는다면, 재귀 깊이에 한계가 있다는 단점이 있다. 따라서 재귀 호출 자체를 직접적인 반복문으로 변경할 수 있도록 재귀 호출을 수행할 함수를 리턴하는 것으로 스택 오버플로우를 회피할 수 있다.

더 보기 »꼬리재귀와 트램폴린

오일러 프로젝트 25

오일러 프로젝트 25 번은 1000자리 이상이 되는 수가 피보나치 수열의 몇 번째 항에서 처음 나타나는 가를 묻는 문제이다. 피보나치 수열은 아래와 같은 점화식으로 정의됩니다. Fn = Fn-1 + Fn-2 (단, F1 = 1, F2 = 1). 이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다. F1 = 1 F2 = 1 F3 = 2 F4 = 3 F5 = 5 F6 = 8 F7 = 13 F8 = 21 F9 = 34 F10 = 55 F11 = 89 F12 =… 더 보기 »오일러 프로젝트 25

재귀호출과 피보나치 수열 탐구

재귀호출은 함수가 그 내부에서 자신을 다시 호출하는 것이다. 이는 언뜻 이상하게 보일 수 있고, 경우에 따라서는 의도치 않은 동작을 하게 할 수 있어서 일반적으로는 지양되는 방법이기는 하나, 대신에 코드가 짧아질 수 있고 실행 로직 자체가 어느 정도 제한된 경우라면 충분히 사용할 수 있다. 특히 하스켈과 같은 함수형 언어에서는 반복문을 돌리는 로직이 없기 때문에 재귀호출을 하는 함수를 자주 사용하게 된다. 더 보기 »재귀호출과 피보나치 수열 탐구