Fibonacci Sequence – 4Clojure #26

http://www.4clojure.com/problem/26

Difficulty:    Easy
Topics:    Fibonacci seqs

Write a function which returns the first X fibonacci numbers.

test not run (= (__ 3) ‘(1 1 2))
test not run (= (__ 6) ‘(1 1 2 3 5 8))
test not run (= (__ 8) ‘(1 1 2 3 5 8 13 21))

 

분명 난이도가 ‘쉬움 (Easy)’인데.. 아직까지도 사고의 전환이 잘 안되어서인지 몰라도 그리 쉽게 풀리지 않았다..

일단 나는 이렇게 풀었다.

(fn [n] (nth (iterate #(conj % (apply + (take-last 2 %))) [1]) (dec n)))

아이디어는 다음과 같다.

  1. 벡터에서 마지막 두 숫자를 잡아서 더하고 기존 벡터에 이어붙이는(conj) 함수를 만들자.
    #(conj % (apply + (take-last 2 %)))
  2. 1번의 과정은 [1] 에서 시작하도록 하되, 한 번 수행한 결과를 다시 그 함수에 집어넣자.
    (iterate (1번결과함수) [1])
  3. 2번의 수행 횟수를 지정하기 위해 다시 함수로 감싸자 (수행 횟수는 이미 [1]로 시작하므로 1회 줄여서 입력)
    (fn [n] (nth (2번결과함수) [dec n]))

처음에는 iterate 함수의 존재를 몰랐기 때문에 2번 과정에서 시간이 많이 걸렸다. reduce 의 경우 아이템 갯수가 정해진 벡터내에서 동작하므로 이 문제를 해결하려면 재귀함수를 별도로 만들어 적용해야할 것 같은데, 더 간단한 방법이 있지 않을까 꽤나 고민을 하다가  iterate 함수가 정확히 그런 용도로 사용되는 것을 발견했다 (ClojureDocs – iterate).

다음으로,  iterate 적용 후에 3번을 수행하는 과정에서도 #(func %) 과 같은 방식의 익명함수를 시도했는데(코드를 조금이라도 더 줄이기 위해), 에러가 나서 실행을 할 수가 없었다.  iterate 에 입력되는 함수에서 인자(%)를 받고 있기는 하지만 이미  iterate 자체가 콜렉션을 리턴하므로 바깥쪽에서 감싸더라도 문제가 없을 것이라 생각했는데 에러가 발생해서 결국 3번과 같은 방식으로 감싸야 했다 (이유는 정확히 모르겠다).

문제를 풀고나면 확인할 수 있는 다른 사람의 풀이도 살펴보자.

; maximental's solution
(fn [n] 
  (take n
        (map first 
             (iterate (fn [[f s]] [s (+ f s)]) 
                      [1 1]))))

; daowen's solution:
#(take % ((fn fib [x y] (lazy-seq (cons x (fib y (+ x y))))) 1 1))

maximental 의 경우 ClojureDocs의 iterate에 있는 예제와 동일한 방식을 사용한다. 두 숫자를 포함하는 벡터 [f s] 에서 뒷쪽 숫자인  s 와,  f 와  s 를 더한 숫자로 구성된 벡터를 만들어내는 과정을 반복하면서 각 벡터로부터 첫번째 숫자만을 골라낸다 (map first) .

daowen의 경우는 처음에 생각해보려했던 재귀적인 방식을 사용한다. 재귀 아이디어를 제외하면 이 방식에서의 키 팁은  lazy-seq 를 사용하는 것이다. 그냥  seq 를 사용해버리면 재귀호출에 의해 overflow 가 발생해버린다.