末尾再帰

末尾再帰をやってみる。

(defun my-fact (n)              ; 普通の再帰
  (if (= n 0) 1
    (* n (my-fact (1- n)))))
      ↓
(defun my-fact (n)              ; 末尾再帰
  (my-fact-loop n 1 1))

(defun my-fact-loop (n i p)
  (if (> i n) p
    (my-fact-loop n (1+ i) (* i p))))

;; test
(trace my-fact)
(trace my-fact-loop)

(my-fact 3)
 Calling (my-fact-loop 3 1 1)
  Calling (my-fact-loop 3 2 1)
   Calling (my-fact-loop 3 3 2)
    Calling (my-fact-loop 3 4 6)
    my-fact-loop returned 6       ; 一番奥で求めた値を持って帰るだけなので、
   my-fact-loop returned 6        ; ちゃんと末尾再帰になってる
  my-fact-loop returned 6
 my-fact-loop returned 6
6

うまくいっているようだが、やってることがさっぱりわからん。
末尾再帰になるように、補助関数を用意するのは分かる。
でもその引数をどうやって決めるのかとか、終了条件とかそのとき返す値の決め方がさっぱりだ。意味わからん。

---

なるべく再帰にしたいということは、なんとなく分かる。

再帰で書くと、ループで書いたものより、なにをやってるかがわかりやすいぞ
　　↓
じゃあ、再帰で書いてみよう
　　↓
とくに末尾再帰にすると、ループ処理に展開されるから早くなるし、スタック使わないからエレガントだ
　　↓
じゃあ、末尾再帰にしてみよう

という流れは分かるんだが･･･。

まあ、どうせ xyzzy には末尾再帰の最適化がないらしいので書けなくてもいいか。
と今は逃げておく。