対話によるCommon Lisp入門 28 再帰

;; m to the Nth power
(defun expt$ (m n)
  (if (= n 0) 1
      (* (expt$ m (- n 1)) m)))

;; number of k-combinations
(defun C (n k)
  (if (= k 0) 1
      (* (/ n k) (C (- n 1) (- k 1)))))

;; number of k-combinations 2
(defun C2 (n k)
  (if (= k 0) 1
      (if (= n k) 1
          (+ (C (- n 1) (- k 1))
             (C (- n 1) k)))))

結果

[28]> (expt$ 3 10)
59049
[29]> (expt$ 2 10)
1024
[30]> (C 10 3)
120
[31]> (C2 10 3)
120

なお、2回呼び出す回帰は二重回帰という。