지난번 글에서

예전에 C 언어를 처음 배울 때 모든 책마다 재귀 함수에 관한 설명이 빠짐없이 있었던 걸로 기억이 되는데, 왜 이런 이상한 방법을 쓰는지 F#을 배우기 전까지 무려 20년이 넘게 이해를 못했었다.

라고 했었는데, Eloquent JavaScript 책을 읽다가 비슷한 예가 있길래 소개해 본다. 다음과 같은 문제가 주어져 있고 이것을 재귀를 통해 해를 구하는 방법이다.

Consider this puzzle: by starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite set of numbers can be produced. How would you write a function that, given a number, tries to find a sequence of such additions and multiplications that produces that number? For example, the number 13 could be reached by first multiplying by 3 and then adding 5 twice, whereas the number 15 cannot be reached at all.

1부터 시작해서 5를 더하거나 3을 곱해 나가다 보면 무한대의 숫자 집합을 얻을 수 있다. 임의의 숫자가 주어질 때 그 숫자를 만들어 내는 합과 곱의 순서열을 찾아라. 예를 들어 숫자 13은 처음에 3을 곱하고 그 다음 5를 두번 더하면 얻을 수 있다. 그러나 숫자 15는 어떤 방법으로도 얻을 수 없다.

책에 나와 있는 해답은 다음과 같다:

function findSolution(target) {
    function find(current, history) {
        if (current == target) {
            return history;
        } else if (current > target) {
            return null;
        } else {
            return find(current * 3, `(${history} * 3)`) ||
                   find(current + 5, `(${history} + 5)`);
        }
    }
    return find(1, "1");
}

console.log(findSolution(24));
// (((1 * 3) + 5) * 3)

같은 문제를 F#으로 풀어 보았다:

let mul3 = "* 3"
let add5 = "+ 5"

let findSolution target =
    let rec find acc =
        acc
        |> List.collect (fun (current, history) ->
            match current * 3 <= target, current + 5 <= target with
            | true,  true  -> find [current * 3, mul3 :: history
                                    current + 5, add5 :: history]
            | true,  false -> find [current * 3, mul3 :: history]
            | false, true  -> find [current + 5, add5 :: history]
            | false, false -> [current, history])

    find [1, []]
    |> List.filter (fst >> ((=) target))
    |> List.map (snd >> List.rev)

findSolution 24
|> List.iter (fun sol ->
    printfn "%s" (("1", sol) ||> List.fold (sprintf "(%s %s)")))

이렇게 하고 나면 실제로는 해가 2개 나온다:

(((((1 * 3) * 3) + 5) + 5) + 5)
(((1 * 3) + 5) * 3)

교훈

여기서 중요한 점은 재귀 함수는 함수형 프로그래밍의 기본 연산(filter, map, collect, fold, …)과 데이터 구조를 이용했을 때 훨씬 쉽고 올바르게 구현할 수 있다는 것이다. 두 코드가 거의 동일한 복잡도를 가졌음에도 불구하고 F# 버전의 경우 List 타입과 List.collect 함수를 이용함으로써 완전해를 구할 수 있었지만, 순전히 제어문에만 의존한 자바스크립트 버전은 부분해 밖에 구하지 못했다. 이렇게 부분해를 구하게 되면 단점이 있는데, 특히 이 버전의 심각한 문제는 결과가 실행 순서에 의존한다는 것이다. 위의 코드에서

            return find(current + 5, `(${history} + 5)`) ||
                   find(current * 3, `(${history} * 3)`);

부분을

            return find(current * 3, `(${history} * 3)`) ||
                   find(current + 5, `(${history} + 5)`);

로 순서를 바꾸기만 해도 결과가 완전히 달라진다. 거기다 더 문제는 결과 자체를 예측할 수 없다는 것인데, 결과로 얻은 수식은 가장 짧은 것도 아니고 가장 긴 것도 아니고 단지 재귀를 반복적으로 하다가 가장 먼저 찾아낸 해에 불과하다. 이렇게 결과를 예측할 수 없는 코드는 테스트도 불가능하고 무엇보다 버그의 온상이 되기 쉽다.

그래서 만약 문제의 조건이 “얻을 수 있는 순서열을 모두 구하라”였거나 “얻을 수 있는 순서열중 가장 긴/짧은 것을 구하라”였다면 이를 충족시키지 못해 코드를 새로 짜야 한다. 따라서 실제로는 아무도 이렇게 재귀 함수를 만들거나 쓰지 않는다. 책의 의도와 반대로 재귀 함수를 쓰지 말아야 하는 좋은 이유가 된 것 같다. 😫

결과적으로 함수형 프로그래밍을 다루는 책이 아니라면 굳이 재귀 함수를 소개해서 독자를 헷갈리게 만들지 말아야겠다.