在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

您需要一個帶有額外參數的輔助函數，用於計算並傳遞結果。