Coefficiente binomiale con ricorsione della coda in LISP

Question

Desidero programmare una funzione per trovare C (n, k) utilizzando la ricorsione della coda e apprezzerei molto il vostro aiuto.

ho raggiunto questo:

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

Utilizzando the following property of the binomial coefficients.

Ma non so come rendere la chiamata ricorsiva come l'ultima istruzione eseguita da ogni istanza, poiché l'ultimo è il prodotto. L'ho provato utilizzando una funzione ausiliaria, che a mio avviso è l'unico modo, ma non ho trovato una soluzione.

Answer 1

Come starblue suggerisce, utilizzare una funzione ausiliaria ricorsiva:

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

Oppure, per dare la funzione principale argomento optional accumulatore con un valore predefinito di 1 (il caso base ricorsivo):

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

Quest'ultima opzione è leggermente meno efficiente, poiché la condizione di errore viene verificata in ogni chiamata ricorsiva.

Answer 2

È necessaria una funzione ausiliaria con un argomento aggiuntivo, che si utilizza per calcolare e trasmettere il risultato.