Binomialkoeffizient mit Tail Rekursion in LISP

Question

Ich möchte eine Funktion zu C (n, k) mit Tail-Rekursion zu finden, und ich würde Ihre Hilfe sehr zu schätzen wissen.

Ich habe dies erreicht:

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

Mit the following property of the binomial coefficients.

Aber ich weiß nicht, wie man den rekursiven Aufruf zum letzten Befehl macht, der von jeder Instanz ausgeführt wird, da dort das letzte das Produkt ist. Ich habe es versucht, indem ich eine Hilfsfunktion verwendet habe, was meiner Meinung nach der einzige Weg ist, aber ich habe keine Lösung gefunden.

Answer 1

Wie Starblue vermuten läßt, verwenden, um eine rekursive Hilfsfunktion:

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

Oder gibt der Hauptfunktion ein optional Akkumulator Argument mit einem Standardwert von 1 (der rekursive Basisfall):

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

Die letztere Option ist etwas weniger effizient, da die Fehlerbedingung in jedem rekursiven Aufruf überprüft wird.

Answer 2

Sie benötigen eine Hilfsfunktion mit einem zusätzlichen Argument, das Sie zum Berechnen und Übergeben des Ergebnisses verwenden.