먼저 재귀 함수의 대표명사인 피보나치 함수를 람다로 만들어 봅시다.
uint64의 최댓값을 넘어가지 않으면서 계산할 수 있는 최대 피보나치 숫자는 93번째까지 입니다.
무려 20자리나 됩니다ㄷㄷ (12,200,160,415,121,876,738)
이 숫자를 계산하려고 재귀함수를 열심히 돌리다보면 당연히 에러가 발생하죠
참고로 c++17 부터는 람다가 constexpr function의 조건을 만족하면 굳이 키워드를 붙이지 않아도 암시적으로 constexpr 람다가 됩니다.
개꿀ㅎㅎ
여기에 꼬리 재귀(tail recursion) 방식을 적용하면 스택을 훨씬 적게 쓰면서 값을 얻어낼 수 있습니다.
코드로 보면 더 심플합니다.
이전값과 이전이전값ㅋㅋ이 인자로 들어갔네요
이 방식대로면 재귀적으로 n번 호출하니까 스택에도 n번만 쌓이게 됩니다.
그리고 함수 내부에 하나의 재귀함수만 있고 마지막에 호출되는 경우에는 컴파일러가 최적화를 수행하면서 스택을 재사용한다고도 하네요ㄷㄷ 너무개꿀
오늘도 하나 배워갑니다.
댓글 0