在LISP中使用尾递归的二项式系数

Question

我想编写一个函数来使用尾递归找到C(n,k),我将非常感谢你的帮助.

我达到了这个:

(defun tail-recursive-binomial (n k)
  (cond ((or (< n k) (< k 0)) NIL)
        ((or (= k 0) (= n k)) 1)
        (T (* (tail-recursive-binomial (- n 1) (- k 1)) (/ n k)))))

使用二项式系数的以下属性.

但我不知道如何使递归调用成为每个实例执行的最后一条指令,因为最后一条指令是产品.我一直在尝试使用辅助功能,我认为这是唯一的方法,但我还没有找到解决方案.

Answer 1

正如starblue建议的那样,使用递归辅助函数:

(defun binom (n k)
  (if (or (< n k) (< k 0))
    NIL  ; there are better ways to handle errors in Lisp
    (binom-r n k 1)))

;; acc is an accumulator variable
(defun binom-r (n k acc)
  (if (or (= k 0) (= n k))
    acc
    (binom-r (- n 1) (- k 1) (* acc (/ n k)))))

或者,为main函数提供一个可选的 accumulator参数,其默认值为1(递归基本情况):

(defun binom (n k &optional (acc 1))
  (cond ((or (< n k) (< k 0)) NIL)
        ((or (= k 0) (= n k)) acc)
        (T (binom (- n 1) (- k 1) (* acc (/ n k))))))

后一种选择的效率略低,因为在每次递归调用中都会检查错误条件.