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

または、メイン関数にオプションのaccumulator 引数をデフォルト値 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

結果を計算して渡すために使用する追加の引数を持つ補助関数が必要です。