Биномиальный коэффициент с использованием рекурсии хвоста в 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)))))

Использование следующего свойства биномиальных коэффициентов .

Но я не знаю, как сделать рекурсивный вызов последней инструкцией, выполняемой каждым экземпляром, поскольку последняя является продуктом. Я пробовал это с помощью вспомогательной функции, которая, я думаю, является единственным способом, но я не нашел решения.

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

Или задайте основной функции необязательный аргумент-накопитель со значением по умолчанию 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

Вам нужна вспомогательная функция с дополнительным аргументом, которую вы используете для вычисления и передачи результата.