안녕하세요. 휴먼스케이프 ted 입니다.
오늘은 함수형 프로그래밍의 꽃이라고 할 수 있는 재귀에 대해서 더 공부해 볼 것입니다.
책의 내용을 해보면서 수정을 했기 때문에 조금씩 다를 수 있으니 참고해주세요.
3.4 메모이제이션(memoization)으로 성능 개선하기
메모이제이션은 어떤 반복된 연산을 수행할 때 이전에 계산했던 값을 캐싱해서 중복된 연산을 제거하는 방법입니다. 이전 결과 값을 사용해서 연산을 줄이는 부분은 DP(동적 계획법)에서의 핵심이기도 합니다.
흔한 피보나치 수열의 재귀판
이걸 실행하면 총 24번 호출됩니다. 시간복잡도가 O(2^N) 이므로 n이 100만 되어도 어마어마해집니다. 같은 호출도 여러번 하게 되구요.
그럼 메모이제이션을 사용하면 어떻게 될까요?
메모이제이션을 사용한 피보나치 수열 재귀판
동일 연산을 반복하지 않기 때문에 시간 복잡도가 O(N)으로 개선되었습니다.
하지만 이 방법이 함수적(functional)일까요?
순수한 함수의 요건을 다시 생각해 봅시다!
memo라는 변수로 인해 부수효과(side effect)가 발생함
불변성(immutable)을 지키지 못함
따라서 이 해법은 함수적이라고 할 수 없습니다.
메모이제이션을 사용하면서도 부수효과를 없애는 방법은 재귀 함수의 매개변수로 받아서 캐싱을 대신하면 됩니다. 한번 해볼까요?
tailrec이 무엇일까?
여기서 살짝 나온 tailrec 은 메모이제이션하고는 다른 개념이므로 3.5에서 다시 얘기하겠습니다 :)
3.5 꼬리 재귀로 최적화하기
tailrec은 언어 차원에서 제공하는 어노데이션입니다. 꼬리 재귀 조건에 부합하지 않으면 warning이 뜨게 돼요.
꼬리 재귀는 어떤 함수가 직간접적으로 자기 자신을 호출하면서도 그 호출이 마지막 연산(tail call)인 경우를 말합니다.
이렇게 되면 stackoverflow가 나지 않도록 컴파일러가 stack frame을 재 사용(마치 for 같은 반복문처럼) 해줍니다! 이득!!
그렇다면 꼬리재귀를 사용한 예와 반복문을 사용한 경우를 비교해 봅시다.
책에서는 1.0에서 코싸인(cosine) 함수를 수행해서 값이 변하지 않을 때 까지 반복하는 함수를 구현했어요.
(직접 해보셔도 좋아요)
1.0에서 코싸인(cos) 함수를 수행해서 값이 변하지 않을 때 까지 반복하는 함수
머리 재귀(head recursion)와 꼬리 재귀(tail recursion) 비교 하기
위 두 함수는 기능적으로 동일하지만 꼬리재귀는 스택프레임을 재사용하여 최적화가 가능합니다. 함수형 언어를 포함한 대부분의 모던 언어들은 꼬리재귀에 의한 컴파일러 최적화를 지원하므로 가능하면 꼬리재귀로 작성하는 게 좋습니다.
아래 예들을 보면서 꼬리 재귀에 대한 감을 잡아보아요 :)
maximum 함수를 꼬리 재귀로 다시 작성하기
reverse 함수를 꼬리 재귀로 다시 작성하기
take 함수를 꼬리 재귀로 다시 작성하기
zip 함수를 꼬리 재귀로 다시 작성하기
3.6 상호 재귀를 꼬리 재귀로 최적화하기
꼬리 재귀를 이용하면 상호 재귀(mutual recursion)를 최적화 할 수 있습니다.
상호 재귀는 함수 A가 함수 B를 호출하고 함수 B가 다시 함수A를 호출하는 것을 말합니다.
상호재귀
함수형 언어의 컴파일러도 일반적으로는 상호재귀를 최적화 할 수는 없습니다. 이를 위해 상호 꼬리 재귀(mutual tail recursion)로 변경해볼까요~?
트램펄린
상호 꼬리 재귀를 가능하게 하려면 트램펄린(trampoline)을 사용하면 됩니다.
상호 재귀를 그냥 사용하게 되면 stack overflow가 발생하게 되는데요, Bounce라는 클래스를 정의하고 이 클래스를 확장한 Done과 More 클래스를 정의해 보겠습니다.
tailrec으로 선언하여 trampolize 함수는 코틀린 컴파일러에 의해 최적화하게 됩니다.
Bounce를 이용해서 다시 홀/짝을 작성해볼까요?
이렇게 구현함으로써 두개 이상의 상호재귀에서도 꼬리 재귀 최적화를 지원할 수 있게 됩니다 :)
스칼라나 클로저 같은 함수형 언어들은 언어 자체적으로 트램펄린을 위한 타입과 기능을 내장하고 있습니다. 그러나 코틀린은 트램펄린을 위한 재료를 내장하고 있지 않기 때문에 직접 구현하였습니다. 실제로는 프리모나드(free monad)를 사용하여 트램펄린 자체를 하나의 타입으로 추상화하여 사용하기 도 합니다.
이상으로 fp 에서 중요한 꼬리재귀에 대해서 함께 공부해보았습니다.
궁금한점 있으시면 댓글 부탁드리겠습니다. 감사합니다!
가입하기
