対話によるCommon Lisp入門 29 末尾再帰

(defun gcd$ (m n)
  (if (= (mod m n) 0) n
      (gcd$ n (mod m n))))

[1]> (load "gcd.l")
;; Loading file gcd.l ...
;; Loaded file gcd.l
T
[2]> (gcd$ 300 45)
15
[3]> (trace gcd$)
;; Tracing function GCD$.
(GCD$)
[4]> (gcd$ 300 45)
1. Trace: (GCD$ '300 '45)
2. Trace: (GCD$ '45 '30)
3. Trace: (GCD$ '30 '15)
3. Trace: GCD$ ==> 15
2. Trace: GCD$ ==> 15
1. Trace: GCD$ ==> 15
15
[5]> (gcd$ 30 18)
1. Trace: (GCD$ '30 '18)
2. Trace: (GCD$ '18 '12)
3. Trace: (GCD$ '12 '6)
3. Trace: GCD$ ==> 6
2. Trace: GCD$ ==> 6
1. Trace: GCD$ ==> 6
6

値を返す直前の関数呼び出しのことを末尾呼び出しといい、
再帰呼び出しから返されてきた値をそのまま自分の答えとして返すような再帰の方法を末尾再帰という。