JS에서 꼬리재귀 최적화하기

함수형 프로그래밍에서 반복문 대신 재귀를 쓸 때, 꼬리재귀 최적화가 없다면 메모리나 속도가 망하기 쉽다. 재귀 깊이 제한이 있다면 함수가 뻥뻥 터지기도 한다. 반복문으로 바꾸면 된다지만 썩 맘에 들지 않는 건 어쩔 수 없다.

함수형을 맛보기 좋은 걸로 알려진 JS에(정확히는 가장 널리 쓰이는 JS 엔진인 V8에) 이런 꼬리재귀 최적화가 없다는 건 상당히 이율배반적인 소리로 들린다. 때문에, 적절한 규격을 가진 재귀함수를 내부적으로 반복문처럼 처리하는 유틸리티 함수를 만들어볼 수 있다.

목표는 T(self => (n, acc = 0) => (n ? self(n - 1, acc + n) : acc))(100000000)을 했을 때 콜스택이 터지지 않고 잘 돌아가도록 T 함수를 만드는 것이다.

const T = f => (...args) => {
    let end = true;
    const g = f((...newArgs) => {
        args = newArgs;
        end = false;
    });
    while (true) {
        const ret = g(...args);
        if (end) return ret;
        end = true;
    }
};

T(self => (n, acc = 0) => (n ? self(n - 1, acc + n) : acc))(100000000)

f에 함수 호출 여부와 다음에 쓸 인자를 확인하는 함수를 끼워넣어 준다. 이후 함수 호출이 멈출 때까지, 즉 재귀가 멈출 때까지 직전에 받은 인자를 넣어주며 반복한다.

기능적으로는 콜스택이 깊어지는 게 방지돼서 터질 일은 줄어들지만, 속도는 오히려 일반 꼬리재귀함수에 비해서도 10% ~ 20%정도 느리다.

아래처럼 spread 연산을 없애고 인자를 객체를 넘기는 방식으로 하면 일반 재귀에 비해 5배쯤 빠르긴 하지만, 여전히 반복문에 비해 5배쯤 느리다.

const T = f => (args) => {
    let end = true;
    const g = f((newArgs) => {
        args = newArgs;
        end = false;
    });
    while (true) {
        const ret = g(args);
        if (end) return ret;
        end = true;
    }
};

T(self => ({ n, acc = 0 }) => (n ? self({ n: n - 1, acc: acc + n }) : acc))({ n: 100000000 })

아쉽긴 하지만 최적화할 여지가 별로 안 보여서 대충 이정도로 마무리하는 걸로...