友人から「関数型でフィボナッチ数列を計算する課題が出たんだけど,どうするの?」という話がきたので解説.

課題はRacketでFor文とか、手続きっぽいのを使っちゃいけないらしい. Racketは書けないし海外の方なので説明も手間取った.

今回はCommon Lispで解説します.

課題は再帰処理でフィボナッチ数列を計算しているものを高速化して. みたいなやつでした.

こんな感じの関数を高速化するみたいですね.

(defun fib (i)
  (if (<= i 1)
      i
      (+ (fib (- i 1)) (fib (- i 2)))))

これだと何度も数列を求めているので時間がめっちゃかかりました.

* (time (fib 42))

Evaluation took:
  5.647 seconds of real time
  5.646444 seconds of total run time (5.646434 user, 0.000010 system)
  99.98% CPU
  11,247,894,108 processor cycles
  0 bytes consed

267914296

時間にして5秒です.

長いです.

サイクルしまくってますね.

要するに順番に数えて足していけばいいわけでしょ?

ただし,for文は使えない. helper関数を作ってぶん回すことを提案しました.

(defun fib (i)
  (if (<= i 1)
      i
      (fib-helper (- i 1) 0 1)))

(defun fib-helper (i nminus1 nminus2)
  (if (eq i 0)
      (+ nminus1 nminus2)
      (fib-helper (- i 1) (+ nminus1 nminus2) nminus1)))
* (time (fib 42))

Evaluation took:
  0.000 seconds of real time
  0.000006 seconds of total run time (0.000006 user, 0.000000 system)
  100.00% CPU
  5,516 processor cycles
  0 bytes consed

267914296

こうして無事に関数型っぽく,高速化できましたね.