Clojureメモ: 再帰を使うとか使わないとか

再帰呼び出し。 練習がてら下記のような関数を作ってみる。

(myfunc 5 [])
=> [1 2 3 4 5]

考え方としては、

(myfunc 5, [])
  -> (myfunc 4, [5])
     -> (myfunc 3, [4 5])
        -> (myfunc 2, [3 4 5])
           ...
           -> (myfunc 0, [1 2 3 4 5])
                => 最後に[1 2 3 4 5]を返す

実装すると以下のようになる。

(defn myfunc [n coll]
  (if (<= n 0)
    coll
    (myfunc (dec n) (cons n coll))))

t-recur-func.core=> (myfunc 5 [])
(1 2 3 4 5)

これは、引数にコレクション（ベクター）を渡してしまうが、 コレクションを渡さない以下のやり方も考えられる。

(defn myfunc2 [n]
  (if (<= n 1)
    [n]
    (conj (myfunc2 (dec n)) n)))

t-recur-func.core=> (myfunc2 5)
[1 2 3 4 5]

こっちは、呼び出した関数の返り値を、どんどんくっつけていくパターン。

どちらかというと、個人的にはこちらの方が実装のイメージがしやすかった。

ただし、こちらの方が末尾再帰ではないので、(recur ..)に置き換えることができず最適化できない。 （再帰呼び出しの回数が多いとスタックオーバーフローを起こす）

とはいえ、このパターンでフィボナッチ数列を求めることもできる。

(defn fib [a b n]
    (if (<= n 1)
      [a] 
      (cons a (fib b (+ a b) (dec n)))))

t-recur-func.core=> (fib 0 1 7)
(0 1 1 2 3 5 8)

てな感じだが、 最後の一行がごちゃごちゃしてて、あまり分かりやすくない…。

フィボナッチ数列の求め方は、Clojure的にはやはり、再帰を使わないやり方がエレガント。 以下のような感じ。

(defn fib2 [n]
  (letfn [(_fb [[a b]]
            [b (+ a b)])]
    (take n
        (map first (iterate _fb [0 1])))))

t-recur-func.core=> (fib2 8)
(0 1 1 2 3 5 8 13)

これは「プログラミングClojure」に載っていた解法。 （ポイントを思い出して書いたので、そのままではない）

一旦、

([0 1] [1 1] [1 2] [2 3] [3 5]...)

のシーケンスを求めといて、 それぞれの最初の要素を取り出してしまう。という考え方。

まあ、mapとかiterateとかの仕様を知らないと読めないのだが。 でも、Clojureのレバレッジを最大に生かすこの解法には膝を打ったな。