Hệ số nhị thức sử dụng Đệ quy đệ quy trong LISP

Question

Tôi muốn lập trình hàm để tìm C (n, k) sử dụng đệ quy đuôi, và tôi sẽ đánh giá rất cao sự giúp đỡ của bạn.

tôi đã đạt đến điều này:

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

Sử dụng the following property of the binomial coefficients.

Nhưng tôi không biết làm thế nào để thực hiện cuộc gọi đệ quy là lệnh cuối cùng được thực hiện bởi mỗi trường hợp, vì đó là lệnh cuối cùng là sản phẩm. Tôi đã thử nó bằng cách sử dụng một chức năng phụ trợ, mà tôi nghĩ là cách duy nhất, nhưng tôi đã không tìm thấy một giải pháp.

Answer 1

Như starblue cho thấy, sử dụng một chức năng phụ trợ đệ quy:

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

Hoặc, cung cấp cho các chức năng chính một cuộc tranh cãi optional ắc với một giá trị mặc định là 1 (trường hợp cơ sở đệ quy):

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

Tùy chọn thứ hai hơi kém hiệu quả, vì điều kiện lỗi được kiểm tra trong mọi cuộc gọi đệ quy.

Answer 2

Bạn cần một hàm phụ trợ với đối số thừa, mà bạn sử dụng để tính toán và chuyển kết quả.