末尾再帰は、再帰のように表すだけループで末尾再帰をサポートしている任意の言語を使用してのオープンとなります。
「フォーク」という再帰的定義がある場合、素朴な実装はT(n)からT(n-1)、T(n-2)、T(n) 2)、T(n-3)、T(n-3)、T(n-4)である。
トリックは、T(1)とT(2)から構築するように計算を逆にしています。これは、各ステップで一定の時間を必要とするだけなので、全体的な計算は線形です。
(let ((n 2)
(t-n 2)
(t-n-1 1))
…)
とスタートのは、更新のためdo
ループを使用してみましょう:
(do ((n 2 (1+ n))
(t-n 2 (+ t-n (* n t-n-1)))
(t-n-1 1 t-n))
…)
今、あなたはちょうどあなたがあなたの希望n
に達したときに停止する必要があります。
(defun telephone-number (x)
(do ((n 2 (1+ n))
(t-n 2 (+ t-n (* n t-n-1)))
(t-n-1 1 t-n))
((= n x) t-n)))
であるために入力を確認してください:
(defun telephone-number (x)
(check-type x (integer 1))
(if (< x 3)
x
(do ((n 2 (1+ n))
(t-n 2 (+ t-n (* n t-n-1)))
(t-n-1 1 t-n))
((= n x) t-n))))
また、テストを作成し、これが何であり、どのように使用するのかのドキュメントを追加してください。これはまだテストされていません。このテール再帰を書くとき
、あなたは新しい値で再帰:末尾再帰が最適化されている場合
(defun telephone (x)
(labels ((tel-aux (n t-n t-n-1)
(if (= n x)
t-n
(tel-aux (1+ n)
(+ t-n (* n t-n-1))
t-n))))
(tel-aux 2 2 1)))
、これはループのようにスケール(ただし、一定の係数は異なる場合があります)。 Common Lispはテールコールの最適化を要求していないことに注意してください。
これは素晴らしいです!しかし何らかの理由で、出力番号が期待どおりではないように見えます。 (すなわち(電話機10)は9496でなければならないが、このコードでは1890である)。) – user3745602
@ user3745602の場合、正しいバージョンは次のとおりです: '(defun telephone-number(x) (チェックタイプx(整数1)) (if(
Renzo
@Renzo:' n'は現在の 'n'を追跡するので、2で始まり、' n'で乗算し、 'n'と' x'を比較してください。訂正してくれてありがとう、私は編集する(まだテストされていない、しかし)。 – Svante