피보나치 수열의 일반항을 꼬리재귀로 만들기

Swift는 꼬리재귀 최적화를 지원하지만, ARC에 의해 코드가 변경되면서 꼬리재귀 형태가 아닌 것으로 바뀌고 따라서 꼬리 재귀 최적화의 지원을 못받는 경우가 생길 수 있다. 따라서 트램폴린 패턴을 이용하여 스택 깊이의 제한을 받지 않고 꼬리재귀를 수동으로 최적화하는 방법에 대해서 알아본다.

오일러 프로젝트 25

오일러 프로젝트 25 번은 1000자리 이상이 되는 수가 피보나치 수열의 몇 번째 항에서 처음 나타나는 가를 묻는 문제이다. 피보나치 수열은 아래와 같은 점화식으로 정의됩니다. Fn = Fn-1 + Fn-2 (단, F1 = 1, F2 = 1). 이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다. F1 = 1 F2 = 1 F3 = 2 F4

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

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