함수형 프로그래밍에서는 반복문을 사용하지 않고 재귀 함수로 대체합니다. 하지만 일반 재귀 함수를 사용할 경우 스택오버 플로우(Stack Overflow) 등 여러 비효율적인 문제들이 발생하게 될 수 있습니다. 이러한 문제를 보안하기 위해 다양한 기법들이 재귀 함수를 효율적으로 사용할 수 있도록 도와주고 있습니다.
재귀 함수란?
함수 안에서 동일한 함수를 호출하여 함수 내 로직을 반복하는 형태를 재귀 함수라고 부릅니다. 우리는 재귀 함수를 통하여 for, while 과 같은 반복문들을 대체할 수 있습니다. 함수형 프로그래밍에서는 이러한 반복문 또한 재귀 함수로 정의하여 재사용성을 높일 수 있습니다.
재귀 함수 작성법
재귀 함수를 작성하기 위해서 아래 항목들에 대하여 생각 후 함수를 정의하여야 합니다.
- 함수의 종료 조건 정의
- 재귀 호출을 실행할 위치 결정
- 입력값이 종료 조건으로 사용되도록 재귀 호출의 입력값 정의
일반 재귀 함수의 한계
- 스택
함수는 스택에 할당되기 때문에 재귀 함수가 호출되는 횟수만큼 스택에 쌓이게 됩니다. 그래서 스택이 초과될 경우 스택오버 플로우가 발생하게 됩니다.
- 메모리
함수형 프로그래밍은 블럭 내에 있는 내부 변수만 활용하기 때문에 이전에 반복 실행하면서 연산된 내용을 참조할 수 없습니다.
- 반복적으로 호출되는 함수 실행
반복적으로 번갈아 가며 호출되는 두가지 함수가 있다고 가정할 때 우리는 이 로직을 일반적인 재귀 함수로 구현할 수 없습니다.
위와 같은 문제점들은 성능이나 메모리 관리에 치명적인 약점을 가지고 있습니다. 당연히 위의 문제점들이 해결되지 못했다면 우리는 현재 재귀 함수를 사용할 수 없었겠지요?
1. 꼬리재귀 최적화 (Tail Call Optimization)
재귀 함수는 호출된 횟수만큼 스택에 쌓이게 된다는 치명적인 단점이 있습니다. 이러한 단점을 보완하기 위하여 나온게 꼬리재귀 최적화입니다. 꼬리재귀 최적화는 컴파일러가 컴파일 하는 시점에 스택 프레임을 재사용 할 수 있도록 일반적인 for, while 문과 비슷한 형태로 코드를 변환하는 기법입니다. 이 조건이 성립되려면 함수 내에 재귀 함수가 호출되는 시점이 로직의 마지막 줄이어야 하며 로직의 마지막 줄에 재귀 함수가 호출되는 것이 꼬리재귀 이며 꼬리재귀 최적화를 지원하는 언어에서만 유효하게 사용할 수 있습니다. 그렇기 때문에 함수형 프로그래밍을 도입하기 전 꼬리재귀 최적화를 지원하는지 확인하는 것은 매우 중요합니다. 코틀린의 경우 tailrec 어노테이션을 사용하여 꼬리재귀 최적화를 사용합니다. 만약 규칙에 어긋날 경우 컴파일 단에서 경고가 발생합니다.
위 예제는 count 수 만큼 num을 list에 담아 반환하는 예제입니다.
2. 메모이제이션 (Memoization)
메모이제이션은 재귀 함수 실행 도중 이전 연산된 값을 활용하기 위하여 이전 연산 결과들을 메모리에 저장해 두었다가 같은 연산일 경우 결과값을 빠르게 호출하여(캐싱) 실행하는 코딩 기법을 말합니다. 이전 동일 연산의 결과값을 바로 가져와 사용하기 때문에 동적인 공간 복잡도를 낮추고 시간 복잡도를 낮출 수 있습니다.
위 소스를 보면 cache 변수에 메모리 공간을 미리 할당하여 캐싱할 데이터를 담을 수 있도록 준비하는 것을 볼 수 있다. 한번 연산된 값은 cache 변수에 담고 재귀 호출이 일어날 때마다 cache에 값이 있는지 확인하고 있을 경우 연산을 진행하지 않고 바로 결과값을 받아올 것이다. 하지만 cache는 외부 변수이기 때문에 위 예제는 순수 함수에 어긋난다. 위 함수를 보완하여 순수 함수 규칙을 유지한 예는 아래와 같다.
이전 연산 결과값을 매개 변수로 넘겨주어 다음 연산에서 사용하는 형태로 구현할 수 있습니다.
3. 트램펄린 (Trampoline)
두 함수가 반복적으로 실행되어야 할 경우 상호 꼬리재귀가 가능하게 하기 위하여 트램펄린을 사용합니다. 먼저 실행되어야 할 두 함수에 마지막 라인에 각각 다음 실행되어야 할 함수를 호출하도록 정의합니다. 또한 각각의 함수에 종료 조건을 정의합니다. 트램펄린은 기본적으로 순수 함수의 특성을 잘 이용한 디자인 패턴이라고 볼 수 있습니다. 부가적인 텍스트 설명보다 예시 코드를 이용하여 설명드리겠습니다.
짝수 / 홀수 여부를 반환하는 두 함수를 상호 꼬리재귀 형태로 구현한 예제입니다. 물론 O(1) 의 시간복잡도가 걸리는 간단한 방법이 있으나 설명을 위해 위와 같이 구현하였습니다.
odd, even 함수 각각 종료 조건과 실행 로직을 구현하였으며 odd 함수는 마지막 부분에 even 함수를 even 함수는 odd 함수를 호출하도록 구현하였습니다. 그리고 이를 More의 매개변수로 실행하도록 구현하여 우리는 trampoline 함수의 매개변수로 넘겨줘 trampoline 함수가 실행되도록 하였고 trampoline 함수는 내부적으로 꼬리재귀 최적화가 가능한 함수로 구현되어 있어 odd와 even이 번갈아가며 꼬리재귀 조건을 충족하며 실행할 수 있게 되었습니다. 이러한 형태로 상호 꼬리재귀를 구현할 수 있습니다.
Conclusions
이번 장에서는 함수형 프로그래밍에서 재귀 함수를 사용하는 방법과 재귀 함수의 특징 및 단점 -> 단점을 보완하는 여러 기법들에 대해 소개하는 시간을 가졌습니다. 일반적인 재귀 함수만으로 실무에 적용하기는 어려우며 이를 보완하기 위한 여러 기법들을 사용하여 효율적인 함수형 프로그래밍을 할 수 있습니다. 하지만 우리는 이러한 도구를 사용하기 위해 익혀야 할 기법들이 많은것도 사실인데요. 대신 이러한 기법들을 익히고 연습하다 보면 기존 명령형 프로그래밍 방식보다 더 간결하고 확장성이 넓고 안전한 코드를 얻을 수 있게됩니다.
