Coeficiente binomial usando recursividad de cola en LISP

Question

Quiero programar una función para encontrar C (n, k) utilizando recursividad de cola, y agradecería mucho su ayuda.

he llegado a esto:

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

Usando the following property of the binomial coefficients.

Pero no sé cómo hacer que la llamada recursiva sea la última instrucción ejecutada por cada instancia, ya que allí la última es el producto. Lo he intentado usando una función auxiliar, que creo que es la única, pero no he encontrado una solución.

Answer 1

Como starblue sugiere, utilizar una función auxiliar recursiva:

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

O, dar la función principal un argumento optional acumulador con un valor predeterminado de 1 (el caso base recursiva):

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

La última opción es ligeramente menos eficiente, ya que la condición de error está marcada en cada llamada recursiva.

Answer 2

Necesita una función auxiliar con un argumento adicional, que se usa para calcular y pasar el resultado.