末尾再帰

末尾再帰をやってみる。

(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 には末尾再帰の最適化がないらしいので書けなくてもいいか。

と今は逃げておく。