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

发布于 2024-09-30 15:18:46 字数 539 浏览 9 评论 0原文

我想编写一个函数来使用尾递归查找 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)))))

使用二项式系数的以下性质。

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

原文

I want to program a function to find C(n,k) using tail recursion, and I would greatly appreciate your help.

I have reached this:

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

Using the following property of the binomial coefficients.

But I don't know how to make the recursive call to be the last instruction executed by each instance, since there the last one is the product. I have been trying it by using an auxiliary function, which I think is the only way, but I haven't found a solution.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

年少掌心 2024-10-07 15:18:46

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

或者，为主函数提供一个可选累加器参数默认值为 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))))))

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

As starblue suggests, use a recursive auxiliary function:

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

Or, give the main function an optional accumulator argument with a default value of 1 (the recursive base case):

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

The latter option is slightly less efficient, since the error condition is checked in every recursive call.

回复收藏 0 原文