scheme - 方案，连续分数，尾递归

Question

作为一个计划新手，我正在尝试解决一些基本问题。
其中之一是连分数，我喜欢通过递归和尾递归两种方式来实现。
我的递归解决方案（d 和 n 是函数，k 是递归深度）：

(define (c-fraction d n k)
  (if (= k 0) 1 
      (/ (n k) (+ (d k) (c-fraction d n (- k 1))))))

正在像我想要的那样工作，但我不知道如何递归地制作这个尾巴。
我不承认，我必须以哪种方式积累哪种表情。

Answer 1

请注意，您的函数计算：

n_k / (d_k + n_{k - 1} / (d_{k - 1} + ...

如果你想计算

n_1 / (d_1 + n_2 / (d_2 + ...

您需要颠倒系数的顺序：

(define (c-fraction2 d n k)
  (c-fraction
    (lambda (x) (d (+ 1 (- k x))))
    (lambda (x) (n (+ 1 (- k x))))
    k
  )
)

对于尾递归函数，您只需要保留：

n_k / (d_k + n_{k + 1} / (d_{k + 1} +

在累加器中，无需反转系数：

(define (c-fraction-tail d n k acc)
  (if (= k 0)
    acc
    (c-fraction-tail
      d
      n
      (- k 1)
      (/ (n k) (+ (d k) acc))
    )
  )
)

表达式(c-fraction2 d n k)并(c-fraction-tail d n k 1)给出相同的结果。