scheme, continued-fraction, tail-recursion

Question

As a scheme-newbie I'm trying to solve some basic problems.
One of them are continued fractions, which I like to realize both ways, recursively and via tailrecursion.
My recursive soloution (d and n are functions and k is the recursion-depth):

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

is working like I want to, but I've no idea, how to makte this tail-recursively.
I do not to recognize, which expression I have to to accumulate in which way.

Answer 1

Remark that your function computes:

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

If you want to compute

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

you need to reverse the order of the coefficients:

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

For a tail-recursive function you just need to keep:

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

in the accumulator, without the need to reverse the coefficients:

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

The expressions (c-fraction2 d n k) and (c-fraction-tail d n k 1) give the same results.