在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))))) 

使用the following property of the binomial coefficients。

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

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))))) 

或者，给主函数的optional累加器参数为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)))))) 

后一个选项的效率稍低，因为在每次递归调用中检查错误条件。

Answer 2

您需要一个带有额外参数的辅助函数，用于计算并传递结果。