第2種スターリング数とフィボナッチ数

第2種スターリング数を求める関数を書いていた。

;n<20程度にする
(defun stirling-2nd-kind (n k)
  (cond ((= n k) 1)
        ((zerop k) 0)
        ((< n k) 0)
        (t (+ (stirling (1- n) (1- k))
              (* k (stirling (1- n) k))))))

これだと，多重再帰となって非常に計算が遅いので，せいぜいn=20を超えるくらいまでしか計算できない。そこで，再帰のない形にできないかと思い，フィボナッチ数が似ているなと思って検索したら，Common Lispの色々なループ - ありの日記を見つけた。コメント欄が興味深かったので，丸写しみたいなものだがフィボナッチ数について書いてみる。

;n<20程度にする
(defun fib (n)
  (cond ((< n 1) 0)
        ((= n 1) 1)
        (t (+ (fib (1- n)) (fib (- n 2))))))

;nにあまり大きい数値を入れない
(defun fib1 (n)
  (labels ((iter (m a b)
             (if (= m n)
                 a
               (iter (1+ m) b (+ a b)))))
    (if (< n 1) 0 (iter 1 1 1))))

(defun fib2 (n)
  (do ((i 0 (1+ i))
       (a 0 b)
       (b 1 (+ a b)))
      ((<= n i) a)))

fibはほぼ定義通りで，nが負数を入れると止まるのを防ぐように直してあるだけである。これは多重再帰なので非常に遅い。そこで，末尾再帰になるようにfib1のように書きなおすわけだが，何か回りくどいやり方をしているように見える。一番効率的なのがループ関数を使う方法で，これがfib2になる。特にdoは美しく書くことができ，数列計算程度では内部式を書く必要すらない！　というところに感銘を受けた次第である。

下の２つはフィボナッチ数の小さい方から順に数えているから，計算結果を順次用いることができるわけだ。第2種スターリング数も，２次元の表を作る必要があるが，同様の計算をすることができるだろう。今は時間が無いので，後で書くか調べることにする。